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.     

求解Maxwell线性元鞍点系统的基于HX预条件子的Uzawa算法

首先对含跳系数的H~1型和H(curl)型椭圆问题的线性有限元方程,分别设计了基于AMG预条件子和基于节点辅助空间预条件子(HX预条件子)的PCG法.数值实验表明,算法的迭代次数基本不依赖于系数跳幅和离散网格"尺寸".然后以此为基础,对Maxwell方程组鞍点问题的第一类N(e)d(e)lec线性棱元离散系统设计并分析了一种基于HX预条件子的Uzawa算法.当系数光滑时,理论上证明了算法的收敛率与网格规模无关.数值实验表明,新算法对跳系数情形也是高效和稳定的.     

New block triangular preconditioner for linear systems arising from the discretized time-harmonic Maxwell equations

In this paper, based on the preconditioners presented by Rees and Greif [T. Rees, C. Greif, A preconditioner for linear systems arising from interior point optimization methods, SIAM J. Sci. Comput. 29 (2007) 1992-2007], we present a new block triangular preconditioner applied to the problem of solving linear systems arising from finite element discretization of the mixed formulation of the time-harmonic Maxwell equations (k=0) in electromagnetic problems, since linear systems arising from the corresponding equations and methods have the same matrix block structure. Similar to spectral distribution of the preconditioners presented by Rees and Greif, this paper analyzes the corresponding spectral distribution of the new preconditioners considered in this paper. From the views of theories and applications, the presented preconditioners are as efficient as the preconditioners presented by Rees and Greif to apply. Moreover, numerical experiments are also reported to illustrate the efficiency of the presented preconditioners.     

Towards a rigorously justified algebraic preconditioner for high-contrast diffusion problems

In this paper we present a new preconditioner suitable for solving linear systems arising from finite element approximations of elliptic PDEs with high-contrast coefficients. The construction of the preconditioner consists of two phases. The first phase is an algebraic one which partitions the degrees of freedom into “high” and “low” permeability regions which may be of arbitrary geometry. This partition yields a corresponding blocking of the stiffness matrix and hence a formula for the action of its inverse involving the inverses of both the high permeability block and its Schur complement in the original matrix. The structure of the required sub-block inverses in the high contrast case is revealed by a singular perturbation analysis (with the contrast playing the role of a large parameter). This shows that for high enough contrast each of the sub-block inverses can be approximated well by solving only systems with constant coefficients. The second phase of the algorithm involves the approximation of these constant coefficient systems using multigrid methods. The result is a general method of algebraic character which (under suitable hypotheses) can be proved to be robust with respect to both the contrast and the mesh size. While a similar performance is also achieved in practice by algebraic multigrid (AMG) methods, this performance is still without theoretical justification. Since the first phase of our method is comparable to the process of identifying weak and strong connections in conventional AMG algorithms, our theory provides to some extent a theoretical justification for these successful algebraic procedures. We demonstrate the advantageous properties of our preconditioner using experiments on model problems. Our numerical experiments show that for sufficiently high contrast the performance of our new preconditioner is almost identical to that of the Ruge and Stüben AMG preconditioner, both in terms of iteration count and CPU-time.     

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.     

Structure Preserving Preconditioners for Image Deblurring

Regularizing preconditioners for accelerating the convergence of iterative regularization methods without spoiling the quality of the approximated solution have been extensively investigated in the last twenty years. Several strategies have been proposed for defining proper preconditioners. Usually, in methods for image restoration, the structure of the preconditioner is chosen Block Circulant with Circulant Blocks (BCCB) because it can be efficiently exploited by Fast Fourier Transform (FFT). Nevertheless, for ill-conditioned problems, it is well-known that BCCB preconditioners cannot provide a strong clustering of the eigenvalues. Moreover, in order to get an effective preconditioner, it is crucial to preserve the structure of the coefficient matrix. The structure of such a matrix, in case of image deblurring problem, depends on the boundary conditions imposed on the imaging model. Therefore, we propose a technique to construct a preconditioner which has the same structure of the blurring matrix related to the restoration problem at hand. The construction of our preconditioner requires two FFTs like the BCCB preconditioner. The presented preconditioning strategy represents a generalization and an improvement with respect to both circulant and structured preconditioning available in the literature. The technique is further extended to provide a non-stationary preconditioning in the same spirit of a recent proposal for BCCB matrices. Some numerical results show the importance of preserving the matrix structure from the point of view of both restoration quality and robustness of the regularization parameter.     

A new preconditioner for generalized saddle point matrices with highly singular(1,1) blocks

