On the multi-level splitting of finite element spaces

Summary In this paper we analyze the condition number of the stiffness matrices arising in the discretization of selfadjoint and positive definite plane elliptic boundary value problems of second order by finite element methods when using hierarchical bases of the finite element spaces instead of the usual nodal bases. We show that the condition number of such a stiffness matrix behaves like O((log )²) where is the condition number of the stiffness matrix with respect to a nodal basis. In the case of a triangulation with uniform mesh sizeh this means that the stiffness matrix with respect to a hierarchical basis of the finite element space has a condition number behaving like instead of for a nodal basis. The proofs of our theorems do not need any regularity properties of neither the continuous problem nor its discretization. Especially we do not need the quasiuniformity of the employed triangulations. As the representation of a finite element function with respect to a hierarchical basis can be converted very easily and quickly to its representation with respect to a nodal basis, our results mean that the method of conjugate gradients needs onlyO(log n) steps andO(n log n) computer operations to reduce the energy norm of the error by a given factor if one uses hierarchical bases or related preconditioning procedures. Heren denotes the dimension of the finite element space and of the discrete linear problem to be solved.     

Incomplete block-matrix factorization iterative methods for convection-diffusion problems

Standard Galerkin finite element methods or finite difference methods for singular perturbation problems lead to strongly unsymmetric matrices, which furthermore are in general notM-matrices. Accordingly, preconditioned iterative methods such as preconditioned (generalized) conjugate gradient methods, which have turned out to be very successful for symmetric and positive definite problems, can fail to converge or require an excessive number of iterations for singular perturbation problems.This is not so much due to the asymmetry, as it is to the fact that the spectrum can have both eigenvalues with positive and negative real parts, or eigenvalues with arbitrary small positive real parts and nonnegligible imaginary parts. This will be the case for a standard Galerkin method, unless the meshparameterh is chosen excessively small. There exist other discretization methods, however, for which the corresponding bilinear form is coercive, whence its finite element matrix has only eigenvalues with positive real parts; in fact, the real parts are positive uniformly in the singular perturbation parameter.In the present paper we examine the streamline diffusion finite element method in this respect. It is found that incomplete block-matrix factorization methods, both on classical form and on an inverse-free (vectorizable) form, coupled with a general least squares conjugate gradient method, can work exceptionally well on this type of problem. The number of iterations is sometimes significantly smaller than for the corresponding almost symmetric problem where the velocity field is close to zero or the singular perturbation parameter =1.The 2 ^nd author's research was sponsored by Control Data Corporation through its PACER fellowship program.The 3 ^rd author's research was supported by the Netherlands organization for scientific research (NWO).On leave from the Institute of Mathematics, Academy of Science, 1090 Sofia, P.O. Box 373, Bulgaria.     

The cascadic multigrid method for elliptic problems

Summary. The paper deals with certain adaptive multilevel methods at the confluence of nested multigrid methods and iterative methods based on the cascade principle of [10]. From the multigrid point of view, no correction cycles are needed; from the cascade principle view, a basic iteration method without any preconditioner is used at successive refinement levels. For a prescribed error tolerance on the final level, more iterations must be spent on coarser grids in order to allow for less iterations on finer grids. A first candidate of such a cascadic multigrid method was the recently suggested cascadic conjugate gradient method of [9], in short CCG method, whichused the CG method as basic iteration method on each level. In [18] it has been proven, that the CCG method is accurate with optimal complexity for elliptic problems in 2D and quasi-uniform triangulations. The present paper simplifies that theory and extends it to more general basic iteration methods like the traditional multigrid smoothers. Moreover, an adaptive control strategy for the number of iterations on successive refinement levels for possibly highly non-uniform grids is worked out on the basis of a posteriori estimates. Numerical tests confirm the efficiency and robustness of the cascadic multigrid method. Received November 12, 1994 / Revised version received October 12, 1995     

Algebraic multilevel preconditioning methods. I

