W-加密三角剖分下二元五次超样条函数空间的局部Lagrange插值

本文选取二元五次C2超样条函数空间作为插值空间,考虑局部Lagrange插值.首先对三角剖分△进行着色,通过Wang-加密三角剖分对原剖分△细分大约一半的三角形.然后通过在内边增加一些另外的光滑条件,使得样条函数在某些边上达到更高阶的光滑.最后在△的加密三角剖分内选择Lagrange插值点.结果表明相应的插值基函数具有...     

Triangulation refinement by using edge subdivision

It is proved that any triangulation of a flat polygonal region can be refined by using repeated subdivisions of an edge so that: (1) the maximum diameter of the triangles would be less than any pre-assigned positive number, and (2) the minimum interior angle of the triangles of the triangulation obtained would be not less than the minimum interior angle of the triangles of the original triangulation divided by 9. The required triangulation refinement is constructed in two steps: first, the triangulation is refined so that the triangles of the triangulation obtained can be combined into pairs, and only boundary triangles may be left unpaired; at this step each triangle is split into at most 4 parts. Then the triangulation obtained is refined once again in order that the diameter of each triangle be less then a prescribed ?. At each of the steps, the minimum interior angle of triangles is reduced by at most 3 times. This is guaranteed by the lemma saying that the interior angles of the triangles into which the original triangle is divided by a median are at least as great as one-third of the minimum interior angle of the original triangle.     

Analysis of optimal preconditioners for CutFEM

In this article, we consider a class of unfitted finite element methods for scalar elliptic problems. These so-called CutFEM methods use standard finite element spaces on a fixed unfitted triangulation combined with the Nitsche technique and a ghost penalty stabilization. As a model problem we consider the application of such a method to the Poisson interface problem. We introduce and analyze a new class of preconditioners that is based on a subspace decomposition approach. The unfitted finite element space is split into two subspaces, where one subspace is the standard finite element space associated to the background mesh and the second subspace is spanned by all cut basis functions corresponding to nodes on the cut elements. We will show that this splitting is stable, uniformly in the discretization parameter and in the location of the interface in the triangulation. Based on this we introduce an efficient preconditioner that is uniformly spectrally equivalent to the stiffness matrix. Using a similar splitting, it is shown that the same preconditioning approach can also be applied to a fictitious domain CutFEM discretization of the Poisson equation. Results of numerical experiments are included that illustrate optimality of such preconditioners for the Poisson interface problem and the Poisson fictitious domain problem.     

Some multilevel methods on graded meshes

We consider Yserentant's hierarchical basis method and multilevel diagonal scaling method on a class of refined meshes used in the numerical approximation of boundary value problems on polygonal domains in the presence of singularities. We show, as in the uniform case, that the stiffness matrix of the first method has a condition number bounded by (ln(1/h))², where h is the meshsize of the triangulation. For the second method, we show that the condition number of the iteration operator is bounded by ln(1/h), which is worse than in the uniform case but better than the hierarchical basis method. As usual, we deduce that the condition number of the BPX iteration operator is bounded by ln(1/h). Finally, graded meshes fulfilling the general conditions are presented and numerical tests are given which confirm the theoretical bounds.     

Minimal triangulation of a graph and optimal pivoting order in a sparse matrix

This paper considers the problem of finding a minimal triangulation of an undirected graph G = (V, E), where a triangulation is a set T such that every cycle in G = (V, E ∪ T) has a chord. A triangulation T is minimal (minimum) if no triangulation F exists such that F is a proper subset of $\text{T (¦F¦ < ¦T¦)}$, and an ordering α is optimal (optimum) if a minimal (minimum) triangulation is generated by α. A minimum triangulation (optimum ordering) is necessarily minimal (optimal), but the converse is not necessarily true. A necessary and sufficient condition for a triangulation to be minimal is presented. This leads to an algorithm for finding an optimal ordering α which produces a minimal set of “fill-in” when the process is viewed as triangular factorization of a sparse matrix.     

Nested dyadic grids associated with Legendre–Gauss–Lobatto grids

