MultiGrid Preconditioners for Mixed Finite Element Methods of the Vector Laplacian

Due to the indefiniteness and poor spectral properties, the discretized linear algebraic system of the vector Laplacian by mixed finite element methods is hard to solve. A block diagonal preconditioner has been developed and shown to be an effective preconditioner by Arnold et al. (Acta Numer 15:1–155, 2006). The purpose of this paper is to propose alternative and effective block diagonal and approximate block factorization preconditioners for solving these saddle point systems. A variable V-cycle multigrid method with the standard point-wise Gauss–Seidel smoother is proved to be a good preconditioner for the discrete vector Laplacian operator. The major benefit of our approach is that the point-wise Gauss–Seidel smoother is more algebraic and can be easily implemented as a black-box smoother. This multigrid solver will be further used to build preconditioners for the saddle point systems of the vector Laplacian. Furthermore it is shown that Maxwell’s equations with the divergent free constraint can be decoupled into one vector Laplacian and one scalar Laplacian equation.     

Application of single-level,pointwise algebraic,and smoothed aggregation multigrid methods to direct numerical simulations of incompressible turbulent flows

Single- and multi-level iterative methods for sparse linear systems are applied to unsteady flow simulations via implementation into a direct numerical simulation solver for incompressible turbulent flows on unstructured meshes. The performance of these solution methods, implemented in the well-established SAMG and ML packages, are quantified in terms of computational speed and memory consumption, with a direct sparse LU solver (SuperLU) used as a reference. The classical test case of unsteady flow over a circular cylinder at low Reynolds numbers is considered, employing a series of increasingly fine anisotropic meshes. As expected, the memory consumption increases dramatically with the considered problem size for the direct solver. Surprisingly, however, the computation times remain reasonable. The speed and memory usage of pointwise algebraic and smoothed aggregation multigrid solvers are found to exhibit near-linear scaling. As an alternative to multi-level solvers, a single-level ILUT-preconditioned GMRES solver with low drop tolerance is also considered. This solver is found to perform sufficiently well only on small meshes. Even then, it is outperformed by pointwise algebraic multigrid on all counts. Finally, the effectiveness of pointwise algebraic multigrid is illustrated by considering a large three-dimensional direct numerical simulation case using a novel parallelization approach on a large distributed memory computing cluster.     

An overview and generalization of implicit Navier–Stokes algorithms and approximate factorization

A theme of linearization and approximate factorization provides the context for a retrospective overview of the development and evolution of implicit numerical methods for the compressible and incompressible Euler and Navier–Stokes algorithms. This topic was chosen for this special volume commemorating the recent retirements of R.M. Beam and R.F. Warming. A generalized treatment of approximate factorization schemes is given, based on an operator notation for the spatial approximation. The generalization focuses on the implicit structure of Euler and Navier–Stokes algorithms as nonlinear systems of partial differential equations, with details of the spatial approximation left to operator definitions. This provides a unified context for discussing noniterative and iterative time-linearized schemes, and Newton iteration for unsteady nonlinear schemes. The factorizations include alternating direction implicit, LU and line relaxation schemes with either upwind or centered spatial approximations for both compressible and incompressible flows. The noniterative schemes are best suited for steady flows, while the iterative schemes are well suited for either steady or unsteady flows. This generalization serves to unify a large number of schemes developed over the past 30 years.     

Parallel nonlinear preconditioners on multicore architectures

Parallel nonlinear preconditioners, for solving mildly nonlinear systems, are proposed. These algorithms are based on both the Fletcher–Reeves version of the nonlinear conjugate gradient method and a polynomial preconditioner type based on block two-stage methods. The behavior of these algorithms is analyzed when incomplete LU factorizations are used in order to obtain the inner splittings of the block two-stage method. As our illustrative example we have considered a nonlinear elliptic partial differential equation, known as the Bratu problem. The reported experiments show the performance of the algorithms designed in this work on two multicore architectures.     

