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 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.     

The approximate Dirichlet Domain Decomposition method. Part I: An algebraic approach

We present a new approach to the construction of Domain Decomposition (DD) preconditioners for the conjugate gradient method applied to the solution of symmetric and positive definite finite element equations. The DD technique is based on a non-overlapping decomposition of the domain Ω intop subdomains connected later with thep processors of a MIMD computer. The DD preconditioner derived contains three block matrices which must be specified for the specific problem considered. One of the matrices is used for the transformation of the nodal finite element basis into the approximate discrete harmonic basis. The other two matrices are block preconditioners for the Dirichlet problems arising on the subdomains and for a modified Schur complement defined over all nodes on the coupling boundaries between the subdomains. The relative spectral condition number is estimated. Relations to the additive Schwarz method are discussed. In the second part of this paper, we will apply the results of this paper to two-dimensional, symmetric, second-order, elliptic boundary value problems and present numerical results performed on a transputer-network.     

Variants of the deteriorated PSS preconditioner for saddle point problems

Two new preconditioners, which can be viewed as variants of the deteriorated positive definite and skew-Hermitian splitting preconditioner, are proposed for solving saddle point problems. The corresponding iteration methods are proved to be convergent unconditionally for cases with positive definite leading blocks. The choice strategies of optimal parameters for the two iteration methods are discussed based on two recent optimization results for extrapolated Cayley transform, which result in faster convergence rate and more clustered spectrum. Compared with some preconditioners of similar structures, the new preconditioners have better convergence properties and spectrum distributions. In addition, more practical preconditioning variants of the new preconditioners are considered. Numerical experiments are presented to illustrate the advantages of the new preconditioners over some similar preconditioners to accelerate GMRES.     

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.     

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.     

A projection method for solving nonsymmetric linear systems on multiprocessors

We consider the iterative solution of large sparse linear systems of equations arising from elliptic and parabolic partial differential equations in two or three space dimensions. Specifically, we focus our attention on nonsymmetric systems of equations whose eigenvalues lie on both sides of the imaginary axis, or whose symmetric part is not positive definite. This system of equation is solved using a block Kaczmarz projection method with conjugate gradient acceleration. The algorithm has been designed with special emphasis on its suitability for multiprocessors. In the first part of the paper, we study the numerical properties of the algorithm and compare its performance with other algorithms such as the conjugate gradient method on the normal equations, and conjugate gradient-like schemes such as ORTHOMIN(k), GCR(k) and GMRES(k). We also study the effect of using various preconditioners with these methods. In the second part of the paper, we describe the implementation of our algorithm on the CRAY X-MP/48 multiprocessor, and study its behavior as the number of processors is increased.     

Block preconditioners with circulant blocks for general linear systems

Block preconditioner with circulant blocks (BPCB) has been used for solving linear systems with block Toeplitz structure since 1992 [R. Chan, X. Jin, A family of block preconditioners for block systems, SIAM J. Sci. Statist. Comput. (13) (1992) 1218–1235]. In this new paper, we use BPCBs to general linear systems (with no block structure usually). The BPCBs are constructed by partitioning a general matrix into a block matrix with blocks of the same size and then applying T. Chan’s optimal circulant preconditioner [T. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. (9) (1988) 766–771] to each block. These BPCBs can be viewed as a generalization of T. Chan’s preconditioner. It is well-known that the optimal circulant preconditioner works well for solving some structured systems such as Toeplitz systems by using the preconditioned conjugate gradient (PCG) method, but it is usually not efficient for solving general linear systems. Unlike T. Chan’s preconditioner, BPCBs used here are efficient for solving some general linear systems by the PCG method. Several basic properties of BPCBs are studied. The relations of the block partition with the cost per iteration and the convergence rate of the PCG method are discussed. Numerical tests are given to compare the cost of the PCG method with different BPCBs.     

Aztec在混凝土细观数值模拟中的应用研究

细观数值模拟是混凝土性能研究的一种重要手段,但稀疏线性方程组求解在总体模拟时间中所占比重很大。由于属于三维问题,且规模很大,所以采用预条件Krylov子空间迭代是必由之路。Aztec是国际上专门设计用于求解稀疏线性方程组的软件包之一,由于目前混凝土细观数值模拟中的稀疏线性方程组对称正定,所以利用Aztec中提供的CG迭代法进行求解,并对多种能保持对称性的预条件选项进行了实验比较。结果表明,在基于区域分解的并行不完全Cholesky分解、无重叠对称化GS迭代、最小二乘等预条件技术中,第一种的效率最高,且在重叠度为0,填充层次为0时,效果最好;实验结果还表明,在本应用问题中,用RCM排序一般导致求解时间更长,从而没有必要采用。     

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.     

Parallel scheduling of the PCG method for banded matrices rising from FDM/FEM

An implicit time-linearized finite difference discretization of partial differential equations on regular/structured meshes results in an n-diagonal block system of algebraic equations, which is usually solved by means of the Preconditioned Conjugate Gradient (PCG) method. In this paper, an analysis of the parallel implementation of this method on several computer architectures and for several programming paradigms is presented. For three-dimensional regular/structured meshes, a new implementation of the PCG method with Jacobi preconditioner is proposed. For the computer architectures and number of processors employed in this study, it has been found that this implementation is more efficient than the standard one, and can be applied to narrow-band matrices and other preconditioners, such as, for example, polynomial ones.     

