A geometric theory for preconditioned inverse iteration I: Extrema of the Rayleigh quotient

The discretization of eigenvalue problems for partial differential operators is a major source of matrix eigenvalue problems having very large dimensions, but only some of the smallest eigenvalues together with the eigenvectors are to be determined. Preconditioned inverse iteration (a “matrix-free” method) derives from the well-known inverse iteration procedure in such a way that the associated system of linear equations is solved approximately by using a (multigrid) preconditioner. A new convergence analysis for preconditioned inverse iteration is presented. The preconditioner is assumed to satisfy some bound for the spectral radius of the error propagation matrix resulting in a simple geometric setup. In this first part the case of poorest convergence depending on the choice of the preconditioner is analyzed. In the second part the dependence on all initial vectors having a fixed Rayleigh quotient is considered. The given theory provides sharp convergence estimates for the eigenvalue approximations showing that multigrid eigenvalue/vector computations can be done with comparable efficiency as known from multigrid methods for boundary value problems.     

Two-step modulus-based matrix splitting iteration method for linear complementarity problems

Bai has recently presented a modulus-based matrix splitting iteration method, which is a powerful alternative for solving the large sparse linear complementarity problems. In this paper, we further present a two-step modulus-based matrix splitting iteration method, which consists of a forward and a backward sweep. Its convergence theory is proved when the system matrix is an H ₊-matrix. Moreover, for the two-step modulus-based relaxation iteration methods, more exact convergence domains are obtained without restriction on the Jacobi matrix associated with the system matrix, which improve the existing convergence theory. Numerical results show that the two-step modulus-based relaxation iteration methods are superior to the modulus-based relaxation iteration methods for solving the large sparse linear complementarity problems.     

An efficient algebraic multigrid method for quadratic discretizations of linear elasticity problems on some typical anisotropic meshes in three dimensions

The quality of the mesh used in the finite element discretizations will affect the efficiency of solving the discreted linear systems. The usual algebraic solvers except multigrid method do not consider the effect of the grid geometry and the mesh quality on their convergence rates. In this paper, we consider the hierarchical quadratic discretizations of three‐dimensional linear elasticity problems on some anisotropic hexahedral meshes and present a new two‐level method, which is weakly independent of the size of the resulting problems by using a special local block Gauss–Seidel smoother, that is LBGS_v iteration when used for vertex nodes or LBGS_m iteration for midside nodes. Moreover, we obtain the efficient algebraic multigrid (AMG) methods by applying DAMG (AMG based on distance matrix) or DAMG‐PCG (PCG with DAMG as a preconditioner) to the solution of the coarse level equation. The resulting AMG methods are then applied to a practical example as a long beam. The numerical results verify the efficiency and robustness of the proposed AMG algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

A posteriori error estimation for elliptic eigenproblems

An a posteriori error estimator is presented for a subspace implementation of preconditioned inverse iteration, which derives from the well‐known inverse iteration in such a way that the associated system of linear equations is solved approximately by using a preconditioner. The error estimator is integrated in an adaptive multigrid algorithm to compute approximations of a modest number of the smallest eigenvalues together with the eigenfunctions of an elliptic differential operator. Error estimation is applied both within the actual finite element space (in order to estimate the iteration error) as well as in its hierarchical refinement of higher‐order elements (to estimate the discretization error) which gives rise to a balanced reduction of the iteration error and of the discretization error in the adaptive multigrid algorithm. Copyright © 2002 John Wiley & Sons, Ltd.     

An optimal order multigrid method for biharmonic,C 1 finite element equations

Summary In this paper, we study a special multigrid method for solving large linear systems which arise from discretizing biharmonic problems by the Hsieh-Clough-Tocher,C ¹ macro finite elements or several otherC ¹ finite elements. Since the multipleC ¹ finite element spaces considered are not nested, the nodal interpolation operator is used to transfer functions between consecutive levels in the multigrid method. This method converges with the optimal computational order.     

Modulus‐based multigrid methods for linear complementarity problems