Adaptive multigrid for finite element computations in plasticity

The solution of the system of equilibrium equations is the most time-consuming part in large-scale finite element computations of plasticity problems. The development of efficient solution methods are therefore of utmost importance to the field of computational plasticity. Traditionally, direct solvers have most frequently been used. However, recent developments of iterative solvers and preconditioners may impose a change. In particular, preconditioning by the multigrid technique is especially favorable in FE applications.The multigrid preconditioner uses a number of nested grid levels to improve the convergence of the iterative solver. Prolongation of fine-grid residual forces is done to coarser grids and computed corrections are interpolated to the fine grid such that the fine-grid solution successively is improved. By this technique, large 3D problems, invincible for solvers based on direct methods, can be solved in acceptable time at low memory requirements. By means of a posteriori error estimates the computational grid could successively be refined (adapted) until the solution fulfils a predefined accuracy level. In contrast to procedures where the preceding grids are erased, the previously generated grids are used in the multigrid algorithm to speed up the solution process.The paper presents results using the adaptive multigrid procedure to plasticity problems. In particular, different error indicators are tested.     

On the performance of SPAI and ADI-like preconditioners for core collapse supernova simulations in one spatial dimension

The simulation of core collapse supernovæ calls for the time accurate solution of the (Euler) equations for inviscid hydrodynamics coupled with the equations for neutrino transport. The time evolution is carried out by evolving the Euler equations explicitly and the neutrino transport equations implicitly. Neutrino transport is modeled by the multi-group Boltzmann transport (MGBT) and the multi-group flux limited diffusion (MGFLD) equations. An implicit time stepping scheme for the MGBT and MGFLD equations yields Jacobian systems that necessitate scaling and preconditioning. Two types of preconditioners, namely, a sparse approximate inverse (SPAI) preconditioner and a preconditioner based on the alternating direction implicit iteration (ADI-like) have been found to be effective for the MGFLD and MGBT formulations. This paper compares these two preconditioners. The ADI-like preconditioner performs well with both MGBT and MGFLD systems. For the MGBT system tested, the SPAI preconditioner did not give competitive results. However, since the MGBT system in our experiments had a high condition number before scaling and since we used a sequential platform, care must be taken in evaluating these results.     

Parallel simulation of anisotropic diffusion with human brain DT-MRI Data

We conduct simulations for the 3D unsteady state anisotropic diffusion process with DT-MRI data in the human brain by discretizing the governing diffusion equation on Cartesian grid and adopting a high performance differential-algebraic equation (DAE) solver, the parallel version of implicit differential-algebraic (IDA) solver, to tackle the resulting large scale system of DAEs. Parallel preconditioning techniques including sparse approximate inverse and banded-block-diagonal preconditioners are used with the GMRES method to accelerate the convergence rate of the iterative solution. We then investigate and compare the efficiency and effectiveness of the two parallel preconditioners. The experimental results of the diffusion simulations on a parallel supercomputer show that the sparse approximate inverse preconditioning strategy, which is robust and efficient with good scalability, gives a much better overall performance than the banded-block-diagonal preconditioner.     

A numerical investigation on the interplay amongst geometry, meshes, and linear algebra in the finite element solution of elliptic PDEs

In this paper, we study the effect of the choice of mesh quality metric, preconditioner, and sparse linear solver on the numerical solution of elliptic partial differential equations (PDEs). We smooth meshes on several geometric domains using various quality metrics and solve the associated elliptic PDEs using the finite element method. The resulting linear systems are solved using various combinations of preconditioners and sparse linear solvers. We use the inverse mean ratio and radius ratio metrics in addition to conditioning-based scale-invariant and interpolation-based size-and-shape metrics. We employ the Jacobi, SSOR, incomplete LU, and algebraic multigrid preconditioners and the conjugate gradient, minimum residual, generalized minimum residual, and bi-conjugate gradient stabilized solvers. We focus on determining the most efficient quality metric, preconditioner, and linear solver combination for the numerical solution of various elliptic PDEs with isotropic coefficients. We also investigate the effect of vertex perturbation and the effect of increasing the problem size on the number of iterations required to converge and on the solver time. In this paper, we consider Poisson’s equation, general second-order elliptic PDEs, and linear elasticity problems.     

