Adaptive algebraic smoothers

This paper will present a new method of adaptively constructing block iterative methods based on Local Sensitivity Analysis (LSA). The method can be used in the context of geometric and algebraic multigrid methods for constructing smoothers, and in the context of Krylov methods for constructing block preconditioners. It is suitable for both constant and variable coefficient problems. Furthermore, the method can be applied to systems arising from both scalar and coupled system partial differential equations (PDEs), as well as linear systems that do not arise from PDEs. The simplicity of the method will allow it to be easily incorporated into existing multigrid and Krylov solvers while providing a powerful tool for adaptively constructing methods tuned to a problem.     

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 block preconditioning technique for the streamfunction‐vorticity formulation of the Navier‐Stokes equations

Iterative methods of Krylov‐subspace type can be very effective solvers for matrix systems resulting from partial differential equations if appropriate preconditioning is employed. We describe and test block preconditioners based on a Schur complement approximation which uses a multigrid method for finite element approximations of the linearized incompressible Navier‐Stokes equations in streamfunction and vorticity formulation. By using a Picard iteration, we use this technology to solve fully nonlinear Navier‐Stokes problems. The solvers which result scale very well with problem parameters. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Multigrid for second‐order ADN elliptic systems

This paper theoretically examines a multigrid strategy for solving systems of elliptic partial differential equations (PDEs) introduced in the work of Lee. Unlike most multigrid solvers that are constructed directly from the whole system operator, this strategy builds the solver using a factorization of the system operator. This factorization is composed of an algebraic coupling term and a diagonal (decoupled) differential operator. Exploiting the factorization, this approach can produce decoupled systems on the coarse levels. The corresponding coarse‐grid operators are in fact the Galerkin variational coarsening of the diagonal differential operator. Thus, rather than performing delicate coarse‐grid selection and interpolation weight procedures on the original strongly coupled system as often done, these procedures are isolated to the diagonal differential operator. To establish the theoretical results, however, we assume that these systems of PDEs are elliptic in the Agmon–Douglis–Nirenberg (ADN) sense and apply the factorization and multigrid only to the principal part of the system of PDEs. Two‐grid error bounds are established for the iteration applied to the complete system of PDEs. Numerical results are presented to illustrate the effectiveness of this strategy and to expose factors that affect the convergence of the methods derived from this strategy.     

Algebraic multigrid preconditioning of the Hessian in optimization constrained by a partial differential equation

We construct an algebraic multigrid (AMG) based preconditioner for the reduced Hessian of a linear‐quadratic optimization problem constrained by an elliptic partial differential equation. While the preconditioner generalizes a geometric multigrid preconditioner introduced in earlier works, its construction relies entirely on a standard AMG infrastructure built for solving the forward elliptic equation, thus allowing for it to be implemented using a variety of AMG methods and standard packages. Our analysis establishes a clear connection between the quality of the preconditioner and the AMG method used. The proposed strategy has a broad and robust applicability to problems with unstructured grids, complex geometry, and varying coefficients. The method is implemented using the Hypre package and several numerical examples are presented.     

Newton-Multigrid for Biological Reaction-Diffusion Problems with Random Coefficients

An algebraic Newton-multigrid method is proposed in order to efficiently solve systems of nonlinear reaction-diffusion problems with stochastic coefficients. These problems model the conversion of starch into sugars in growing apples. The stochastic system is first converted into a large coupled system of deterministic equations by applying a stochastic Galerkin finite element discretization. This method leads to high-order accurate stochastic solutions. A stable and high-order time discretization is obtained by applying a fully implicit Runge-Kutta method. After Newton linearization, a point-based algebraic multigrid solution method is applied. In order to decrease the computational cost, alternative multigrid preconditioners are presented. Numerical results demonstrate the convergence properties, robustness and efficiency of the proposed multigrid methods.     

An order optimal solver for the discretized bidomain equations

The electrical activity in the heart is governed by the bidomain equations. In this paper, we analyse an order optimal method for the algebraic equations arising from the discretization of this model. Our scheme is defined in terms of block Jacobi or block symmetric Gauss–Seidel preconditioners. Furthermore, each block in these methods is based on standard preconditioners for scalar elliptic or parabolic partial differential equations (PDEs). Such preconditioners can be realized in terms of multigrid or domain decomposition schemes, and are thus readily available by applying ‘off‐the‐shelves’ software. Finally, our theoretical findings are illuminated by a series of numerical experiments. Copyright © 2006 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.     

