BTTB preconditioners for BTTB least squares problems

In this paper, we consider solving the least squares problem min_x‖b-Tx‖₂ by using preconditioned conjugate gradient (PCG) methods, where T is a large rectangular matrix which consists of several square block-Toeplitz-Toeplitz-block (BTTB) matrices and b is a column vector. We propose a BTTB preconditioner to speed up the PCG method and prove that the BTTB preconditioner is a good preconditioner. We then discuss the construction of the BTTB preconditioner. Numerical examples, including image restoration problems, are given to illustrate the efficiency of our BTTB preconditioner. Numerical results show that our BTTB preconditioner is more efficient than the well-known Level-1 and Level-2 circulant preconditioners.     

Iterative solvers and stabilisation for mixed electrostatic and magnetostatic formulations

Mixed electrostatic and magnetostatic finite element formulations are considered. Solution methods for the resulting indefinite algebraic systems are investigated. Methods developed for the mixed formulations of the Stokes equations are modified in order to apply to the Maxwell equations: an efficient block preconditioner is proposed and a stabilised formulation is described. The different methods are applied to 2D and 3D examples.     

Parallel preconditioners for large scale partial difference equation systems

We propose a new preconditioner DASP (discrete approximate spectral preconditioner), based on the existing well-known preconditioners and our computational experience. Parallel preconditioning strategies for large scale partial difference equation systems arising from partial differential equations are investigated. Numerical results are given to show the efficiency and effectiveness of the new preconditioners for both model problems and real applications in petroleum reservoir simulation.     

A Rayleigh–Ritz preconditioner for the iterative solution to large scale nonlinear problems

The approximation to the solution of large sparse symmetric linear problems arising from nonlinear systems of equations is considered. We are focusing herein on reusing information from previous processes while solving a succession of linear problems with a Conjugate Gradient algorithm. We present a new Rayleigh–Ritz preconditioner that is based on the Krylov subspaces and superconvergence properties, and consists of a suitable reuse of a given set of Ritz vectors. The relevance and the mathematical foundations of the current approach are detailed and the construction of the preconditioner is presented either for the unconstrained or the constrained problems. A corresponding practical preconditioner for iterative domain decomposition methods applied to nonlinear elasticity is addressed, and numerical validation is performed on a poorly-conditioned large-scale practical problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

Positive definite balancing Neumann–Neumann preconditioners for nearly incompressible elasticity

In this paper, a positive definite Balancing Neumann–Neumann (BNN) solver for the linear elasticity system is constructed and analyzed. The solver implicitly eliminates the interior degrees of freedom in each subdomain and solves iteratively the resulting Schur complement, involving only interface displacements, using a BNN preconditioner based on the solution of a coarse elasticity problem and local elasticity problems with natural and essential boundary conditions. While the Schur complement becomes increasingly ill-conditioned as the materials becomes almost incompressible, the BNN preconditioned operator remains well conditioned. The main theoretical result of the paper shows that the proposed BNN method is scalable and quasi-optimal in the constant coefficient case. This bound holds for material parameters arbitrarily close to the incompressible limit. While this result is due to an underlying mixed formulation of the problem, both the interface problem and the preconditioner are positive definite. Numerical results in two and three dimensions confirm these good convergence properties and the robustness of the methods with respect to the almost incompressibility of the material.     

Two preconditioners based on the multi-level splitting of finite element spaces

Summary The hierarchical basis preconditioner and the recent preconditioner of Bramble, Pasciak and Xu are derived and analyzed within a joint framework. This discussion elucidates the close relationship between both methods. Special care is devoted to highly nonuniform meshes; exclusively local properties like the shape regularity of the finite elements are utilized.The author was supported by the Konrad-Zuse-Zentrum für Informationstechnik Berlin, Federal Republic of Germany     

Evaluation of ST preconditioners for saddle point problems

The general block ST decomposition of the saddle point problem is used as a preconditioner to transform the saddle point problem into an equivalent symmetric and positive definite system. Such a decomposition is called a block ST preconditioner. Two general block ST preconditioners are proposed for saddle point problems with symmetric and positive definite (1,1)-block. Some estimations of the condition number of the preconditioned system are given. The same study is done for singular (1,1)-block.     

On block-circulant preconditioners for high-order compact approximations of convection-diffusion problems