By employing modulus‐based matrix splitting iteration methods as smoothers, we establish modulus‐based multigrid methods for solving large sparse linear complementarity problems. The local Fourier analysis is used to quantitatively predict the asymptotic convergence factor of this class of multigrid methods. Numerical results indicate that the modulus‐based multigrid methods of the W‐cycle can achieve optimality in terms of both convergence factor and computing time, and their asymptotic convergence factors can be predicted perfectly by the local Fourier analysis of the corresponding modulus‐based two‐grid methods.     

On preconditioned MHSS iteration methods for complex symmetric linear systems

We propose a preconditioned variant of the modified HSS (MHSS) iteration method for solving a class of complex symmetric systems of linear equations. Under suitable conditions, we prove the convergence of the preconditioned MHSS (PMHSS) iteration method and discuss the spectral properties of the PMHSS-preconditioned matrix. Numerical implementations show that the resulting PMHSS preconditioner leads to fast convergence when it is used to precondition Krylov subspace iteration methods such as GMRES and its restarted variants. In particular, both the stationary PMHSS iteration and PMHSS-preconditioned GMRES show meshsize-independent and parameter-insensitive convergence behavior for the tested numerical examples.     

A full multigrid method for nonlinear eigenvalue problems

We introduce a type of full multigrid method for the nonlinear eigenvalue problem. The main idea is to transform the solution of the nonlinear eigenvalue problem into a series of solutions of the corresponding linear boundary value problems on the sequence of finite element spaces and nonlinear eigenvalue problems on the coarsest finite element space. The linearized boundary value problems are solved by some multigrid iterations. Besides the multigrid iteration, all other efficient iteration methods for solving boundary value problems can serve as the linear problem solver. We prove that the computational work of this new scheme is truly optimal, the same as solving the linear corresponding boundary value problem. In this case, this type of iteration scheme certainly improves the overfull efficiency of solving nonlinear eigenvalue problems. Some numerical experiments are presented to validate the efficiency of the new method.     

On HSS-based iteration methods for weakly nonlinear systems

Based on separable property of the linear and the nonlinear terms and on the Hermitian and skew-Hermitian splitting of the coefficient matrix, we present the Picard-HSS and the nonlinear HSS-like iteration methods for solving a class of large scale systems of weakly nonlinear equations. The advantage of these methods over the Newton and the Newton-HSS iteration methods is that they do not require explicit construction and accurate computation of the Jacobian matrix, and only need to solve linear sub-systems of constant coefficient matrices. Hence, computational workloads and computer memory may be saved in actual implementations. Under suitable conditions, we establish local convergence theorems for both Picard-HSS and nonlinear HSS-like iteration methods. Numerical implementations show that both Picard-HSS and nonlinear HSS-like iteration methods are feasible, effective, and robust nonlinear solvers for this class of large scale systems of weakly nonlinear equations.     

Comparison of multigrid algorithms for high‐order continuous finite element discretizations

We present a comparison of different multigrid approaches for the solution of systems arising from high‐order continuous finite element discretizations of elliptic partial differential equations on complex geometries. We consider the pointwise Jacobi, the Chebyshev‐accelerated Jacobi, and the symmetric successive over‐relaxation smoothers, as well as elementwise block Jacobi smoothing. Three approaches for the multigrid hierarchy are compared: (1) high‐order h‐multigrid, which uses high‐order interpolation and restriction between geometrically coarsened meshes; (2) p‐multigrid, in which the polynomial order is reduced while the mesh remains unchanged, and the interpolation and restriction incorporate the different‐order basis functions; and (3) a first‐order approximation multigrid preconditioner constructed using the nodes of the high‐order discretization. This latter approach is often combined with algebraic multigrid for the low‐order operator and is attractive for high‐order discretizations on unstructured meshes, where geometric coarsening is difficult. Based on a simple performance model, we compare the computational cost of the different approaches. Using scalar test problems in two and three dimensions with constant and varying coefficients, we compare the performance of the different multigrid approaches for polynomial orders up to 16. Overall, both h‐multigrid and p‐multigrid work well; the first‐order approximation is less efficient. For constant coefficients, all smoothers work well. For variable coefficients, Chebyshev and symmetric successive over‐relaxation smoothing outperform Jacobi smoothing. While all of the tested methods converge in a mesh‐independent number of iterations, none of them behaves completely independent of the polynomial order. When multigrid is used as a preconditioner in a Krylov method, the iteration number decreases significantly compared with using multigrid as a solver. Copyright © 2015 John Wiley & Sons, Ltd.     

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     