Efficient iterative solvers for time-harmonic Maxwell equations using domain decomposition and algebraic multigrid

Paper presents a set of parallel iterative solvers and preconditioners for the efficient solution of systems of linear equations arising in the high order finite-element approximations of boundary value problems for 3-D time-harmonic Maxwell equations on unstructured tetrahedral grids. Balancing geometric domain decomposition techniques combined with algebraic multigrid approach and coarse-grid correction using hierarchic basis functions are exploited to achieve high performance of the solvers and small memory load on the supercomputers with shared and distributed memory. Testing results for model and real-life problems show the efficiency and scalability of the presented algorithms.     

Fast Fourier Transform Solvers and Preconditioners for Quadratic Spline Collocation

Quadratic Spline Collocation (QSC) methods of optimal order of convergence have been recently developed for the solution of elliptic Partial Differential Equations (PDEs). In this paper, linear solvers based on Fast Fourier Transforms (FFT)are developed for the solution of the QSC equations. The complexity of the FFT solvers is O(N ² log N), where N is the gridsize in one dimension. These direct solvers can handle PDEs with coefficients in one variable or constant, and Dirichlet, Neumann, alternating Dirichlet-Neumann or periodic boundary conditions, along at least one direction of a rectangular domain. General variable coefficient PDEs are handled by preconditioned iterative solvers. The preconditioner is the QSC matrix arising from a constant coefficient PDE. The convergence analysis of the preconditioner is presented. It is shown that, under certain conditions, the convergence rate is independent of the gridsize. The preconditioner is solved by FFT techniques, and integrated with one-step or acceleration methods, giving rise to asymptotically almost optimal linear solvers, with complexity O(N ² log N). Numerical experiments verify the effectiveness of the solvers and preconditioners, even on problems more general than the analysis assumes. The development and analysis of FFT solvers and preconditioners is extended to QSC equations corresponding to systems of elliptic PDEs.     

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.     

Circulant-block preconditioners for solving ordinary differential equations

Boundary value methods for solving ordinary differential equations require the solution of non-symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A circulant-block preconditioner is proposed to speed up the convergence rate of the GMRES method. Theoretical and practical arguments are given to show that this preconditioner is more efficient than some other circulant-type preconditioners in some cases. A class of waveform relaxation methods is also proposed to solve the linear systems.     

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.     

Hermite collocation solution of partial differential equations via preconditioned Krylov methods

We are concerned with the numerical solution of partial differential equations (PDEs) in two spatial dimensions discretized via Hermite collocation. To efficiently solve the resulting systems of linear algebraic equations, we choose a Krylov subspace method. We implement two such methods: Bi‐CGSTAB [1] and GMRES [2]. In addition, we utilize two different preconditioners: one based on the Gauss–Seidel method with a block red‐black ordering (RBGS); the other based upon a block incomplete LU factorization (ILU). Our results suggest that, at least in the context of Hermite collocation, the RBGS preconditioner is superior to the ILU preconditioner and that the Bi‐CGSTAB method is superior to GMRES. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17:120–136, 2001     

Schwarz preconditioned CG algorithm for the mortar finite element

We propose a simple and effective hybrid (multiplicative) Schwarz precondtioner for solving systems of algebraic equations resulting from the mortar finite element discretization of second order elliptic problems on nonmatching meshes. The preconditioner is embedded in a variant of the classical preconditioned conjugate gradient (PCG) for an effective implementation reducing the cost of computing the matrix-vector multiplication in each iteration of the PCG. In fact, it serves as a framework for effective implementation of a class of hybrid Schwarz preconditioners. The preconditioners of this class are based on solving a sequence of non-overlapping local subproblems exactly, and the coarse problems either exactly or inexactly (approximately). The classical PCG algorithm is reformulated in order to make reuse of the results of matrix-vector multiplications that are already available from the preconditioning step resulting in an algorithm which is cost effective. An analysis of the proposed preconditioner, with numerical results, showing scalability with respect to the number of subdomains, and a convergence which is independent of the jumps of the coefficients are given.     