We study some properties of block-circulant preconditioners for high-order compact approximations of convection-diffusion problems. For two-dimensional problems, the approximation gives rise to a nine-point discretisation matrix and in three dimensions, we obtain a nineteen-point matrix. We derive analytical expressions for the eigenvalues of the block-circulant preconditioner and this allows us to establish the invertibility of the preconditioner in both two and three dimensions. The eigenspectra of the preconditioned matrix in the two-dimensional case is described for different test cases. Our numerical results indicate that the block-circulant preconditioning leads to significant reduction in iteration counts and comparisons between the high-order compact and upwind discretisations are carried out. For the unpreconditioned systems, we observe fewer iteration counts for the HOC discretisation but for the preconditioned systems, we find similar iteration counts for both finite difference approximations of constant-coefficient two-dimensional convection-diffusion problems.     

Lower bounds for three-dimensional nonoverlapping domain decomposition algorithms

Summary. Lower bounds for the condition numbers of the preconditioned systems are obtained for the wire basket preconditioner and the Neumann-Neumann preconditioner in three dimensions. They show that the known upper bounds are sharp. Received January 28, 2001 / Revised version received September 3, 2001 / Published online January 30, 2002 This work was supported in part by the National Science Foundation under Grant Nos. DMS-9600133 and DMS-0074246     

Performance Study and Analysis of Parallel Multilevel Preconditioners

The significant gap between peak and realized performance of parallel systems motivates the need for performance analysis. In order to predict the performance of a class of parallel multilevel ILU preconditioner (PBILUM), we build two performance prediction models for both the preconditioner construction phase and the solution phase. These models combine theoretical features of the preconditioners with estimates on computation cost, communications overhead, etc. Experimental simulations show that our model predication based on certain reasonable assumptions is close to the simulation results. The models may be used to predict the performance of this class of parallel preconditioners.*The research work of the authors was supported in part by the U.S. National Science Foundation under grants CCR-9988165, CCR-0092532, ACR-0202934, and ACR-234270, by the U.S. Department of Energy Office of Science under grant DE-FG02-02ER45961, by the Kentucky Science & Engineering Foundation under grant KSEF-02-264-RED-002.     

New breakdown-free variant of AINV method for nonsymmetric positive definite matrices

This paper proposes a new breakdown-free preconditioning technique, called SAINV-NS, of the AINV method of Benzi and Tuma for nonsymmetric positive definite matrices. The resulting preconditioner which is an incomplete factorization of the inverse of a nonsymmetric matrix will be used as an explicit right preconditioner for QMR, BiCGSTAB and GMRES(m) methods. The preconditoner is reliable (pivot breakdown can not occur) and effective at reducing the number of iterations. Some numerical experiments on test matrices are presented to show the efficiency of the new method and comparing to the AINV-A algorithm.     

An additive Schwarz preconditioner for p-version boundary element approximation of the hypersingular operator in three dimensions

Summary. Additive Schwarz preconditioners are developed for the p-version of the boundary element method for the hypersingular integral equation on surfaces in three dimensions. The principal preconditioner consists of decomposing the subspace into local spaces associated with the element interiors supplemented with a wirebasket space associated with the the element interfaces. The wirebasket correction involves inverting a diagonal matrix. If exact solvers are used on the element interiors then theoretical analysis shows that growth of the condition number of the preconditioned system is bounded by for an open surface and for a closed surface. A modified form of the preconditioner only requires the inversion of a diagonal matrix but results in a further degradation of the condition number by a factor . Received December 15, 1998 / Revised version received March 26, 1999 / Published online March 16, 2000     

Adaptive filtering

Summary. In this paper, the adaptive filtering method is introduced and analysed. This method leads to robust algorithms for the solution of systems of linear equations which arise from the discretisation of partial differential equations with strongly varying coefficients. These iterative algorithms are based on the tangential frequency filtering decompositions (TFFD). During the iteration with a preliminary preconditioner, the adaptive test vector method calculates new test vectors for the TFFD. The adaptive test vector iterative method allows the combination of the tangential frequency decomposition and other iterative methods such as multi-grid. The connection with the TFFD improves the robustness of these iterative methods with respect to varying coefficients. Interface problems as well as problems with stochastically distributed properties are considered. Realistic numerical experiments confirm the efficiency of the presented algorithms. Received June 26, 1996 / Revised version received October 7, 1996     

Incomplete block factorization preconditioning for indefinite elliptic problems

