Applying approximate LU-factorizations as preconditioners in eight iterative methods for solving systems of linear algebraic equations

Many problems arising in different fields of science and engineering can be reduced, by applying some appropriate discretization, either to a system of linear algebraic equations or to a sequence of such systems. The solution of a system of linear algebraic equations is very often the most time-consuming part of the computational process during the treatment of the original problem, because these systems can be very large (containing up to many millions of equations). It is, therefore, important to select fast, robust and reliable methods for their solution, also in the case where fast modern computers are available. Since the coefficient matrices of the systems are normally sparse (i.e. most of their elements are zeros), the first requirement is to efficiently exploit the sparsity. However, this is normally not sufficient when the systems are very large. The computation of preconditioners based on approximate LU-factorizations and their use in the efforts to increase further the efficiency of the calculations will be discussed in this paper. Computational experiments based on comprehensive comparisons of many numerical results that are obtained by using ten well-known methods for solving systems of linear algebraic equations (the direct Gaussian elimination and nine iterative methods) will be reported. Most of the considered methods are preconditioned Krylov subspace algorithms.     

A UNIFIED FRAMEWORK FOR THE CONSTRUCTION OF VARIOUS ALGEBRAIC MULTILEVEL PRECONDITIONING METHODS

1.IntroductionThediscretizationofmanysecondorderselfadjointellipticboundaryvalueproblemsbythefiniteelementmethodleadstolargesparsesystemsoflinearequationswithsymmetricpositivedefinite(SPD)coefficientmatrices.Fortheselinearsystems,algebraicmultilevelp...     

BANDED TOEPLITZ PRECONDITIONERS FOR TOEPLITZ MATRICES FROM SINC METHODS

We give general expressions, analyze algebraic properties and derive eigenvalue bounds for a sequence of Toeplitz matrices associated with the sinc discretizations of various orders of differential operators. We demonstrate that these Toeplitz matrices can be satisfactorily preconditioned by certain banded Toeplitz matrices through showing that the spectra of the preconditioned matrices are uniformly bounded. In particular, we also derive eigenvalue bounds for the banded Toeplitz preconditioners. These results are elementary in constructing high-quality structured preconditioners for the systems of linear equations arising from the sinc discretizations of ordinary and partial differential equations, and are useful in analyzing algebraic properties and deriving eigenvalue bounds for the corresponding preconditioned matrices. Numerical examples are given to show effectiveness of the banded Toeplitz preconditioners.     

Algebraic multilevel iteration method for Stieltjes matrices

The numerical solution of elliptic selfadjoint second-order boundary value problems leads to a class of linear systems of equations with symmetric, positive definite, large and sparse matrices which can be solved iteratively using a preconditioned version of some algorithm. Such differential equations originate from various applications such as heat conducting and electromagnetics. Systems of equations of similar type can also arise in the finite element analysis of structures. We discuss a recursive method constructing preconditioners to a symmetric, positive definite matrix. An algebraic multilevel technique based on partitioning of the matrix in two by two matrix block form, approximating some of these by other matrices with more simple sparsity structure and using the corresponding Schur complement as a matrix on the lower level, is considered. The quality of the preconditioners is improved by special matrix polynomials which recursively connect the preconditioners on every two adjoining levels. Upper and lower bounds for the degree of the polynomials are derived as conditions for a computational complexity of optimal order for each level and for an optimal rate of convergence, respectively. The method is an extended and more accurate algebraic formulation of a method for nine-point and mixed five- and nine-point difference matrices, presented in some previous papers.     

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.     

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.     

Parallel preconditioners and multigrid solvers for stochastic polynomial chaos discretizations of the diffusion equation at the large scale

This paper presents parallel preconditioners and multigrid solvers for solving linear systems of equations arising from stochastic polynomial chaos formulations of the diffusion equation with random coefficients. These preconditioners and solvers are extensions of the preconditioner developed in an earlier paper for strongly coupled systems of elliptic partial differential equations that are norm equivalent to systems that can be factored into an algebraic coupling component and a diagonal differential component. The first preconditioner, which is applied to the norm equivalent system, is obtained by sparsifying the inverse of the algebraic coupling component. This sparsification leads to an efficient method for solving these systems at the large scale, even for problems with large statistical variations in the random coefficients. An extension of this preconditioner leads to stand‐alone multigrid methods that can be applied directly to the actual system rather than to the norm equivalent system. These multigrid methods exploit the algebraic/differential factorization of the norm equivalent systems to produce variable‐decoupled systems on the coarse levels. Moreover, the structure of these methods allows easy software implementation through re‐use of robust high‐performance software such as the Hypre library package. Two‐grid matrix bounds will be established, and numerical results will be given. Copyright © 2015 John Wiley & Sons, Ltd.     

On the semi-conjugate direction methods with dynamic preconditioning

The semi-conjugate residual methods and semi-conjugate gradient methods with dynamic preconditioners in Krylov subspaces are considered for solving the systems of linear algebraic equations whose matrices are not symmetric. Their orthogonal and variational properties are under study. New algorithms are proposed for choosing the inner iteration parameters in the preconditioning matrices corresponding to incomplete factorization methods. The efficiency of the resulting iterative processes is demonstrated by a set of numerical experiments for finite difference diffusion-convection equations.     