Summary A recursive way of constructing preconditioning matrices for the stiffness matrix in the discretization of selfadjoint second order elliptic boundary value problems is proposed. It is based on a sequence of nested finite element spaces with the usual nodal basis functions. Using a nodeordering corresponding to the nested meshes, the finite element stiffness matrix is recursively split up into two-level block structures and is factored approximately in such a way that any successive Schur complement is replaced (approximated) by a matrix defined recursively and thereform only implicitely given. To solve a system with this matrix we need to perform a fixed number (v) of iterations on the preceding level using as an iteration matrix the preconditioning matrix already defined on that level. It is shown that by a proper choice of iteration parameters it suffices to use \left( {1 - \gamma ^2 } \right)^{ - \tfrac{1}{2}} $$ " align="middle" border="0"> iterations for the so constructedv-foldV-cycle (wherev=2 corresponds to aW-cycle) preconditioning matrices to be spectrally equivalent to the stiffness matrix. The conditions involve only the constant in the strengthened C.-B.-S. inequality for the corresponding two-level hierarchical basis function spaces and are therefore independent of the regularity of the solution for instance. If we use successive uniform refinements of the meshes the method is of optimal order of computational complexity, if . Under reasonable assumptions of the finite element mesh, the condition numbers turn out to be so small that there are in practice few reasons to use an accelerated iterative method like the conjugate gradient method, for instance.Dedicated to the memory of Peter HenriciThe research of the second author reported here was supported in part by the Committee of Science, Bulgaria, under Grant No. 55/26.03.87     

Block SSOR preconditionings for high order 3d fe systems

For solving 3D high order hierarchical FE systems the block SSOR preconditioned CG algorithms based on new stripwise block two-color orderings of degrees of freedom and providing for efficient concurrent/vector implementation are suggested. As demonstrated by numerical results for the 3D Navier equations approximated using hierarchical orderp, 2 p 5, FE's the convergence rate of such BSSOR-CG algorithms is only slightly dependent onp and mesh nonunformity.     

Implementation of a modified Marder–Weitzner method for solving nonlinear eigenvalue problems

Our goal is to propose four versions of modified Marder–Weitzner methods and to present the implementation of the new-type methods with incremental unknowns for solving nonlinear eigenvalue problems. By combining with compact schemes and modified Marder–Weitzner methods, six schemes well suited for the calculation of unstable solutions are obtained. We illustrate the efficiency of the new algorithms by using numerical computations and by comparing them with existing methods for some two-dimensional problems.     

Condition number and diagonal preconditioning: comparison of the p-version and the spectral element methods

Summary. In the framework of adaptive methods, bases of hierarchical type are used in the -version of the finite element method. We study the matrices corresponding to the commonly used basis, introduced by Babuška and Szabo, in the case of -dimensional rectangular elements for 2 order elliptic boundary value problems. For the internal nodes, we show that the condition number is equivalent to and to for the stiffness and mass matrix, respectively. Moreover, we show that the usual diagonal preconditioning divides in the previous orders the exponents of by two. Finally, we compare these results with those obtained for spectral elements (nodal basis). Received November 24, 1994 / Revised version received March 20, 1995     

A class of modified block SSOR preconditioners for symmetric positive definite systems of linear equations

A class of modified block SSOR preconditioners is presented for solving symmetric positive definite systems of linear equations, which arise in the hierarchical basis finite element discretizations of the second order self‐adjoint elliptic boundary value problems. This class of methods is strongly related to two level methods, standard multigrid methods, and Jacobi‐like hierarchical basis methods. The optimal relaxation factors and optimal condition numbers are estimated in detail. Theoretical analyses show that these methods are very robust, and especially well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes. This revised version was published online in June 2006 with corrections to the Cover Date.     

An iterative substructuring algorithm for equilibrium equations

Summary The topic of iterative substructuring methods, and more generally domain decomposition methods, has been extensively studied over the past few years, and the topic is well advanced with respect to first and second order elliptic problems. However, relatively little work has been done on more general constrained least squares problems (or equivalent formulations) involving equilibrium equations such as those arising, for example, in realistic structural analysis applications. The potential is good for effective use of iterative algorithms on these problems, but such methods are still far from being competitive with direct methods in industrial codes. The purpose of this paper is to investigate an order reducing, preconditioned conjugate gradient method proposed by Barlow, Nichols and Plemmons for solving problems of this type. The relationships between this method and nullspace methods, such as the force method for structures and the dual variable method for fluids, are examined. Convergence properties are discussed in relation to recent optimality results for Varga's theory ofp-cyclic SOR. We suggest a mixed approach for solving equilibrium equations, consisting of both direct reduction in the substructures and the conjugate gradient iterative algorithm to complete the computations.Dedicated to R. S. Varga on the occasion of his 60th birthdayResearch completed while pursuing graduate studies sponsored by the Department of Mathematical Sciences, US Air Force Academy, CO, and funded by the Air Force Institute of Technology, WPAFB, OHResearch supported by the Air Force under grant no. AFOSR-88-0285 and by the National Science Foundation under grant no. DMS-89-02121     