Stability and spectral properties of some incomplete block factorizations

Incomplete block factorizations are often used to derive preconditioners for the Preconditioned Conjugate Gradient (PCG) method. The stability properties of some incomplete block factorizations are investigated for a class of symmetric, nonsingular M-matrices. The error analysis is carried out for a simpler case. The spectral properties are discussed in order to derive a preconditioner with better properties.     

A parallel fully coupled implicit domain decomposition method for numerical simulation of microfluidic mixing in 3D

A parallel fully coupled implicit fluid solver based on a Newton–Krylov–Schwarz algorithm is developed on top of the Portable, Extensible Toolkit for Scientific computation for the simulation of microfluidic mixing described by the three-dimensional unsteady incompressible Navier–Stokes equations. The popularly used fractional step method, originally designed for high Reynolds number flows, requires some modification of the inviscid-type pressure boundary condition in order to reduce the divergence error near the wall. On the other hand, the fully coupled approach works well without any special treatment of the boundary condition for low Reynolds number microchannel flows. A key component of the algorithm is an additive Schwarz preconditioner, which is used to accelerate the convergence of a linear Krylov-type solver for the saddle-point-type Jacobian systems. As a test case, we carefully study a three-dimensional passive serpentine micromixer and report the parallel performance of the algorithm obtained on a parallel machine with more than one hundred processors.     

Robust multigrid preconditioners for cell-centered finite volume discretization of the high-contrast diffusion equation

We study a conservative 5-point cell-centered finite volume discretization of the high-contrast diffusion equation. We aim to construct preconditioners that are robust with respect to the magnitude of the coefficient contrast and the mesh size simultaneously. For that, we prove and numerically demonstrate the robustness of the preconditioner proposed by Aksoylu et al. (Comput Vis Sci 11:319–331, 2008) by extending the devised singular perturbation analysis from linear finite element discretization to the above discretization. The singular perturbation analysis is more involved than that of finite element case because all the subblocks in the discretization matrix depend on the diffusion coefficient. However, as the diffusion coefficient approaches infinity, that dependence is eliminated. This allows the same preconditioner to be utilized due to similar limiting behaviours of the submatrices; leading to a narrowing family of preconditioners that can be used for different discretizations. Therefore, we have accomplished a desirable preconditioner design goal. We compare our numerical results to standard cell-centered multigrid implementations and observe that performance of our preconditioner is independent of the utilized smoothers and prolongation operators. As a side result, we also prove a fundamental qualitative property of solution of the high-contrast diffusion equation. Namely, the solution over the highly-diffusive island becomes constant asymptotically. Integration of this qualitative understanding of the underlying PDE to our preconditioner is the main reason behind its superior performance. Diagonal scaling is probably the most basic preconditioner for high-contrast coefficients. Extending the matrix entry based spectral analysis introduced by Graham and Hagger, we rigorously show that the number of small eigenvalues of the diagonally scaled matrix depends on the number of isolated islands comprising the highly-diffusive region. This indicates that diagonal scaling creates a significant clustering of the spectrum, a favorable property for faster convergence of Krylov subspace solvers.     

A class of parallel two-level nonlinear Schwarz preconditioned inexact Newton algorithms