An Improvement of Multigrid Methods Using Multiple Grids on Each Layer for Parallel Computing

Multigrid methods are widely used and well studied for linear solvers and preconditioners of Krylov subspace methods. The multigrid method is one of the most powerful approaches for solving large scale linear systems;however, it may show low parallel efficiency on coarse grids. There are several kinds of research on this issue. In this paper, we intend to overcome this difficulty by proposing a novel multigrid algorithm that has multiple grids on each layer.Numerical results indicate that the proposed method shows a better convergence rate compared with the existing multigrid method.     

Strang‐type preconditioners applied to ordinary and neutral differential‐algebraic equations

This paper deals with boundary‐value methods (BVMs) for ordinary and neutral differential‐algebraic equations. Different from what has been done in Lei and Jin (Lecture Notes in Computer Science, vol. 1988. Springer: Berlin, 2001; 505–512), here, we directly use BVMs to discretize the equations. The discretization will lead to a nonsymmetric large‐sparse linear system, which can be solved by the GMRES method. In order to accelerate the convergence rate of GMRES method, two Strang‐type block‐circulant preconditioners are suggested: one is for ordinary differential‐algebraic equations (ODAEs), and the other is for neutral differential‐algebraic equations (NDAEs). Under some suitable conditions, it is shown that the preconditioners are invertible, the spectra of the preconditioned systems are clustered, and the solution of iteration converges very rapidly. The numerical experiments further illustrate the effectiveness of the methods. Copyright © 2011 John Wiley & Sons, Ltd.     

Respectively scaled HSS iteration methods for solving discretized spatial fractional diffusion equations

For the discrete linear systems resulted from the discretization of the one‐dimensional anisotropic spatial fractional diffusion equations of variable coefficients with the shifted finite‐difference formulas of the Grünwald–Letnikov type, we propose a class of respectively scaled Hermitian and skew‐Hermitian splitting iteration method and establish its asymptotic convergence theory. The corresponding induced matrix splitting preconditioner, through further replacements of the involved Toeplitz matrices with certain circulant matrices, leads to an economic variant that can be executed by fast Fourier transforms. Both theoretical analysis and numerical implementations show that this fast respectively scaled Hermitian and skew‐Hermitian splitting preconditioner can significantly improve the computational efficiency of the Krylov subspace iteration methods employed as effective linear solvers for the target discrete linear systems.     

Robust Multiscale Iterative Solvers for Nonlinear Flows in Highly Heterogeneous Media

In this paper, we study robust iterative solvers for finite element systems resulting in approximation of steady-state Richards' equation in porous media with highly heterogeneous conductivity fields. It is known that in such cases the contrast, ratio between the highest and lowest values of the conductivity, can adversely affect the performance of the preconditioners and, consequently, a design of robust preconditioners is important for many practical applications. The proposed iterative solvers consist of two kinds of iterations, outer and inner iterations. Outer iterations are designed to handle nonlinearities by linearizing the equation around the previous solution state. As a result of the linearization, a large-scale linear system needs to be solved. This linear system is solved iteratively (called inner iterations), and since it can have large variations in the coefficients, a robust preconditioner is needed. First, we show that under some assumptions the number of outer iterations is independent of the contrast. Second, based on the recently developed iterative methods, we construct a class of preconditioners that yields convergence rate that is independent of the contrast. Thus, the proposed iterative solvers are optimal with respect to the large variation in the physical parameters. Since the same preconditioner can be reused in every outer iteration, this provides an additional computational savings in the overall solution process. Numerical tests are presented to confirm the theoretical results.     

Preconditioning spectral element schemes for definite and indefinite problems

Spectral element schemes for the solution of elliptic boundary value problems are considered. Preconditioning methods based on finite difference and finite element schemes are implemented. Numerical experiments show that inverting the preconditioner by a single multigrid iteration is most efficient and that the finite difference preconditioner is superior to the finite element one for both definite and indefinite problems. A multigrid preconditioner is also derived from the finite difference preconditioner and is found suitable for the CGS acceleration method. It is pointed out that, for the finite difference and finite element preconditioners, CGS does not always converge to the accurate algebraic solution. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 535–543, 1999