In this paper, based on the preconditioners presented by Cao [A note on spectrum analysis of augmentation block preconditioned generalized saddle point matrices, Journal of Computational and Applied Mathematics 238(15) (2013), pp. 109–115], we introduce and study a new augmentation block preconditioners for generalized saddle point matrices whose coefficient matrices have singular (1,1) blocks. Moreover, theoretical analysis gives the eigenvalue distribution, forms of the eigenvectors and its minimal polynomial. Finally, numerical examples show that the eigenvalue distribution with presented preconditioner has the same spectral clustering with preconditioners in the literature when choosing the optimal parameters and the preconditioner in this paper and in the literature improve the convergence of BICGSTAB and GMRES iteration efficiently when they are applied to the preconditioned BICGSTAB and GMRES to solve the Stokes equation and two-dimensional time-harmonic Maxwell equations by choosing different parameters.     

Solving the signorini problem on the basis of domain decomposition techniques

The finite element discretization of the Signorini Problem leads to a large scale constrained minimization problem. To improve the convergence rate of the projection method preconditioning must be developed. To be effective, the relative condition number of the system matrix with respect to the preconditioning matrix has to be small and the applications of the preconditioner as well as the projection onto the set of feasible elements have to be fast computable. In this paper, we show how to construct and analyze such preconditioners on the basis of domain decomposition techniques. The numerical results obtained for the Signorini problem as well as for contact problems in plane elasticity confirm the theoretical analysis quite well.     

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.     

A general class of shift-splitting preconditioners for non-Hermitian saddle point problems with applications to time-harmonic eddy current models

Based on a general splitting of the (1,1) leading block matrix, we first construct a general class of shift-splitting (GCSS) preconditioners for non-Hermitian saddle point problems. Convergence conditions of the corresponding matrix splitting iteration methods and preconditioning properties of the GCSS preconditioned saddle point matrices are analyzed. Then the GCSS preconditioner is specifically applied to the non-Hermitian saddle point problems arising from the finite element discretizations of the hybrid formulations of the time-harmonic eddy current models. With suitable choices of the splittings, the new GCSS preconditioners are easier to implement and have faster convergence rates than the existing shift-splitting preconditioner and its modified variant. Two numerical examples are presented to verify the theoretical results and show effectiveness of the new proposed preconditioners.     

A new wavelet transform preconditioner for iterative solution of elastohydrodynamic lubrication problems

We develop a novel preconditioning strategy, based on a non-standard, Discrete Wavelet Transform (DWT), for the dense, non-symmetric, linear systems that must be solved when Newton's method is used in the solution of Elastohydrodynamic Lubrication (EHL) problems. Simple band preconditioners and sparse preconditioners based on standard DWT have been found to be of limited value for EHL problems, since they may be singular, give poor convergence or be expensive to apply. We present algorithms for preconditioner design based on detecting non-smooth diagonal bands within an otherwise smooth matrix and applying a non-standard DWT to compress the part of the matrix away from the band. We illustrate, by numerical examples, the improvements that can be made when our methods are used.     

A robust preconditioner for fluid–structure interaction problems

Two preconditioners are presented for equation systems of strongly coupled fluid–structure interaction computations where the structure is modeled by shell elements. These preconditioners fall into the general category of incomplete LU factorization. The two differ mainly in whether the coefficient matrix is factorized node by node or variable-by-variable. In the variable-wise preconditioner, a modified Schur complement system for pressure is solved approximately with a few iterations using a special preconditioner. The efficiencies of the two preconditioners are compared for different finite element formulations of the fluid mechanics part, including formulations with SUPG and PSPG stabilizations.     

Variable Additive Preconditioning Procedures

Iterative methods with variable preconditioners of additive type are proposed. The scaling factors of each summand in the additive preconditioners are optimized within each iteration step. It is proved that the presented methods converge at least as fast as the Richardson's iterative method with the corresponding additive preconditioner with optimal scaling factors. In the presented numerical experiments the suggested methods need nearly the same number of iterations as the usual preconditioned conjugate gradient method with the corresponding additive preconditioner with numerically determined fixed optimal scaling factors. Received: June 10, 1998; revised October 16, 1998     

A fast preconditioner for the incompressible Navier Stokes Equations

The pressure matrix method is a well known scheme for the solution of the incompressible Navier–Stokes equations by splitting the computation of the velocity and the pressure fields (see, e.g., [17]). However, the set-up of effective preconditioners for the pressure matrix is mandatory in order to have an acceptable computational cost. Different strategies can be pursued (see, e.g., [6, 22 , 4, 7, 9]). Inexact block LU factorizations of the matrix obtained after the discretization and linearization of the problem, originally proposed as fractional step solvers, provide also a strategy for building effective preconditioners of the pressure matrix (see [23]). In this paper, we present numerical results about a new preconditioner, based on an inexact factorization. The new preconditioner applies to the case of the generalized Stokes problem and to the Navier–Stokes one, as well. In the former case, it improves the performances of the well known Cahouet–Chabard preconditioner (see [2]). In the latter one, numerical results presented here show an almost optimal behavior (with respect to the space discretization) and suggest that the new preconditioner is well suited also for flexible or inexact strategies, in which the systems for the preconditioner are solved inaccurately.     