Legendre–Gauss–Lobatto (LGL) grids play a pivotal role in nodal spectral methods for the numerical solution of partial differential equations. They not only provide efficient high-order quadrature rules, but give also rise to norm equivalences that could eventually lead to efficient preconditioning techniques in high-order methods. Unfortunately, a serious obstruction to fully exploiting the potential of such concepts is the fact that LGL grids of different degree are not nested. This affects, on the one hand, the choice and analysis of suitable auxiliary spaces, when applying the auxiliary space method as a principal preconditioning paradigm, and, on the other hand, the efficient solution of the auxiliary problems. As a central remedy, we consider certain nested hierarchies of dyadic grids of locally comparable mesh size, that are in a certain sense properly associated with the LGL grids. Their actual suitability requires a subtle analysis of such grids which, in turn, relies on a number of refined properties of LGL grids. The central objective of this paper is to derive the main properties of the associated dyadic grids needed for preconditioning the systems arising from \(hp\)- or even spectral (conforming or Discontinuous Galerkin type) discretizations for second order elliptic problems in a way that is fully robust with respect to varying polynomial degrees. To establish these properties requires revisiting some refined properties of LGL grids and their relatives.     

Optimization of the Relaxation Parameter for S.S.O.R. and A.D.I. Preconditioning

We present and compare several approaches for the optimization of the relaxation parameter both for A.D.I. and S.S.O.R. basic iteration and preconditioning conjugate gradient method. For each kind of preconditioning a detailed link between estimates of the spectral radius of the iteration matrix and of the condition number resulting from preconditioning is proposed. It allows to choose the best approach in order to obtain the optimal relaxation parameter and the corresponding optimal estimates either of the spectral radius of the iteration matrix and of the resulting condition mumber of the S.S.O.R. and A.D.I. preconditioning.     

Stable three-point wavelet bases on general meshes

Summary. Recently, we introduced a wavelet basis on general, possibly locally refined linear finite element spaces. Each wavelet is a linear combination of three nodal basis functions, independently of the number of space dimensions. In the present paper, we show -stability of this basis for a range of , that in any case includes , which means that the corresponding additive Schwarz preconditioner is optimal for second order problems. Furthermore, we generalize the construction of the wavelet basis to manifolds. We show that the wavelets have at least one-, and in areas where the manifold is smooth and the mesh is uniform even two vanishing moments. Because of these vanishing moments, apart from preconditioning, the basis can be used for compression purposes: For a class of integral equation problems, the stiffness matrix with respect to the wavelet basis will be close to a sparse one, in the sense that, a priori, it can be compressed to a sparse matrix without the order of convergence being reduced. Received November 6, 1996 / Revised version received June 30, 1997     

Composite orthogonal projection methods for large matrix eigenproblems

For classical orthogonal projection methods for large matrix eigenproblems, it may be much more difficult for a Ritz vector to converge than for its corresponding Ritz value when the matrix in question is non-Hermitian. To this end, a class of new refined orthogonal projection methods has been proposed. It is proved that in some sense each refined method is a composite of two classical orthogonal projections, in which each refined approximate eigenvector is obtained by realizing a new one of some Hermitian semipositive definite matrix onto the same subspace. Apriori error bounds on the refined approximate eigenvector are established in terms of the sine of acute angle of the normalized eigenvector and the subspace involved. It is shown that the sufficient conditions for convergence of the refined vector and that of the Ritz value are the same, so that the refined methods may be much more efficient than the classical ones.     

Approximate factoring of the inverse

Computation of approximate factors for the inverse constitutes an algebraic approach to preconditioning large and sparse linear systems. In this paper, the aim is to combine standard preconditioning ideas with sparse approximate inverse approximation, to have dense approximate inverse approximations (implicitly). For optimality, the approximate factoring problem is associated with a minimization problem involving two matrix subspaces. This task can be converted into an eigenvalue problem for a Hermitian positive semidefinite operator whose smallest eigenpairs are of interest. Because of storage and complexity constraints, the power method appears to be the only admissible algorithm for devising sparse–sparse iterations. The subtle issue of choosing the matrix subspaces is addressed. Numerical experiments are presented.     