Block triangular preconditioners for nonsymmetric saddle point problems: field-of-values analysis

A preconditioned minimal residual method for nonsymmetric saddle point problems is analyzed. The proposed preconditioner is of block triangular form. The aim of this article is to show that a rigorous convergence analysis can be performed by using the field of values of the preconditioned linear system. As an example, a saddle point problem obtained from a mixed finite element discretization of the Oseen equations is considered. The convergence estimates obtained by using a field–of–values analysis are independent of the discretization parameter h. Several computational experiments supplement the theoretical results and illustrate the performance of the method. Received March 20, 1997 / Revised version received January 14, 1998     

Incremental unknowns for solving partial differential equations

Summary Incremental unknowns have been proposed in [T] as a method to approximate fractal attractors by using finite difference approximations of evolution equations. In the case of linear elliptic problems, the utilization of incremental unknown methods provides a new way for solving such problems using several levels of discretization; the method is similar but different from the classical multigrid method.In this article we describe the application of incremental unknowns for solving Laplace equations in dimensions one and two. We provide theoretical results concerning two-level approximations and we report on numerical tests done with multi-level approximations.     

Using approximate inverses in algebraic multilevel methods

Summary. This paper deals with the iterative solution of large sparse symmetric positive definite systems. We investigate preconditioning techniques of the two-level type that are based on a block factorization of the system matrix. Whereas the basic scheme assumes an exact inversion of the submatrix related to the first block of unknowns, we analyze the effect of using an approximate inverse instead. We derive condition number estimates that are valid for any type of approximation of the Schur complement and that do not assume the use of the hierarchical basis. They show that the two-level methods are stable when using approximate inverses based on modified ILU techniques, or explicit inverses that meet some row-sum criterion. On the other hand, we bring to the light that the use of standard approximate inverses based on convergent splittings can have a dramatic effect on the convergence rate. These conclusions are numerically illustrated on some examples Received March 3, 1997 / Revised version received July 16, 1997     

Multilevel diagonal scaling preconditioners for boundary element equations on locally refined meshes

Summary. We study a multilevel preconditioner for the Galerkin boundary element matrix arising from a symmetric positive-definite bilinear form. The associated energy norm is assumed to be equivalent to a Sobolev norm of positive, possibly fractional, order m on a bounded (open or closed) surface of dimension d, with . We consider piecewise linear approximation on triangular elements. Successive levels of the mesh are created by selectively subdividing elements within local refinement zones. Hanging nodes may be created and the global mesh ratio can grow exponentially with the number of levels. The coarse-grid correction consists of an exact solve, and the correction on each finer grid amounts to a simple diagonal scaling involving only those degrees of freedom whose associated nodal basis functions overlap the refinement zone. Under appropriate assumptions on the choice of refinement zones, the condition number of the preconditioned system is shown to be bounded by a constant independent of the number of degrees of freedom, the number of levels and the global mesh ratio. In addition to applying to Galerkin discretisation of hypersingular boundary integral equations, the theory covers finite element methods for positive-definite, self-adjoint elliptic problems with Dirichlet boundary conditions. Received October 5, 2001 / Revised version received December 5, 2001 / Published online April 17, 2002 The support of this work through Visiting Fellowship grant GR/N21970 from the Engineering and Physical Sciences Research Council of Great Britain is gratefully acknowledged. The second author was also supported by the Australian Research Council     

Two-level hierarchically preconditioned conjugate gradient methods for solving linear elasticity finite element equations