Summary. The application of the finite difference method to approximate the solution of an indefinite elliptic problem produces a linear system whose coefficient matrix is block tridiagonal and symmetric indefinite. Such a linear system can be solved efficiently by a conjugate residual method, particularly when combined with a good preconditioner. We show that specific incomplete block factorization exists for the indefinite matrix if the mesh size is reasonably small, and that this factorization can serve as an efficient preconditioner. Some efforts are made to estimate the eigenvalues of the preconditioned matrix. Numerical results are also given. Received November 21, 1995 / Revised version received February 2, 1998 / Published online July 28, 1999     

Using groups in the splitting preconditioner computation for interior point methods

Interior point methods usually rely on iterative methods to solve the linear systems of large scale problems. The paper proposes a hybrid strategy using groups for the preconditioning of these iterative methods. The objective is to solve large scale linear programming problems more efficiently by a faster and robust computation of the preconditioner. In these problems, the coefficient matrix of the linear system becomes ill conditioned during the interior point iterations, causing numerical difficulties to find a solution, mainly with iterative methods. Therefore, the use of preconditioners is a mandatory requirement to achieve successful results. The paper proposes the use of a new columns ordering for the splitting preconditioner computation, exploring the sparsity of the original matrix and the concepts of groups. This new preconditioner is designed specially for the final interior point iterations; a hybrid approach with the controlled Cholesky factorization preconditioner is adopted. Case studies show that the proposed methodology reduces the computational times with the same quality of solutions when compared to previous reference approaches. Furthermore, the benefits are obtained while preserving the sparse structure of the systems. These results highlight the suitability of the proposed approach for large scale problems.     

Solution of finite systems of equations by interval iteration

In actual practice, iteration methods applied to the solution of finite systems of equations yield inconclusive results as to the existence or nonexistence of solutions and the accuracy of any approximate solutions obtained. On the other hand, construction of interval extensions of ordinary iteration operators permits one to carry out interval iteration computationally, with results which can give rigorous guarantees of existence or nonexistence of solutions, and error bounds for approximate solutions. Examples are given of the solution of a nonlinear system of equations and the calculation of eigenvalues and eigenvectors of a matrix by interval iteration. Several ways to obtain lower and upper bounds for eigenvalues are given.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041.     

On the approximation of derivatives using divided difference operators preserving the local convergence order of iterative methods

A development of an inverse first-order divided difference operator for functions of several variables is presented. Two generalized derivative-free algorithms built up from Ostrowski’s method for solving systems of nonlinear equations are written and analyzed. A direct computation of the local order of convergence for these variants of Ostrowski’s method is given. In order to preserve the local order of convergence, any divided difference operator is not valid. Two counterexamples of computation of a classical divided difference operator without preserving the order are presented. A rigorous study to know a priori if the new method will preserve the order of the original modified method is presented. The conclusion is that this fact does not depend on the method but on the systems of equations and if the associated divided difference verifies a particular condition. A new divided difference operator solving this problem is proposed. Furthermore, a computation that approximates the order of convergence is generated for the examples and it confirms in a numerical way that the order of the methods is well deduced. This study can be applied directly to other Newton’s type methods where derivatives are approximated by divided differences.     

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.     

Adaptive polynomial preconditioning for hermitian indefinite linear systems

This paper explores the use of polynomial preconditioned CG methods for hermitian indefinite linear systems,Ax=b. Polynomial preconditioning is attractive for several reasons. First, it is well-suited to vector and/or parallel architectures. It is also easy to employ, requiring only matrix-vector multiplication and vector addition. To obtain an optimum polynomial preconditioner we solve a minimax approximation problem. The preconditioning polynomial,C(), is optimum in that it minimizes a bound on the condition number of the preconditioned matrix,C(A)A. We also characterize the behavior of this minimax polynomial, which makes possible a thorough understanding of the associated CG methods. This characterization is also essential to the development of an adaptive procedure for dynamically determining the optimum polynomial preconditioner. Finally, we demonstrate the effectiveness of polynomial preconditioning in a variety of numerical experiments on a Cray X-MP/48. Our results suggest that high degree (20–50) polynomials are usually best.This research was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Dept. of Energy, by Lawrence Livermore National Laboratory under contract W-7405-ENG-48.This research was supported in part by the Dept. of Energy and the National Science Foundation under grant DMS 8704169.This research was supported in part by U.S. Dept. of Energy grant DEFG02-87ER25026 and by National Science Foundation grant DMS 8703226.