On preconditioned eigensolvers and Invert-Lanczos processes

This paper deals with the convergence analysis of various preconditioned iterations to compute the smallest eigenvalue of a discretized self-adjoint and elliptic partial differential operator. For these eigenproblems several preconditioned iterative solvers are known, but unfortunately, the convergence theory for some of these solvers is not very well understood.The aim is to show that preconditioned eigensolvers (like the preconditioned steepest descent iteration (PSD) and the locally optimal preconditioned conjugate gradient method (LOPCG)) can be interpreted as truncated approximate Krylov subspace iterations. In the limit of preconditioning with the exact inverse of the system matrix (such preconditioning can be approximated by multiple steps of a preconditioned linear solver) the iterations behave like Invert-Lanczos processes for which convergence estimates are derived.     

A comparison of preconditioned Krylov subspace methods for large‐scale nonsymmetric linear systems

Preconditioned Krylov subspace (KSP) methods are widely used for solving large‐scale sparse linear systems arising from numerical solutions of partial differential equations (PDEs). These linear systems are often nonsymmetric due to the nature of the PDEs, boundary or jump conditions, or discretization methods. While implementations of preconditioned KSP methods are usually readily available, it is unclear to users which methods are the best for different classes of problems. In this work, we present a comparison of some KSP methods, including GMRES, TFQMR, BiCGSTAB, and QMRCGSTAB, coupled with three classes of preconditioners, namely, Gauss–Seidel, incomplete LU factorization (including ILUT, ILUTP, and multilevel ILU), and algebraic multigrid (including BoomerAMG and ML). Theoretically, we compare the mathematical formulations and operation counts of these methods. Empirically, we compare the convergence and serial performance for a range of benchmark problems from numerical PDEs in two and three dimensions with up to millions of unknowns and also assess the asymptotic complexity of the methods as the number of unknowns increases. Our results show that GMRES tends to deliver better performance when coupled with an effective multigrid preconditioner, but it is less competitive with an ineffective preconditioner due to restarts. BoomerAMG with a proper choice of coarsening and interpolation techniques typically converges faster than ML, but both may fail for ill‐conditioned or saddle‐point problems, whereas multilevel ILU tends to succeed. We also show that right preconditioning is more desirable. This study helps establish some practical guidelines for choosing preconditioned KSP methods and motivates the development of more effective preconditioners.     

A Rayleigh quotient minimization algorithm based on algebraic multigrid

This paper presents a new algebraic extension of the Rayleigh quotient multigrid (RQMG) minimization algorithm to compute the smallest eigenpairs of a symmetric positive definite pencil ( A , M ). Earlier versions of RQMG minimize the Rayleigh quotient over a hierarchy of geometric grids. We replace the geometric mesh information with the algebraic information defined by an algebraic multigrid preconditioner. At each level, we minimize the Rayleigh quotient with a block preconditioned algorithm. Numerical experiments illustrate the efficiency of this new algorithm to compute several eigenpairs. Copyright © 2007 John Wiley & Sons, Ltd.     

A Black-Box Multigrid Preconditioner for the Biharmonic Equation

We examine the convergence characteristics of a preconditioned Krylov subspace solver applied to the linear systems arising from low-order mixed finite element approximation of the biharmonic problem. The key feature of our approach is that the preconditioning can be realized using any “black-box” multigrid solver designed for the discrete Dirichlet Laplacian operator. This leads to preconditioned systems having an eigenvalue distribution consisting of a tightly clustered set together with a small number of outliers. Numerical results show that the performance of the methodology is competitive with that of specialized fast iteration methods that have been developed in the context of biharmonic problems. This revised version was published online in July 2006 with corrections to the Cover Date.     

High Accuracy Solution of Three-Dimensional Biharmonic Equations

In this paper, we consider several finite-difference approximations for the three-dimensional biharmonic equation. A symbolic algebra package is utilized to derive a family of finite-difference approximations for the biharmonic equation on a 27 point compact stencil. The unknown solution and its first derivatives are carried as unknowns at selected grid points. This formulation allows us to incorporate the Dirichlet boundary conditions automatically and there is no need to define special formulas near the boundaries, as is the case with the standard discretizations of biharmonic equations. We exhibit the standard second-order, finite-difference approximation that requires 25 grid points. We also exhibit two compact formulations of the 3D biharmonic equations; these compact formulas are defined on a 27 point cubic grid. The fourth-order approximations are used to solve a set of test problems and produce high accuracy numerical solutions. The system of linear equations is solved using a variety of iterative methods. We employ multigrid and preconditioned Krylov iterative methods to solve the system of equations. Test results from two test problems are reported. In these experiments, the multigrid method gives excellent results. The multigrid preconditioning also gives good results using Krylov methods.     

A Projected Algebraic Multigrid Method for Linear Complementarity Problems

We present an algebraic version of an iterative multigrid method for obstacle problems, called projected algebraic multigrid (PAMG) here. We show that classical algebraic multigrid algorithms can easily be extended to deal with this kind of problem. This paves the way for efficient multigrid solution of obstacle problems with partial differential equations arising, for example, in financial engineering.     