On the adjacencies of triangular meshes based on skeleton-regular partitions

For any 2D triangulation τ, the 1-skeleton mesh of τ is the wireframe mesh defined by the edges of τ, while that for any 3D triangulation τ, the 1-skeleton and the 2-skeleton meshes, respectively, correspond to the wireframe mesh formed by the edges of τ and the “surface” mesh defined by the triangular faces of τ. A skeleton-regular partition of a triangle or a tetrahedra, is a partition that globally applied over each element of a conforming mesh (where the intersection of adjacent elements is a vertex or a common face, or a common edge) produce both a refined conforming mesh and refined and conforming skeleton meshes. Such a partition divides all the edges (and all the faces) of an individual element in the same number of edges (faces). We prove that sequences of meshes constructed by applying a skeleton-regular partition over each element of the preceding mesh have an associated set of difference equations which relate the number of elements, faces, edges and vertices of the nth and (n−1)th meshes. By using these constitutive difference equations we prove that asymptotically the average number of adjacencies over these meshes (number of triangles by node and number of tetrahedra by vertex) is constant when n goes to infinity. We relate these results with the non-degeneracy properties of longest-edge based partitions in 2D and include empirical results which support the conjecture that analogous results hold in 3D.     

On the eigenvalue distribution of a class of preconditioning methods

Summary A class of preconditioning methods depending on a relaxation parameter is presented for the solution of large linear systems of equationAx=b, whereA is a symmetric positive definite matrix. The methods are based on an incomplete factorization of the matrixA and include both pointwise and blockwise factorization. We study the dependence of the rate of convergence of the preconditioned conjugate gradient method on the distribution of eigenvalues ofC ^–1 A, whereC is the preconditioning matrix. We also show graphic representations of the eigenvalues and present numerical tests of the methods.     

Diagonally compensated reduction and related preconditioning methods

When solving linear algebraic equations with large and sparse coefficient matrices, arising, for instance, from the discretization of partial differential equations, it is quite common to use preconditioning to accelerate the convergence of a basic iterative scheme. Incomplete factorizations and sparse approximate inverses can provide efficient preconditioning methods but their existence and convergence theory is based mostly on M-matrices (H-matrices). In some application areas, however, the arising coefficient matrices are not H-matrices. This is the case, for instance, when higher-order finite element approximations are used, which is typical for structural mechanics problems. We show that modification of a symmetric, positive definite matrix by reduction of positive offdiagonal entries and diagonal compensation of them leads to an M-matrix. This diagonally compensated reduction can take place in the whole matrix or only at the current pivot block in a recursive incomplete factorization method. Applications for constructing preconditioning matrices for finite element matrices are described.     

Prefiltration technique via aggregation for constructing low‐density high‐quality factorized sparse approximate inverse preconditionings

This paper considers a new approach to a priori sparsification of the sparsity pattern of the factorized approximate inverses (FSAI) preconditioner using the so‐called vector aggregation technique. The suggested approach consists in construction of the FSAI preconditioner to the aggregated matrix with a prescribed sparsity pattern. Then small entries of the computed ‘aggregated’ FSAI preconditioning matrix are dropped, and the resulting pointwise sparsity pattern is used to construct the low‐density block sparsity pattern of the FSAI preconditioning matrix to the original matrix. This approach allows to minimize (sometimes significantly) the construction costs of low‐density high‐quality FSAI preconditioners. Numerical results with sample matrices from structural mechanics and thin shell problems are presented. Copyright © 2002 John Wiley & Sons, Ltd.     

On the preconditioning of matrices with skew-symmetric splittings

