PRECONDITIONING HIGHER ORDER FINITE ELEMENT SYSTEMS BY ALGEBRAIC MULTIGRID METHOD OF LINEAR ELEMENTS

We present and analyze a robust preconditioned conjugate gradient method for the higher order Lagrangian finite element systems of a class of elliptic problems. An auxiliary linear element stiffness matrix is chosen to be the preconditioner for higher order finite elements. Then an algebraic multigrid method of linear finite element is applied for solving the preconditioner. The optimal condition number which is independent of the mesh size is obtained. Numerical experiments confirm the efficiency of the algorithm.     

EXPLICIT BOUNDS OF EIGENVALUES FOR STIFFNESS MATRICES BY QUADRATIC HIERARCHICAL BASIS METHOD)

The bounds for the eigenvalues of the stiffness matrices in the finite element discretiza-tion corresponding to Lu:=-u″with zero boundary conditions by quadratic hierarchical basic are shown explicitly.The condition numberof the resulting system behaves like O(1/h)where h is the mesh size.We also analyze a main diagonal preconditioner of the stiffness matrix which reduces the condition number of the preconditioned system to O(1).     

Preconditioning of the Stiffness Matrix of Local Refined Triangulation

A preconditioning method for the finite element stiffness matrix is given in this paper. The triangulation is refined in a subregion; the preconditioning process is composed of resolution of two regular subproblems; the condition number of the preconditioned matrix is O(1 logH/h), where H and h are mesh sizes of the unrefined and local refined triangulations respectively.     

Preconditioning analysis of the one dimensional incremental unknowns method on nonuniform meshes

The condition number of the incremental unknowns matrix on nonuniform meshes associated to the elliptic problem is analyzed. Comparing to the usual nodal unknowns matrix, the condition number of the incremental unknowns matrix is reduced significantly even if the meshes are nonuniform. Furthermore, if a diagonal scaling is used, the condition number of the preconditioned incremental unknowns matrix comes out to be O(1). Numerical experiments are performed respectively on Shishkin mesh and Chebyshev mesh. Computational results with respect to the two particular nonuniform meshes confirm our theoretical analysis.     

Analysis of Iterative Sub-structuring Techniques for Boundary Element Approximation of the Hypersingular Operator in Three Dimensions

The article deals with the analysis of Additive Schwarz preconditioners for the h -version of the boundary element method for the hypersingular integral equation on surfaces in three dimensions. The first preconditioner consists of decomposing into local spaces associated with the subdomain interiors, supplemented with a wirebasket space associated with the subdomain interfaces. The wirebasket correction only involves the inversion of a diagonal matrix, while the interior correction consists of inverting the sub-blocks of the stiffness matrix corresponding to the interior degrees of freedom on each subdomain. It is shown that the condition number of the preconditioned system grows at most as max K H m 1 (1 + log H / h K ) 2 where H is the size of the quasi-uniform subdomains and h K is the size of the elements in subdomain K . A second preconditioner is given that incorporates a coarse space associated with the subdomains. This improves the robustness of the method with respect to the number of subdomains: theoretical analysis shows that growth of the condition number of the preconditioned system is now bounded by max K (1 + log H / h K ) 2 .     

Conditioning analysis of block incomplete factorizations and its application to elliptic equations

Summary. The paper deals with eigenvalue estimates for block incomplete factorization methods for symmetric matrices. First, some previous results on upper bounds for the maximum eigenvalue of preconditioned matrices are generalized to each eigenvalue. Second, upper bounds for the maximum eigenvalue of the preconditioned matrix are further estimated, which presents a substantial improvement of earlier results. Finally, the results are used to estimate bounds for every eigenvalue of the preconditioned matrices, in particular, for the maximum eigenvalue, when a modified block incomplete factorization is used to solve an elliptic equation with variable coefficients in two dimensions. The analysis yields a new upper bound of type for the condition number of the preconditioned matrix and shows clearly how the coefficients of the differential equation influence the positive constant . Received March 27, 1996 / Revised version received December 27, 1996     

A robust structured preconditioner for time-harmonic parabolic optimal control problems

We consider the iterative solution of optimal control problems constrained by the time-harmonic parabolic equations. Due to the time-harmonic property of the control equations, a suitable discretization of the corresponding optimality systems leads to a large complex linear system with special two-by-two block matrix of saddle point form. For this algebraic system, an efficient preconditioner is constructed, which results in a fast Krylov subspace solver, that is robust with respect to the mesh size, frequency, and regularization parameters. Furthermore, the implementation is straightforward and the computational complexity is of optimal order, linear in the number of degrees of freedom. We show that the eigenvalue distribution of the corresponding preconditioned matrix leads to a condition number bounded above by 2. Numerical experiments confirming the theoretical derivations are presented, including comparisons with some other existing preconditioners.     

On the convergence of basic iterative methods for convection–diffusion equations