We propose and test a new class of two-level nonlinear additive Schwarz preconditioned inexact Newton algorithms (ASPIN). The two-level ASPIN combines a local nonlinear additive Schwarz preconditioner and a global linear coarse preconditioner. This approach is more attractive than the two-level method introduced in [X.-C. Cai, D.E. Keyes, L. Marcinkowski, Nonlinear additive Schwarz preconditioners and applications in computational fluid dynamics, Int. J. Numer. Methods Fluids, 40 (2002), 1463-1470], which is nonlinear on both levels. Since the coarse part of the global function evaluation requires only the solution of a linear coarse system rather than a nonlinear coarse system derived from the discretization of original partial differential equations, the overall computational cost is reduced considerably. Our parallel numerical results based on an incompressible lid-driven flow problem show that the new two-level ASPIN is quite scalable with respect to the number of processors and the fine mesh size when the coarse mesh size is fine enough, and in addition the convergence is not sensitive to the Reynolds numbers.     

Convergence Acceleration for Hyperbolic Systems Using Semicirculant Approximations

The iterative solution of systems of equations arising from systems of hyperbolic, time-independent partial differential equations (PDEs) is studied. The PDEs are discretized using a finite volume or finite difference approximation on a structured grid. A convergence acceleration technique where a semicirculant approximation of the spatial difference operator is employed as preconditioner is considered. The spectrum of the preconditioned coefficient matrix is analyzed for a model problem. It is shown that, asymptotically, the time step for the forward Euler method could be chosen as a constant, which is independent of the number of grid points and the artificial viscosity parameter. By linearizing the Euler equations around an approximate solution, a system of linear PDEs with variable coefficients is formed. When utilizing the semicirculant (SC) preconditioner for this problem, which has properties very similar to the full nonlinear equations, numerical experiments show that the favorable convergence properties hold also here. We compare the results for the SC method to those of a multigrid (MG) scheme. The number of iterations and the arithmetic complexities are considered, and it is clear that the SC method is more efficient for the problems studied. Also, the MG scheme is sensitive to the amount of artificial dissipation added, while the SC method is not.     

Efficient nonlinear solvers for Laplace–Beltrami smoothing of three-dimensional unstructured grids

The Laplace–Beltrami system of nonlinear, elliptic, partial differential equations has utility in the generation of computational grids on complex and highly curved geometry. Discretization of this system using the finite-element method accommodates unstructured grids, but generates a large, sparse, ill-conditioned system of nonlinear discrete equations. The use of the Laplace–Beltrami approach, particularly in large-scale applications, has been limited by the scalability and efficiency of solvers. This paper addresses this limitation by developing two nonlinear solvers based on the Jacobian-Free Newton–Krylov (JFNK) methodology. A key feature of these methods is that the Jacobian is not formed explicitly for use by the underlying linear solver. Iterative linear solvers such as the Generalized Minimal RESidual (GMRES) method do not technically require the stand-alone Jacobian; instead its action on a vector is approximated through two nonlinear function evaluations. The preconditioning required by GMRES is also discussed. Two different preconditioners are developed, both of which employ existing Algebraic Multigrid (AMG) methods. Further, the most efficient preconditioner, overall, for the problems considered is based on a Picard linearization. Numerical examples demonstrate that these solvers are significantly faster than a standard Newton–Krylov approach; a speedup factor of approximately 26 was obtained for the Picard preconditioner on the largest grids studied here. In addition, these JFNK solvers exhibit good algorithmic scaling with increasing grid size.     

New updates of incomplete LU factorizations and applications to large nonlinear systems

In this paper, we address the problem of preconditioning sequences of large sparse indefinite systems of linear equations and present two new strategies to construct approximate updates of factorized preconditioners. Both updates are based on the availability of an incomplete factorization for one matrix of the sequence and differ in the approximation of the so-called ideal update. For a general treatment, an incomplete LU (ILU) factorization is considered, but the proposed approaches apply to incomplete factorizations of symmetric matrices as well. The first strategy is an approximate diagonal update of the ILU factorization; the second strategy relies on banded approximations of the factors in the ideal update. The efficiency and reliability of the proposed preconditioners are shown in the solution of nonlinear systems of equations by preconditioned Newton–Krylov methods. Nearly matrix-free implementations of the updating strategy are provided, and numerical experiments are carried out on application problems.     