Robust AMLI methods for parabolic Crouzeix-Raviart FEM systems

For the iterative solution of linear systems of equations arising from finite element discretization of elliptic problems there exist well-established techniques to construct numerically efficient and computationally optimal preconditioners. Among those, most often preferred choices are Multigrid methods (geometric or algebraic), Algebraic MultiLevel Iteration (AMLI) methods, Domain Decomposition techniques.In this work, the method in focus is AMLI. We extend its construction and the underlying theory over to systems arising from discretizations of parabolic problems, using non-conforming finite element methods (FEM). The AMLI method is based on an approximated block two-by-two factorization of the original system matrix. A key ingredient for the efficiency of the AMLI preconditioners is the quality of the utilized block two-by-two splitting, quantified by the so-called Cauchy-Bunyakowski-Schwarz (CBS) constant, which measures the abstract angle between the two subspaces, associated with the two-by-two block splitting of the matrix.The particular choice of space discretization for the parabolic equations, used in this paper, is Crouzeix-Raviart non-conforming elements on triangular meshes. We describe a suitable splitting of the so-arising matrices and derive estimates for the associated CBS constant. The estimates are uniform with respect to discretization parameters in space and time as well as with respect to coefficient and mesh anisotropy, thus providing robustness of the method.     

Explicit preconditioning of systems of linear algebraic equations with dense matrices

For the acceleration of the convergence of the iterative methods for solving systems of linear algebraic equations with dense matrices, one suggests the use of sparse explicit preconditioners, based on the minimization of quadratic functionals and admitting adaptive refinement. One gives the results of test computations for exterior potential flow problems.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 154, pp. 90–100, 1986.The author considers it a pleasant duty to express here gratitude to A. T. Berland and V. A. Galaev for placing at my disposal a program for the generation of a test problem and to A. Yu. Eremin for assistance in carrying out the numerical experiments.     

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     

非匹配网格上Stokes-Darcy模型的非协调元方法及其预条件技术

本文讨论了非匹配网格上Stokes-Darcy模型的两种低阶非协调元方法,证明了离散问题的适定性并得到了最优的误差估计.对离散出来的非对称不定线性方程组,我们提出了几种有效的预条件子,证明了预条件子的最优性.最后,数值试验验证了我们的理论结果.     

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.     

Multilevel Preconditioners for Mixed Methods for Second Order Elliptic Problems

A new approach for constructing algebraic multilevel preconditioners for mixed finite element methods for second order elliptic problems with tensor coefficients on general geometry is proposed. The linear system arising from the mixed methods is first algebraically condensed to a symmetric, positive definite system for Lagrange multipliers, which corresponds to a linear system generated by standard nonconforming finite element methods. Algebraic multilevel preconditioners for this system are then constructed based on a triangulation of the domain into tetrahedral substructures. Explicit estimates of condition numbers and simple computational schemes are established for the constructed preconditioners. Finally, numerical results for the mixed finite element methods are presented to illustrate the present theory.     

Block two-stage preconditioners

Linear systems of the form Ax = b, where the matrix A is symmetric and positive definite, often arise from the discretization of elliptic partial differential equations. A very successful method for solving these linear systems is the preconditioned conjugate gradient method. In this paper, we study parallel preconditioners for the conjugate gradient method based on the block two-stage iterative methods. Sufficient conditions for the validity of these preconditioners are given. Computational results of these preconditioned conjugate gradient methods on two parallel computing systems are presented.     

A framework of parallel algebraic multilevel preconditioning iterations

1.IntroductionConsiderthesyllUnetricpositivedeflate(SPD)systemsoflinearequationsthatariseinfiniteelementdiscretisstionsofmanysecond-orderself-adjointellipticboundaryvalueproblems.Tosolvethisclassoflinearsystemsiteratively,AxelssonandVassilevski[1--4]preselltedthealgebraicmultileveliteration(AMLI)methodsbyreasonablyutilizingthemultigridtechniqueandthepolynomialaccelerationstrategy.Thesemethodsareamongthemostefficientiterativesolversbecausetheirpreconditioningmatricesarespectrallyequlvalellt…     

HYBRID ALGEBRAIC MULTILEVEL PRECONDITIONING METHODS

ＨＹＢＲＩＤＡＬＧＥＢＲＡＩＣＭＵＬＴＩＬＥＶＥＬＰＲＥＣＯＮＤＩＴＩＯＮＩＮＧＭＥＴＨＯＤＳ￥ＢａｉＺｈｏｎｇｚｈｉ（白中治）（ＦｕｄａｎＵｎｉｖｅｒｓｉｔｙ，复旦大学，邮编：２００４３３）Ａｂｓｔｒａｃｔ：Ａｃｌａｓｓｏｆｈｙｂｒｉｄａｌｇｅｂｒ...     

Improvements for some condition number estimates for preconditioned system in p‐FEM

In this paper, we consider domain decomposition preconditioners for a system of linear algebraic equations arising from the p‐version of the FEM. We analyse several multi‐level preconditioners for the Dirichlet problems in the sub‐domains in two and three dimensions. It is proved that the condition number of the preconditioned system is bounded by a constant independent of the polynomial degree. Relations between the p‐version of the FEM and the h‐version are helpful in the interpretations of the results. Copyright © 2006 John Wiley & Sons, Ltd.     

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.