Analysis of a multigrid preconditioner for Crouzeix–Raviart discretization of elliptic partial differential equation with jump coefficients

In this paper, we present a multigrid V‐cycle preconditioner for the linear system arising from piecewise linear nonconforming Crouzeix–Raviart discretization of second‐order elliptic problems with jump coefficients. The preconditioner uses standard conforming subspaces as coarse spaces. We showed that the convergence rates of the (multiplicative) two‐grid and multigrid V‐cycle algorithms will deteriorate rapidly because of large jumps in coefficient. However, the preconditioned systems have only a fixed number of small eigenvalues depending on the large jump in coefficient, and the effective condition numbers are independent of the coefficient and bounded logarithmically with respect to the mesh size. As a result, the two‐grid or multigrid preconditioned conjugate gradient algorithm converges nearly uniformly. We also comment on some major differences of the convergence theory between the nonconforming case and the standard conforming case. Numerical experiments support the theoretical results. Copyright © 2012 John Wiley & Sons, Ltd.     

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.     

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.     

Nonnested multigrid methods for linear problems

This article presents an application of nonnested and unstructured multigrid methods to linear elastic problems. A variational formulation for transfer operators and some multigrid strategies, including adaptive algorithms, are presented. Expressions for the performance evaluation of multigrid strategies and its comparison with direct and preconditioned conjugate gradient algorithms are also presented. A C++ implementation of the multigrid algorithms and the quadtree and octree data structures for transfer operators are discussed. Some two‐ and three‐dimensional elasticity examples are analyzed. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17:313–331, 2001     

Preconditioning indefinite discretization matrices

Summary The finite element discretization of many elliptic boundary value problems leads to linear systems with positive definite and symmetric coefficient matrices. Many efficient preconditioners are known for these systems. We show that these preconditioning matrices can also be used for the linear systems arising from boundary value problems which are potentially indefinite due to lower order terms in the partial differential equation. Our main tool is a careful algebraic analysis of the condition numbers and the spectra of perturbed matrices which are preconditioned by the same matrices as in the unperturbed case.     

A survey of multilevel preconditioned iterative methods

We survey multilevel iterative methods applied for solving large sparse systems with matrices, which depend on a level parameter, such as arise by the discretization of boundary value problems for partial differential equations when successive refinements of an initial discretization mesh is used to construct a sequence of nested difference or finite element meshes.We discuss various two-level (two-grid) preconditioning techniques, including some for nonsymmetric problems. The generalization of these techniques to the multilevel case is a nontrivial task. We emphasize several ways this can be done including classical multigrid methods and a recently proposed algebraic multilevel preconditioning method. Conditions for which the methods have an optimal order of computational complexity are presented.On leave from the Institute of Mathematics, and Center for Informatics and Computer Technology, Bulgarian Academy of Sciences, Sofia, Bulgaria. The research of the second author reported here was partly supported by the Stichting Mathematisch Centrum, Amsterdam.     

Reducing complexity of algebraic multigrid by aggregation

A typical approach to decrease computational costs and memory requirements of classical algebraic multigrid methods is to replace a conservative coarsening algorithm and short‐distance interpolation on a fixed number of fine levels by an aggressive coarsening with a long‐distance interpolation. Although the quality of the resulting algebraic multigrid grid preconditioner often deteriorates in terms of convergence rates and iteration counts of the preconditioned iterative solver, the overall performance can improve substantially. We investigate here, as an alternative, a possibility to replace the classical aggressive coarsening by aggregation, which is motivated by the fact that the convergence of aggregation methods can be independent of the problem size provided that the number of levels is fixed. The relative simplicity of aggregation can lead to improved solution and setup costs. The numerical experiments show the relevance of the proposed combination on both academic and benchmark problems in reservoir simulation from oil industry. Copyright © 2016 John Wiley & Sons, Ltd.     

Efficient parallel solution to large‐size sparse eigenproblems with block FSAI preconditioning

The choice of the preconditioner is a key factor to accelerate the convergence of eigensolvers for large‐size sparse eigenproblems. Although incomplete factorizations with partial fill‐in prove generally effective in sequential computations, the efficient preconditioning of parallel eigensolvers is still an open issue. The present paper describes the use of block factorized sparse approximate inverse (BFSAI) preconditioning for the parallel solution of large‐size symmetric positive definite eigenproblems with both a simultaneous Rayleigh quotient minimization and the Jacobi–Davidson algorithm. BFSAI coupled with a block diagonal incomplete decomposition proves a robust and efficient parallel preconditioner in a number of test cases arising from the finite element discretization of 3D fluid‐dynamical and mechanical engineering applications, outperforming FSAI even by a factor of 8 and exhibiting a satisfactory scalability. Copyright © 2011 John Wiley & Sons, Ltd.     

On block preconditioners for saddle point problems with singular or indefinite (1, 1) block