In this paper we analyze convergence of basic iterative Jacobi and Gauss–Seidel type methods for solving linear systems which result from finite element or finite volume discretization of convection–diffusion equations on unstructured meshes. In general the resulting stiffness matrices are neither M‐matrices nor satisfy a diagonal dominance criterion. We introduce two newmatrix classes and analyse the convergence of the Jacobi and Gauss–Seidel methods for matrices from these classes. A new convergence result for the Jacobi method is proved and negative results for the Gauss–Seidel method are obtained. For a few well‐known discretization methods it is shown that the resulting stiffness matrices fall into the new matrix classes. Copyright © 1999 John Wiley & Sons, Ltd.     

A Preconditioner Determined by a Subdomain Covering the Interface

1)AkeyprojectofChineseAcademyofSciences.1.IntroductionLetnCR2beapolygonalregion,andbeanellipticoperatordefinedonit;here,(ai,j)i,j=1,2issymmetricpositivedefiniteandboundedfromaboveandbelowonfl,c2O.isthevariationalformoftheboundaryvalueproblem,withthebilinearformForconveniencewediscusson1ythehomogeneousDirichletboundaryvalueproblemhere.ThenorminHl(fl)introducedbya(.,.)isequivalenttotheoriginalone.Hj(fl)willbetreatedasaHilbertspacewithinnerprodueta(.,-)inthefollowing-(1,1)isdiscretizedbythefi…     

COMBINATIVE PRECONDITIONERS OF MODIFIED INCOMPLETE CHOLESKY FACTORIZATION AND SHERMAN-MORRISON-WOODBURY UPDATE FOR SELF-ADJOINT ELLIPTIC DIRICHLET-PERIODIC BOUNDARY VALUE PROBLEMS

For the system of linear equations arising from discretization of the second-order self-adjoint elliptic Dirichlet-periodic boundary value problems,by making use of the specialstructure of the coefficient matrix we present a class of combinative preconditioners whichare technical combinations of modified incomplete Cholesky factorizations and Sherman-Morrison-Woodbury update.Theoretical analyses show that the condition numbers of thepreconditioned matrices can be reduced to(?)(h~(-1)),one order smaller than the conditionnumber(?)(h~(-2))of the original matrix.Numerical implementations show that the resultingpreconditioned conjugate gradient methods are feasible,robust and efficient for solving thisclass of linear systems.     

Equivalent operator preconditioning for elliptic problems with nonhomogeneous mixed boundary conditions

The numerical solution of linear elliptic partial differential equations often involves finite element discretization, where the discretized system is usually solved by some conjugate gradient method. The crucial point in the solution of the obtained discretized system is a reliable preconditioning, that is to keep the condition number of the systems under control, no matter how the mesh parameter is chosen. The PCG method is applied to solving convection-diffusion equations with nonhomogeneous mixed boundary conditions. Using the approach of equivalent and compact-equivalent operators in Hilbert space, it is shown that for a wide class of elliptic problems the superlinear convergence of the obtained preconditioned CGM is mesh independent under FEM discretization.     

Additive Schwarz Method for Mortar Discretization of Elliptic Problems with <Emphasis Type="Italic">P</Emphasis><Subscript>1</Subscript> Nonconforming Finite Elements

An additive Schwarz preconditioner for nonconforming mortar finite element discretization of a second order elliptic problem in two dimensions with arbitrary large jumps of the discontinuous coefficients in subdomains is described. An almost optimal estimate of the condition number of the preconditioned problem is proved. The number of preconditioned conjugate gradient iterations is independent of jumps of the coefficients and is proportional to (1+log(H/h)), where H,h are mesh sizes. AMS subject classification (2000) 65N55, 65N30, 65N22     

WELL-CONDITIONED FRAMES FOR HIGH ORDER FINITE ELEMENT METHODS

The purpose of this paper is to discuss representations of high order C⁰finite element spaces on simplicial meshes in any dimension.When computing with high order piecewise polynomials the conditioning of the basis is likely to be important.The main result of this paper is a construction of representations by frames such that the associated L²condition number is bounded independently of the polynomial degree.To our knowledge,such a representation has not been presented earlier.The main tools we will use for the construction is the bubble transform,introduced previously in[1],and properties of Jacobi polynomials on simplexes in higher dimensions.We also include a brief discussion of preconditioned iterative methods for the finite element systems in the setting of representations by frames.     

A preconditioner for generalized saddle point problems: Application to 3D stationary Navier‐Stokes equations

In this article we consider the stationary Navier‐Stokes system discretized by finite element methods which do not satisfy the inf‐sup condition. These discretizations typically take the form of a variational problem with stabilization terms. Such a problem may be transformed by iteration methods into a sequence of linear, Oseen‐type variational problems. On the algebraic level, these problems belong to a certain class of linear systems with nonsymmetric system matrices (“generalized saddle point problems”). We show that if the underlying finite element spaces satisfy a generalized inf‐sup condition, these problems have a unique solution. Moreover, we introduce a block triangular preconditioner and we show how the eigenvalue bounds of the preconditioned system matrix depend on the coercivity constant and continuity bounds of the bilinear forms arising in the variational problem. Finally we prove that the stabilized P1‐P1 finite element method proposed by Rebollo is covered by our theory and we show that the condition number of the preconditioned system matrix is independent of the mesh size. Numerical tests with 3D stationary Navier‐Stokes flows confirm our results. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006     