In this paper we study and compare some preconditioned conjugate gradient methods for solving large-scale higher-order finite element schemes approximating two- and three-dimensional linear elasticity boundary value problems. The preconditioners discussed in this paper are derived from hierarchical splitting of the finite element space first proposed by O. Axelsson and I. Gustafsson. We especially focus our attention to the implicit construction of preconditioning operators by means of some fixpoint iteration process including multigrid techniques. Many numerical experiments confirm the efficiency of these preconditioners in comparison with classical direct methods most frequently used in practice up to now.     

Preconditioned iterative methods for a class of nonlinear eigenvalue problems

This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem.     

Two preconditioners based on the multi-level splitting of finite element spaces

Summary The hierarchical basis preconditioner and the recent preconditioner of Bramble, Pasciak and Xu are derived and analyzed within a joint framework. This discussion elucidates the close relationship between both methods. Special care is devoted to highly nonuniform meshes; exclusively local properties like the shape regularity of the finite elements are utilized.The author was supported by the Konrad-Zuse-Zentrum für Informationstechnik Berlin, Federal Republic of Germany     

An algorithm for coarsening unstructured meshes

Summary. We develop and analyze a procedure for creating a hierarchical basis of continuous piecewise linear polynomials on an arbitrary, unstructured, nonuniform triangular mesh. Using these hierarchical basis functions, we are able to define and analyze corresponding iterative methods for solving the linear systems arising from finite element discretizations of elliptic partial differential equations. We show that such iterative methods perform as well as those developed for the usual case of structured, locally refined meshes. In particular, we show that the generalized condition numbers for such iterative methods are of order , where is the number of hierarchical basis levels. Received December 5, 1994     

Local refinement techniques for elliptic problems on cell-centered grids

Summary Algebraic multilevel analogues of the BEPS preconditioner designed for solving discrete elliptic problems on grids with local refinement are formulated, and bounds on their relative condition numbers, with respect to the composite-grid matrix, are derived. TheV-cycle and, more generally,v-foldV-cycle multilevel BEPS preconditioners are presented and studied. It is proved that for 2-D problems theV-cycle multilevel BEPS is almost optimal, whereas thev-foldV-cycle algebraic multilevel BEPS is optimal under a mild restriction on the composite cell-centered grid. For thev-fold multilevel BEPS, the variational relation between the finite difference matrix and the corresponding matrix on the next-coarser level is not necessarily required. Since they are purely algebraically derived, thev-fold (v>1) multilevel BEPS preconditioners perform without any restrictionson the shape of subregions, unless the refinement is too fast. For theV-cycle BEPS preconditioner (2-D problem), a variational relation between the matrices on two consecutive grids is required, but there is no restriction on the method of refinement on the shape, or on the size of the subdomains.     

Fourier analysis of schwarz alternating methods for piecewise hermite bicubic orthogonal spline collocation

The rates of convergence of two Schwarz alternating methods are analyzed for the iterative solution of a discrete problem which arises when orthogonal spline collocation with piecewise Hermite bicubics is applied to the Dirichlet problem for Poisson's equation on a rectangle. In the first method, the rectangle is divided into two overlapping subrectangles, while three overlapping subrectangles are used in the second method. Fourier analysis is used to obtain explicit formulas for the convergence factors by which theH ¹-norm of the errors is reduced in one iteration of the Schwarz methods. It is shown numerically that while these factors depend on the size of overlap, they are independent of the partition stepsize. Results of numerical experiments are presented which confirm the established rates of convergence of the Schwarz methods.This research was supported in part by funds from the National Science Foundation grant CCR-9103451.     

Adaptive filtering

Summary. In this paper, the adaptive filtering method is introduced and analysed. This method leads to robust algorithms for the solution of systems of linear equations which arise from the discretisation of partial differential equations with strongly varying coefficients. These iterative algorithms are based on the tangential frequency filtering decompositions (TFFD). During the iteration with a preliminary preconditioner, the adaptive test vector method calculates new test vectors for the TFFD. The adaptive test vector iterative method allows the combination of the tangential frequency decomposition and other iterative methods such as multi-grid. The connection with the TFFD improves the robustness of these iterative methods with respect to varying coefficients. Interface problems as well as problems with stochastically distributed properties are considered. Realistic numerical experiments confirm the efficiency of the presented algorithms. Received June 26, 1996 / Revised version received October 7, 1996