Convergent nonnegative matrices and iterative methods for consistent linear systems

Summary In this paper we study linear stationary iterative methods with nonnegative iteration matrices for solving singular and consistent systems of linear equationsAx=b. The iteration matrices for the schemes are obtained via regular and weak regular splittings of the coefficients matrixA. In certain cases when only some necessary, but not sufficient, conditions for the convergence of the iterations schemes exist, we consider a transformation on the iteration matrices and obtain new iterative schemes which ensure convergence to a solution toAx=b. This transformation is parameter-dependent, and in the case where all the eigenvalues of the iteration matrix are real, we show how to choose this parameter so that the asymptotic convergence rate of the new schemes is optimal. Finally, some applications to the problem of computing the stationary distribution vector for a finite homogeneous ergodic Markov chain are discussed.Research sponsored in part by US Army Research Office     

Algebraic interface‐based coarsening AMG preconditioner for multi‐scale sparse matrices with applications to radiation hydrodynamics computation

Coarsening is a crucial component of algebraic multigrid (AMG) methods for iteratively solving sparse linear systems arising from scientific and engineering applications. Its application largely determines the complexity of the AMG iteration operator. Usually, high operator complexities lead to fast convergence of the AMG method; however, they require additional memory and as such do not scale as well in parallel computation. In contrast, although low operator complexities improve parallel scalability, they often lead to deterioration in convergence. This study introduces a new type of coarsening strategy called algebraic interface‐based coarsening that yields a better balance between convergence and complexity for a class of multi‐scale sparse matrices. Numerical results for various model‐type problems and a radiation hydrodynamics practical application are provided to show the effectiveness of the proposed AMG solver.     

A preconditioned general modulus-based matrix splitting iteration method for linear complementarity problems of <Emphasis Type="Italic">H</Emphasis>-matrices

In this paper, we propose a preconditioned general modulus-based matrix splitting iteration method for solving modulus equations arising from linear complementarity problems. Its convergence theory is proved when the system matrix is an H₊-matrix, from which some new convergence conditions can be derived for the (general) modulus-based matrix splitting iteration methods. Numerical results further show that the proposed methods are superior to the existing methods.     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.     

A full multigrid method for semilinear elliptic equation

A full multigrid finite element method is proposed for semilinear elliptic equations. The main idea is to transform the solution of the semilinear problem into a series of solutions of the corresponding linear boundary value problems on the sequence of finite element spaces and semilinear problems on a very low dimensional space. The linearized boundary value problems are solved by some multigrid iterations. Besides the multigrid iteration, all other efficient numerical methods can also serve as the linear solver for solving boundary value problems. The optimality of the computational work is also proved. Compared with the existing multigrid methods which need the bounded second order derivatives of the nonlinear term, the proposed method only needs the Lipschitz continuation in some sense of the nonlinear term.     

Numerical simulation of fluid-structure interaction problems on hybrid meshes with algebraic multigrid methods

Fluid-structure interaction problems arise in many fields of application such as flows around elastic structures and blood flow in arteries. The method presented in this paper for solving such a problem is based on a reduction to an equation at the interface, involving the so-called Steklov-Poincaré operators. This interface equation is solved by a Newton iteration, for which directional derivatives involving shape derivatives with respect to the interface perturbation have to be evaluated appropriately. One step of the Newton iteration requires the solution of several decoupled linear sub-problems in the structure and the fluid domains. These sub-problems are spatially discretized by a finite element method on hybrid meshes. For the time discretization, implicit first-order methods are used for both sub-problems. The discretized equations are solved by algebraic multigrid methods.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

A multigrid discrete‐ordinates solution for isotropic transport equation

We propose a robust multigrid solver for the isotropic transport equation in three space dimensions. Discrete‐ordinates and Galerkin method are used for angle and space discretizations, respectively. The fully discrete problem is formulated as a compact linear system of algebraic equations with a dense iterate matrix. Using a hierarchy of nested meshes our multigrid algorithm employes the Atkinson‐Brakhage approximate inverse as a smoother while a Krylov subspace method is used to solve the coarse problem. Numerical results and comparisons are shown for a transport problem with thermal source. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)