We discuss a class of preconditioning methods for the iterative solution of symmetric algebraic saddle point problems, where the (1, 1) block matrix may be indefinite or singular. Such problems may arise, e.g. from discrete approximations of certain partial differential equations, such as the Maxwell time harmonic equations. We prove that, under mild assumptions on the underlying problem, a class of block preconditioners (including block diagonal, triangular and symmetric indefinite preconditioners) can be chosen in a way which guarantees that the convergence rate of the preconditioned conjugate residuals method is independent of the discretization mesh parameter. We provide examples of such preconditioners that do not require additional scaling. Copyright © 2010 John Wiley & Sons, Ltd.     

An efficient hierarchical preconditioner for quadratic discretizations of finite element problems

Higher order finite element discretizations, although providing higher accuracy, are considered to be computationally expensive and of limited use for large‐scale problems. In this paper, we have developed an efficient iterative solver for solving large‐scale quadratic finite element problems. The proposed approach shares some common features with geometric multigrid methods but does not need structured grids to create the coarse problem. This leads to a robust method applicable to finite element problems discretized by unstructured meshes such as those from adaptive remeshing strategies. The method is based on specific properties of hierarchical quadratic bases. It can be combined with an algebraic multigrid (AMG) preconditioner or with other algebraic multilevel block factorizations. The algorithm can be accelerated by flexible Krylov subspace methods. We present some numerical results on the convection–diffusion and linear elasticity problems to illustrate the efficiency and the robustness of the presented algorithm. In these experiments, the performance of the proposed method is compared with that of an AMG preconditioner and other iterative solvers. Our approach requires less computing time and less memory storage. Copyright © 2010 John Wiley & Sons, Ltd.     

WEB-Spline–Based Multigrid Methods for the Stationary Stokes Problem

We discuss a multigrid technique in solving a large system of linear algebraic equations arising in the approximation of Stokes equations by a new strategy based on weighted extended B-spline (WEB-spline) methods. Three types of WEB-spline–based Stokes elements satisfying the inf-sup condition are considered. First for a linear-constant type of Stokes element, we give the detailed multigrid algorithm and its convergence proof. The convergence proof of the multigrid algorithm for a bubble-stabilized WEB-spline–based Stokes element is dealt with separately. Multigrid method in the case of bubble-condensed variational form is simplified using the techniques from the bubble-stabilized case.     

Smoothed aggregation multigrid for incompressible flows

We discuss the advantages of using algebraic multigrid based on smoothed aggregation for solving indefinite linear problems. The ingredients of smoothed aggregation are used to construct a black-box monolithic multigrid method with indefinite coarse problems. Although we discuss some techniques for enforcing the uniform inf-sup stability on all coarse levels, numerical experiments suggest that it is not strictly necessary. The proposed multigrid preconditioner shows robust behaviour for different time-step parameters and even for very elongated geometries, where other techniques based on h -independent preconditioners of the pressure Schur complement lose their efficiency. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Steepest descent preconditioning for nonlinear GMRES optimization

Steepest descent preconditioning is considered for the recently proposed nonlinear generalized minimal residual (N‐GMRES) optimization algorithm for unconstrained nonlinear optimization. Two steepest descent preconditioning variants are proposed. The first employs a line search, whereas the second employs a predefined small step. A simple global convergence proof is provided for the N‐GMRES optimization algorithm with the first steepest descent preconditioner (with line search), under mild standard conditions on the objective function and the line search processes. Steepest descent preconditioning for N‐GMRES optimization is also motivated by relating it to standard non‐preconditioned GMRES for linear systems in the case of a standard quadratic optimization problem with symmetric positive definite operator. Numerical tests on a variety of model problems show that the N‐GMRES optimization algorithm is able to very significantly accelerate convergence of stand‐alone steepest descent optimization. Moreover, performance of steepest‐descent preconditioned N‐GMRES is shown to be competitive with standard nonlinear conjugate gradient and limited‐memory Broyden–Fletcher–Goldfarb–Shanno methods for the model problems considered. These results serve to theoretically and numerically establish steepest‐descent preconditioned N‐GMRES as a general optimization method for unconstrained nonlinear optimization, with performance that appears promising compared with established techniques. In addition, it is argued that the real potential of the N‐GMRES optimization framework lies in the fact that it can make use of problem‐dependent nonlinear preconditioners that are more powerful than steepest descent (or, equivalently, N‐GMRES can be used as a simple wrapper around any other iterative optimization process to seek acceleration of that process), and this potential is illustrated with a further application example. Copyright © 2012 John Wiley & Sons, Ltd.     

Preconditioned Uzawa Algorithm for Elastic Contact Problems

After finite element discretization of the elastic contact problems with friction, we obtain a big sparse non–symmetric and nonlinear systems of equations, and in many cases ill–conditioned. Solving these systems by direct methods or classical iterative methods are non efficient and with bad convergence properties. One way to overcome these difficulties is to use the preconditioned Uzawa–type algorithms. On this paper we focus on the transformation of the generalized Signorini elastic contact problems into a saddle point problem of some augmented Lagrangian functional and give a preconditioning technique for Uzawa algorithm. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)