AILU preconditioning for the finite element formulation of the incompressible Navier–Stokes equations

In this paper, the effect of a variable reordering method on the performance of “adapted incomplete LU (AILU)” preconditioners applied to the P2P1 mixed finite element discretization of the three-dimensional unsteady incompressible Navier–Stokes equations has been studied through numerical experiments, where eigenvalue distribution and convergence histories are examined. It has been revealed that the performance of an AILU preconditioner is improved by adopting a variable reordering method which minimizes the bandwidth of a globally assembled saddle-point type matrix. Furthermore, variants of the existing AILU(1) preconditioner have been suggested and tested for some three-dimensional flow problems. It is observed that the AILU(2) outperforms the existing AILU(1) with a little extra computing time and memory.     

The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids

An abstract framework ofauxiliary space method is proposed and, as an application, an optimal multigrid technique is developed for general unstructured grids. The auxiliary space method is a (nonnested) two level preconditioning technique based on a simple relaxation scheme (smoother) and an auxiliary space (that may be roughly understood as a nonnested coarser space). An optimal multigrid preconditioner is then obtained for a discretized partial differential operator defined on an unstructured grid by using an auxiliary space defined on a more structured grid in which a furthernested multigrid method can be naturally applied. This new technique makes it possible to apply multigrid methods to general unstructured grids without too much more programming effort than traditional solution methods. Some simple examples are also given to illustrate the abstract theory and for instance the Morley finite element space is used as an auxiliary space to construct a preconditioner for Argyris element for biharmonic equations. Some numerical results are also given to demonstrate the efficiency of using structured grid for auxiliary space to precondition unstructured grids.     

On relaxed nested factorization and combination preconditioning

The efficient solution of block tridiagonal linear systems arising from the discretization of convection–diffusion problem is considered in this paper. Starting with the classical nested factorization, we propose a relaxed nested factorization preconditioner. Then, several combination preconditioners are developed based on relaxed nested factorization and a tangential filtering preconditioner. Influence of the relaxation parameter is numerically studied, the results indicate that the optimal relaxation parameter should be close to but less than 1. The number of iteration counts exhibit an extremely sensitive behaviour. This phenomena resembles the behaviour of relaxed ILU preconditioner. For symmetric positive-definite coefficient matrix, we also show that the proposed combination preconditioner is convergent. Finally, numerous test cases are carried out with both additive and multiplicative combinations to verify the robustness of the proposed preconditioners.     

Spectral-element preconditioners for the uzawa pressure operator applied to incompressible flows

Seven preconditioners for the Uzawa pressure operator are discussed in the context of the spectral-element discretization of unsteady, incompressible flows. An already existing algorithm, based on decomposition of the pressure operator, is modified in order to reduce the number of iterations and cpu time. A twostage preconditioning technique is set up to solve efficiently problems at high Reynold numbers. The performance of the preconditioners is tested on a number of Stokes and Navier-Stokes problems in three dimensions.     

Comparison of Two-Level Preconditioners Derived from Deflation,Domain Decomposition and Multigrid Methods

For various applications, it is well-known that a multi-level, in particular two-level, preconditioned CG (PCG) method is an efficient method for solving large and sparse linear systems with a coefficient matrix that is symmetric positive definite. The corresponding two-level preconditioner combines traditional and projection-type preconditioners to get rid of the effect of both small and large eigenvalues of the coefficient matrix. In the literature, various two-level PCG methods are known, coming from the fields of deflation, domain decomposition and multigrid. Even though these two-level methods differ a lot in their specific components, it can be shown that from an abstract point of view they are closely related to each other. We investigate their equivalences, robustness, spectral and convergence properties, by accounting for their implementation, the effect of roundoff errors and their sensitivity to inexact coarse solves, severe termination criteria and perturbed starting vectors.