A modified symmetric successive overrelaxation method for augmented systems

In this paper, we establish a modified symmetric successive overrelaxation (MSSOR) method, to solve augmented systems of linear equations, which uses two relaxation parameters. This method is an extension of the symmetric SOR (SSOR) iterative method. The convergence of the MSSOR method for augmented systems is studied. Numerical examples show that the new method is an efficient method.     

Approximate polynomial preconditionings applied to biharmonic equations

Applying a finite difference approximation to a biharmonic equation results in a very ill conditioned system of equations. This paper examines the conjugate gradient method used with polynomial preconditioning techniques for solving such linear systems. A new approach using an approximate polynomial preconditioner is described. The preconditioner is constructed from a series approximation based on the Laplacian finite difference matrix. A particularly attractive feature of this approach is that the Laplacian matrix consists of far fewer non-zero entries than the biharmonic finite difference matrix. Moreover, analytical estimates and computational results show that this preconditioner is more effective (in terms of the rate of convergence and the computational work required per iteration) than the polynomial preconditioner based on the original biharmonic matrix operator. The conjugate gradient algorithm and the preconditioning step can be efficiently implemented on a vector super-computer such as the CDC CYBER 205.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada Grant U0375; and in part by NASA (funded under the Space Act Agreement C99066G) while the author was visiting ICOMP, NASA Lewis Research Center.The work of this author was supported by an Izaak Walton Killam Memorial Scholarship.     

广义修正HSS迭代法的超松弛加逮

通过推广修正埃尔米特和反埃尔米特（MHSS）迭代法,我们进一步得到了求解大型稀疏非埃尔米特正定线性方程组的广义MHSS（GMHSS）迭代法．基于不动点方程,我们还将超松弛（SOR）技术运用到了GMHSS迭代法,得到了关于GMHSS迭代法的SOR加速,并分析了它的收敛性．数值算例表明,SOR技术能够大大提高加速GMHSS迭代法的收敛效率．     

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.     

A numerical study on preconditioning and partitioning schemes for reactive transport in a PEMFC catalyst layer

A numerical method used to simulate PEMFC catalyst layer transport and electrochemistry is described. The set of nonlinear equations is discretized using the finite volume method and solved using an inexact Newton method. A block “ILU porous” preconditioner is used to precondition the linear system. A “porous partitioning” scheme is used to partition the domain for parallel processors. Geometries with low porosities are found to require a much smaller number of iterations for convergence compared to geometries with high porosities. The porous partitioning scheme is shown to outperform the standard partitioning scheme for cases run with more than 4 processors. The block “ILU porous” preconditioner was not found to be more effective than the block ILU(1) preconditioner. Finally, the importance of using rigorous convergence criteria in these simulations is demonstrated by comparing the computed total consumption values of different species at different nonlinear rms tolerance values.     

A useful technique for the point Successive Over Relaxation method

By gradually decreasing the relaxation parameter in the SOR method, it is shown that the number of iterations required for the unknown variables to converge to reasonable values can be reduced. This practical SOR method can also be applied for composite substances with arbitrary geometry. When applying the method to a simple example of a composite substance, the iteration number was reduced by about 20% as compared with the ordinary SOR method using an optimal relaxation parameter.     

Fast parallel Preconditioned Conjugate Gradient algorithms for robot manipulator dynamics simulation

In this paper fast parallel Preconditioned Conjugate Gradient (PCG) algorithms for robot manipulator forward dynamics, or dynamic simulation, problem are presented. By exploiting the inherent structure of the forward dynamics problem, suitable preconditioners are devised to accelerate the iterations. Also, based on the choice of preconditioners, a modified dynamic formulation is used to speedup both serial and parallel computation of each iteration. The implementation of the parallel algorithms on two interconnected processor arrays is discussed and their computation and communication complexities are analyzed. The simulation results for a Puma Arm are presented to illustrate the effectiveness of the proposed preconditioners. With a faster convergence due to preconditioning and a faster computation of iterations due to parallelization, the developed parallel PCG algorithms represent the fastest alternative for parallel computation of the problem withO(n) processors.     

A new matrix splitting preconditioner for generalized saddle point problems

For generalized saddle point problems, we establish a new matrix splitting preconditioner and give the implementing process in detail. The new preconditioner is much easier to be implemented than the modified dimensional split (MDS) preconditioner. The convergence properties of the new splitting iteration method are analyzed. The eigenvalue distribution of the new preconditioned matrix is discussed and an upper bound for the degree of its minimal polynomial is derived. Finally, some numerical examples are carried out to verify the effectiveness and robustness of our preconditioner on generalized saddle point problems discretizing the incompressible Navier–Stokes equations.     

Preconditioning technique for symmetric M-matrices

Abstract Linear systems with M-matrices occur in a wide variety of areas including numerical partial differential equations, input-output production and growth models in economics, linear complementarity problems in operations research and Markov chains in stochastic analysis.In this paper, we propose a new preconditioner for solving a system with symmetric positive definite M-matrix by the preconditioned conjugate gradient (PCG) method. We show that our preconditioner increases the convergence rate of the PCG method and reduces the operation cost. Numerical results are given.