The rates of convergence of iterative methods with standard preconditioning techniques usually degrade when the skew-symmetric part S of the matrix is relatively large. In this paper, we address the issue of preconditioning matrices with such large skew-symmetric parts. The main idea of the preconditioner is to split the matrix into its symmetric and skew-symmetric parts and to invert the (shifted) skew-symmetric matrix. Successful use of the method requires the solution of a linear system with matrix I+S. An efficient method is developed using the normal equations, preconditioned by an incomplete orthogonal factorization.Numerical experiments on various systems arising in physics show that the reduction in terms of iteration count compensates for the additional work per iteration when compared to standard preconditioners.     

Constraint preconditioning for nonsymmetric indefinite linear systems

This paper introduces and presents theoretical analyses of constraint preconditioning via a Schilders'‐like factorization for nonsymmetric saddle‐point problems. We extend the Schilders' factorization of a constraint preconditioner to a nonsymmetric matrix by using a different factorization. The eigenvalue and eigenvector distributions of the preconditioned matrix are determined. The choices of the parameter matrices in the extended Schilders' factorization and the implementation of the preconditioning step are discussed. An upper bound on the degree of the minimum polynomial for the preconditioned matrix and the dimension of the corresponding Krylov subspace are determined, as well as the convergence behavior of a Krylov subspace method such as GMRES. Numerical experiments are presented. Copyright © 2009 John Wiley & Sons, Ltd.     

Composite orthogonal projection methods for large matrix eigenproblems

For classical orthogonal projection methods for large matrix eigenproblems, it may be much more difficult for a Ritz vector to converge than for its corresponding Ritz value when the matrix in question is non-Hermitian. To this end, a class of new refined orthogonal projection methods has been proposed. It is proved that in some sense each refined method is a composite of two classical orthogonal projections, in which each refined approximate eigenvector is obtained by realizing a new one of some Hermitian semipositive definite matrix onto the same subspace. Apriori error bounds on the refined approximate eigenvector are established in terms of the sine of acute angle of the normalized eigenvector and the subspace involved. It is shown that the sufficient conditions for convergence of the refined vector and that of the Ritz value are the same, so that the refined methods may be much more efficient than the classical ones. Project supported by the China State Major Key Projects for Basic Researches, the National Natural Science Foundation of China (Grant No. 19571014), the Doctoral Program (97014113), the Foundation of Excellent Young Scholors of Ministry of Education, the Foundation of Returned Scholars of China and the Liaoning Province Natural Science Foundation.     

The structured distance to normality of Toeplitz matrices with application to preconditioning

A formula for the distance of a Toeplitz matrix to the subspace of {e^i?}‐circulant matrices is presented, and applications of {e^i?}‐circulant matrices to preconditioning of linear systems of equations with a Toeplitz matrix are discussed. Copyright © 2010 John Wiley & Sons, Ltd.     

Multiplicative Correction of a Matrix on a Sequence of Subspaces. I: Basic Algorithms and Theory for General Unsymmetric Matrices

The paper considers the problem of a guaranteed improvement of matrix properties by preconditioning. An algorithm for constructing the so-called correcting operators, differing from the identity matrix by a small-rank term, is suggested. A correcting operator improves the matrix action on a subspace of small dimension and provides the possibility of controlling its action on the complementary subspace. In the algorithm suggested, correcting operators are computed by using the operation of multiplying the original matrix by a vector. The resulting preconditioner is a composition of basic correctors. Its nonsingularity is established in the general unsymmetric and indefinite case, and estimates enabling one to predict the convergence properties of the corresponding iterative algorithm are obtained. In order to reduce the arithmetic and memory costs, it is suggested to replace correcting operators by their approximations. Estimates for the resulting deterioration of the preconditioning quality are presented. Bibliography: 3 titles.     

An incomplete-factorization preconditioning using repeated red-black ordering

Summary The convergence of the conjugate gradient method for the iterative solution of large systems of linear equations depends on proper preconditioning matrices. We present an efficient incomplete-factorization preconditioning based on a specific, repeated red-black ordering scheme and cyclic reduction. For the Dirichlet model problem, we prove that the condition number increases asymptotically slower with the number of equations than for usual incomplete factorization methods. Numerical results for symmetric and non-symmetric test problems and on locally refined grids demonstrate the performance of this method, especially for large linear systems.