Guaranteed and Fully Robust a posteriori Error Estimates for Conforming Discretizations of Diffusion Problems with Discontinuous Coefficients

We study in this paper a posteriori error estimates for H ¹-conforming numerical approximations of diffusion problems with a diffusion coefficient piecewise constant on the mesh cells but arbitrarily discontinuous across the interfaces between the cells. Our estimates give a global upper bound on the error measured either as the energy norm of the difference between the exact and approximate solutions, or as a dual norm of the residual. They are guaranteed, meaning that they feature no undetermined constants. (Local) lower bounds for the error are also derived. Herein, only generic constants independent of the diffusion coefficient appear, whence our estimates are fully robust with respect to the jumps in the diffusion coefficient. In particular, no condition on the diffusion coefficient like its monotonous increasing along paths around mesh vertices is imposed, whence the present results also include the cases with singular solutions. For the energy error setting, the key requirement turns out to be that the diffusion coefficient is piecewise constant on dual cells associated with the vertices of an original simplicial mesh and that harmonic averaging is used in the scheme. This is the usual case, e.g., for the cell-centered finite volume method, included in our analysis as well as the vertex-centered finite volume, finite difference, and continuous piecewise affine finite element ones. For the dual norm setting, no such a requirement is necessary. Our estimates are based on H(div)-conforming flux reconstruction obtained thanks to the local conservativity of all the studied methods on the dual grids, which we recall in the paper; mutual relations between the different methods are also recalled. Numerical experiments are presented in confirmation of the guaranteed upper bound, full robustness, and excellent efficiency of the derived estimators.     

Preconditioning by Gram matrix approximation for diffusion–convection–reaction equations with discontinuous coefficients

This work analyses the preconditioning with Gram matrix approximation for the numerical solution of a linear convection–diffusion–reaction equation with discontinuous diffusion and reaction coefficients. The standard finite element method with piecewise linear test and trial functions on uniform meshes discretizes the equation. Three preconditioned conjugate gradient algorithms solve the discrete linear system: CGS, CGSTAB and GMRES. The preconditioning with Gram matrix approximation consists of replacing the solving of the equation with the preconditioner by two symmetric MG iterations. Numerical results are presented to assess the convergence behaviour of the preconditioning and to compare it with other preconditioners of multilevel type.     

块三对角矩阵局部块分解及其在预条件中的应用

该文利用块三对阵角阵分解因子的估值分析了其局部依赖性，并用其构了一类不完全分解型预条件子，给出了五点差分矩阵预条件后的条件数估计，并比较了条件数估计值与实际值，表明了估计值的准确性与预备件的有效性，在具体实现时，考虑了预条件的6个串行实现方案并提出了一个有效的并行化方法，该并行算法具有通信量少的特点，最后在由4中微机通过高速以太网连成的机群系统上作了大量数值实验，并将其与其它较效的预条件方法进行了。结果表明该预条件方法效果较好，尤其适用于并行计算。     

Parameterized generalized shift-splitting preconditioners for nonsymmetric saddle point problems

To solve nonsymmetric saddle point problems, the parameterized generalized shift-splitting (PGSS) preconditioner is presented and analyzed. The corresponding PGSS iteration method can be applied not only to the nonsingular saddle point problems but also to the singular ones. The convergence and semi-convergence of the PGSS iteration method are discussed carefully. Meanwhile, the spectral properties of the preconditioned matrix and the strategy of the choices of the parameters are given. Numerical experiments further demonstrate that the PGSS iteration method and the PGSS preconditioner are efficient and have better performance than some existing iteration methods and newly proposed preconditioners, respectively, for solving both the nonsingular and singular nonsymmetric saddle point problems.     

Accelerating iterative linear solvers using multiple graphical processing units

In this paper, we develop, study and implement iterative linear solvers and preconditioners using multiple graphical processing units (GPUs). Techniques for accelerating sparse matrix–vector (SpMV) multiplication, linear solvers and preconditioners are presented. Four Krylov subspace solvers, a Neumann polynomial preconditioner and a domain decomposition preconditioner are implemented. Our numerical tests with NVIDIA C2050 GPUs show that the SpMV kernel can be sped over 40 times faster using four GPUs. Our linear solvers and preconditioners have similar speedup.     

The approximate Dirichlet Domain Decomposition method. Part II: Applications to 2nd-order Elliptic B.V.P.s

In the first part of this article series, we had derived Domain Decomposition (DD) preconditioners containing three block matrices which must be specified for specific applications. In the present paper, we consider finite element equations arising from the DD discretization of plane, symmetric, 2nd-order, elliptic b.v.p.s and specify the matrices involved in the preconditioner via multigrid and hierarchical techniques. The resulting DD-PCCG methods are asymptotically almost optimal with respect to the operation count and well suited for parallel computations on MIMD computers with local memory and message passing. The numerical experiments performed on a transputer hypercube confirm the efficiency of the DD preconditioners proposed.