A new Jacobi operational matrix: An application for solving fractional differential equations

In this paper, we derived the shifted Jacobi operational matrix (JOM) of fractional derivatives which is applied together with spectral tau method for numerical solution of general linear multi-term fractional differential equations (FDEs). A new approach implementing shifted Jacobi operational matrix in combination with the shifted Jacobi collocation technique is introduced for the numerical solution of nonlinear multi-term FDEs. The main characteristic behind this approach is that it reduces such problems to those of solving a system of algebraic equations which greatly simplifying the problem. The proposed methods are applied for solving linear and nonlinear multi-term FDEs subject to initial or boundary conditions, and the exact solutions are obtained for some tested problems. Special attention is given to the comparison of the numerical results obtained by the new algorithm with those found by other known methods.     

Domain decomposition preconditioners for multiscale problems in linear elasticity

We analyze two‐level overlapping Schwarz domain decomposition methods for vector‐valued piecewise linear finite element discretizations of the PDE system of linear elasticity. The focus of our study lies in the application to compressible, particle‐reinforced composites in 3D with large jumps in their material coefficients. We present coefficient‐explicit bounds for the condition number of the two‐level additive Schwarz preconditioned linear system. Thereby, we do not require that the coefficients are resolved by the coarse mesh. The bounds show a dependence of the condition number on the energy of the coarse basis functions, the coarse mesh, and the overlap parameters, as well as the coefficient variation. Similar estimates have been developed for scalar elliptic PDEs by Graham et al. 1 The coarse spaces to which they apply here are assumed to contain the rigid body modes and can be considered as generalizations of the space of piecewise linear vector‐valued functions on a coarse triangulation. The developed estimates provide a concept for the construction of coarse spaces, which can lead to preconditioners that are robust with respect to high contrasts in Young's modulus and the Poisson ratio of the underlying composite. To confirm the sharpness of the theoretical findings, we present numerical results in 3D using vector‐valued linear, multiscale finite element and energy‐minimizing coarse spaces. The theory is not restricted to the isotropic (Lamé) case, extends to the full‐tensor case, and allows applications to multiphase materials with anisotropic constituents in two and three spatial dimensions. However, the bounds will depend on the ratio of largest to smallest eigenvalue of the elasticity tensor.     

Realistic Eigenvalue Bounds for the Galerkin Mass Matrix

In time-dependent finite-element calculations, a mass matrixnaturally arises. To avoid the solution of the correspondingalgebraic equation system at each time step, ‘mass lumping’is widely used, even though this pragmatic diagonalization ofthe mass matrix often reduces accuracy. We show how the unassembled form of finite-element equationscan be used to establish (in an element-by-element manner) realisticupper and lower bounds on the eigenvalues of the fully consistentmass matrix when preconditioned by its diagonal entries. Weuse this technique to give specific results for a number ofdifferent types of finite elements in one, two, and three dimensions.The bounds are found by independent calculations on the elements,and, for certain element types, are independent of mesh irregularity.We give examples of when some of the bounds are attained. These results indicate that the preconditioned conjugate-gradientmethod is appropriate and very rapid for the solution of Galerkinmass-matrix equations.     

Parallel Algorithms for Orthotropic Problems

Finite element meshes and node-numberings suitable for parallel solution with equally loaded processors are presented for linear orthotropic elliptic partial differential equations. These problems are of great importance, for instance in the oil and airfoil industries. The linear systems of equations are solved by the conjugate gradient method preconditioned by modified incomplete factorization, MIC. The basic method presented, is based on fronts of uncoupled nodes and unlike earlier methods it has the advantage of no requirement of a specific orientation of the mesh. This method is however, in general, restricted to small degree of anisotropy in the differential equation. Another method, which does not suffer from this limitation, uses rotation of the differential equation and spectral equivalence. The rotation is made in such a way that in the new co-ordinate system, the basic method is applicable. The spectral equivalence property is used for estimation of the condition number of the preconditioned system. Both methods are suitable for implementation on parallel computers. The computer architecture could be single instruction multiple data (SIMD) as well as multiple instruction multiple data (MIMD) with shared or distributed memory. Implementation of the basic method on a shared memory parallel computer shows a significant improvement by use of the MIC method compared with the diagonal scaling preconditioning method.     

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     

Fourier analysis of frequency filtering decomposition preconditioners

In this paper, frequency filtering decomposition (FFD) preconditioner is analyzed by the approach of Fourier analysis. The condition number estimation of a preconditioned 2-D model problem is presented. Analysis reveals that condition number of the preconditioned matrix grows like O(h^-1), with h be the mesh size. By using the framework of FFD, a stabilized frequency filtering decomposition (SFFD) method is proposed and analyzed by Fourier method. Results show that SFFD preconditioner is superior to FFD preconditioner in the sense that . Numerical tests are performed to illustrate the theoretical results and the superiority of SFFD preconditioner.