ILUCP: a Crout ILU preconditioner with pivoting

We introduce a new preconditioner, ILUCP, to be used with an iterative method for solving sparse linear systems. It is based on an incomplete LU factorization combining Crout's formulation of Gaussian elimination with pivoting by columns. It is usually faster than ILUTP, which is based on a delayed update version of Gaussian elimination with pivoting, but requires more memory. For applications where memory is not a primary concern, ILUCP can be an attractive alternative to ILUTP. Copyright © 2005 John Wiley & Sons, Ltd.     

A multilevel Crout ILU preconditioner with pivoting and row permutation

In this paper, we present a new incomplete LU factorization using pivoting by columns and row permutation. Pivoting by columns helps to avoid small pivots and row permutation is used to promote sparsity. This factorization is used in a multilevel framework as a preconditioner for iterative methods for solving sparse linear systems. In most multilevel incomplete ILU factorization preconditioners, preprocessing (scaling and permutation of rows and columns of the coefficient matrix) results in further improvements. Numerical results illustrate that these preconditioners are suitable for a wide variety of applications. Copyright © 2007 John Wiley & Sons, Ltd.     

A robust algebraic multilevel preconditioner for non‐symmetric M‐matrices

Stable finite difference approximations of convection‐diffusion equations lead to large sparse linear systems of equations whose coefficient matrix is an M‐matrix, which is highly non‐symmetric when the convection dominates. For an efficient iterative solution of such systems, it is proposed to consider in the non‐symmetric case an algebraic multilevel preconditioning method formerly proposed for pure diffusion problems, and for which theoretical results prove grid independent convergence in this context. These results are supplemented here by a Fourier analysis that applies to constant coefficient problems with periodic boundary conditions whenever using an ‘idealized’ version of the two‐level preconditioner. Within this setting, it is proved that any eigenvalue λ of the preconditioned system satisfies for some real constant c such that . This result holds independently of the grid size and uniformly with respect to the ratio between convection and diffusion. Extensive numerical experiments are conducted to assess the convergence of practical two‐ and multi‐level schemes. These experiments, which include problems with highly variable and rotating convective flow, indicate that the convergence is grid independent. It deteriorates moderately as the convection becomes increasingly dominating, but the convergence factor remains uniformly bounded. This conclusion is supported for both uniform and some non‐uniform (stretched) grids. Copyright © 2000 John Wiley & Sons, Ltd.     

Multicolor low‐rank preconditioner for general sparse linear systems

This article presents a multilevel parallel preconditioning technique for solving general large sparse linear systems of equations. Subdomain coloring is invoked to reorder the coefficient matrix by multicoloring the adjacency graph of the subdomains, resulting in a two‐level block diagonal structure. A full binary tree structure $\mathrm{??}$ is then built to facilitate the construction of the preconditioner. A key property that is exploited is the observation that the difference between the inverse of the original matrix and that of its block diagonal approximation is often well approximated by a low‐rank matrix. This property and the block diagonal structure of the reordered matrix lead to a multicolor low‐rank (MCLR) preconditioner. The construction procedure of the MCLR preconditioner follows a bottom‐up traversal of the tree $\mathrm{??}$. All irregular matrix computations, such as ILU factorizations and related triangular solves, are restricted to leaf nodes where these operations can be performed independently. Computations in nonleaf nodes only involve easy‐to‐optimize dense matrix operations. In order to further reduce the number of iteration of the Preconditioned Krylov subspace procedure, we combine MCLR with a few classical block‐relaxation techniques. Numerical experiments on various test problems are proposed to illustrate the robustness and efficiency of the proposed approach for solving large sparse symmetric and nonsymmetric linear systems.     

Hierarchical Schur complement preconditioner for the stochastic Galerkin finite element methods

Use of the stochastic Galerkin finite element methods leads to large systems of linear equations obtained by the discretization of tensor product solution spaces along their spatial and stochastic dimensions. These systems are typically solved iteratively by a Krylov subspace method. We propose a preconditioner, which takes an advantage of the recursive hierarchy in the structure of the global matrices. In particular, the matrices posses a recursive hierarchical two‐by‐two structure, with one of the submatrices block diagonal. Each of the diagonal blocks in this submatrix is closely related to the deterministic mean‐value problem, and the action of its inverse is in the implementation approximated by inner loops of Krylov iterations. Thus, our hierarchical Schur complement preconditioner combines, on each level in the approximation of the hierarchical structure of the global matrix, the idea of Schur complement with loops for a number of mutually independent inner Krylov iterations, and several matrix–vector multiplications for the off‐diagonal blocks. Neither the global matrix nor the matrix of the preconditioner need to be formed explicitly. The ingredients include only the number of stiffness matrices from the truncated Karhunen–Loève expansion and a good preconditioned for the mean‐value deterministic problem. We provide a condition number bound for a model elliptic problem, and the performance of the method is illustrated by numerical experiments. Copyright © 2013 John Wiley & Sons, Ltd.     

Preconditioner updates for solving sequences of linear systems in matrix‐free environment

We present two new ways of preconditioning sequences of nonsymmetric linear systems in the special case where the implementation is matrix free. Both approaches are fully algebraic, they are based on the general updates of incomplete LU decompositions recently introduced in (SIAM J. Sci. Comput. 2007; 29 (5):1918–1941), and they may be directly embedded into nonlinear algebraic solvers. The first of the approaches uses a new model of partial matrix estimation to compute the updates. The second approach exploits separability of function components to apply the updated factorized preconditioner via function evaluations with the discretized operator. Experiments with matrix‐free implementations of test problems show that both new techniques offer useful, robust and black‐box solution strategies. In addition, they show that the new techniques are often more efficient in matrix‐free environment than either recomputing the preconditioner from scratch for every linear system of the sequence or than freezing the preconditioner throughout the whole sequence. Copyright © 2010 John Wiley & Sons, Ltd.     

A Class of Incomplete Orthogonal Factorization Methods. II: Implementation and Results

We present, implement and test several incomplete QR factorization methods based on Givens rotations for sparse square and rectangular matrices. For square systems, the approximate QR factors are used as right-preconditioners for GMRES, and their performance is compared to standard ILU techniques. For rectangular matrices corresponding to linear least-squares problems, the approximate R factor is used as a right-preconditioner for CGLS. A comprehensive discussion is given about the uses, advantages and shortcomings of the preconditioners. AMS subject classification (2000) 65F10, 65F25, 65F50.Received May 2002. Revised October 2004. Communicated by Åke Björck.     

Efficient parallel solution to large‐size sparse eigenproblems with block FSAI preconditioning

The choice of the preconditioner is a key factor to accelerate the convergence of eigensolvers for large‐size sparse eigenproblems. Although incomplete factorizations with partial fill‐in prove generally effective in sequential computations, the efficient preconditioning of parallel eigensolvers is still an open issue. The present paper describes the use of block factorized sparse approximate inverse (BFSAI) preconditioning for the parallel solution of large‐size symmetric positive definite eigenproblems with both a simultaneous Rayleigh quotient minimization and the Jacobi–Davidson algorithm. BFSAI coupled with a block diagonal incomplete decomposition proves a robust and efficient parallel preconditioner in a number of test cases arising from the finite element discretization of 3D fluid‐dynamical and mechanical engineering applications, outperforming FSAI even by a factor of 8 and exhibiting a satisfactory scalability. Copyright © 2011 John Wiley & Sons, Ltd.     

Overlapping Domain Decomposition Algorithms for General Sparse Matrices

Domain decomposition methods for finite element problems using a partition based on the underlying finite element mesh have been extensively studied. In this paper, we discuss algebraic extensions of the class of overlapping domain decomposition algorithms for general sparse matrices. The subproblems are created with an overlapping partition of the graph corresponding to the sparsity structure of the matrix. These algebraic domain decomposition methods are especially useful for unstructured mesh problems. We also discuss some difficulties encountered in the algebraic extension, particularly the issues related to the coarse solver.     

Local reconstruction of low‐rank matrices and subspaces

We study the problem of reconstructing a low‐rank matrix, where the input is an n × m matrix M over a field and the goal is to reconstruct a (near‐optimal) matrix that is low‐rank and close to M under some distance function Δ. Furthermore, the reconstruction must be local, i.e., provides access to any desired entry of by reading only a few entries of the input M (ideally, independent of the matrix dimensions n and m). Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010). Our main result is a local reconstruction algorithm for the case where Δ is the normalized Hamming distance (between matrices). Given M that is ‐close to a matrix of rank (together with d and ), this algorithm computes with high probability a rank‐d matrix that is ‐close to M. This is a local algorithm that proceeds in two phases. The preprocessing phase reads only random entries of M, and stores a small data structure. The query phase deterministically outputs a desired entry by reading only the data structure and 2d additional entries of M. We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When Δ is the normalized Hamming distance between vectors, we derive an algorithm that runs in polynomial time by applying our main result for matrix reconstruction. For comparison, when Δ is the truncated Euclidean distance and , we analyze sampling algorithms by using statistical learning tools. A preliminary version of this paper appears appears in ECCC, see: http://eccc.hpi-web.de/report/2015/128/ © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 607–630, 2017     

A note on simultaneous preconditioning and symmetrization of non‐symmetric linear systems

Motivated by the theory of self‐duality that provides a variational formulation and resolution for non‐self‐adjoint partial differential equations (Ann. Inst. Henri Poincaré (C) Anal Non Linéaire 2007; 24 :171–205; Selfdual Partial Differential Systems and Their Variational Principles. Springer: New York, 2008), we propose new templates for solving large non‐symmetric linear systems. The method consists of combining a new scheme that simultaneously preconditions and symmetrizes the problem, with various well‐known iterative methods for solving linear and symmetric problems. The approach seems to be efficient when dealing with certain ill‐conditioned, and highly non‐symmetric systems. The numerical and theoretical results are provided to show the efficiency of our approach. Copyright © 2010 John Wiley & Sons, Ltd.     

Wilkinson's inertia‐revealing factorization and its application to sparse matrices

We propose a new inertia‐revealing factorization for sparse symmetric matrices. The factorization scheme and the method for extracting the inertia from it were proposed in the 1960s for dense, banded, or tridiagonal matrices, but they have been abandoned in favor of faster methods. We show that this scheme can be applied to any sparse symmetric matrix and that the fill in the factorization is bounded by the fill in the sparse QR factorization of the same matrix (but is usually much smaller). We describe our serial proof‐of‐concept implementation and present experimental results, studying the method's numerical stability and performance.     

Schur complement‐based domain decomposition preconditioners with low‐rank corrections

This paper introduces a robust preconditioner for general sparse matrices based on low‐rank approximations of the Schur complement in a Domain Decomposition framework. In this ‘Schur Low Rank’ preconditioning approach, the coefficient matrix is first decoupled by a graph partitioner, and then a low‐rank correction is exploited to compute an approximate inverse of the Schur complement associated with the interface unknowns. The method avoids explicit formation of the Schur complement. We show the feasibility of this strategy for a model problem and conduct a detailed spectral analysis for the relation between the low‐rank correction and the quality of the preconditioner. We first introduce the SLR preconditioner for symmetric positive definite matrices and symmetric indefinite matrices if the interface matrices are symmetric positive definite. Extensions to general symmetric indefinite matrices as well as to nonsymmetric matrices are also discussed. Numerical experiments on general matrices illustrate the robustness and efficiency of the proposed approach. Copyright © 2016 John Wiley & Sons, Ltd.     

A preconditioned low‐rank CG method for parameter‐dependent Lyapunov matrix equations

This paper is concerned with the numerical solution of symmetric large‐scale Lyapunov equations with low‐rank right‐hand sides and coefficient matrices depending on a parameter. Specifically, we consider the situation when the parameter dependence is sufficiently smooth, and the aim is to compute solutions for many different parameter samples. On the basis of existing results for Lyapunov equations and parameter‐dependent linear systems, we prove that the tensor containing all solution samples typically allows for an excellent low multilinear rank approximation. Stacking all sampled equations into one huge linear system, this fact can be exploited by combining the preconditioned CG method with low‐rank truncation. Our approach is flexible enough to allow for a variety of preconditioners based, for example, on the sign function iteration or the alternating direction implicit method. Copyright © 2013 John Wiley & Sons, Ltd.     

A nearly optimal preconditioner for the Navier–Stokes equations

We present a preconditioner for the linearized Navier–Stokes equations which is based on the combination of a fast transform approximation of an advection diffusion problem together with the recently introduced ‘BFBT^T’ preconditioner of Elman (SIAM Journal of Scientific Computing, 1999; 20 :1299–1316). The resulting preconditioner when combined with an appropriate Krylov subspace iteration method yields the solution in a number of iterations which appears to be independent of the Reynolds number provided a mesh Péclet number restriction holds, and depends only mildly on the mesh size. The preconditioner is particularly appropriate for problems involving a primary flow direction. Copyright © 2001 John Wiley & Sons, Ltd.     

Algebraic interface‐based coarsening AMG preconditioner for multi‐scale sparse matrices with applications to radiation hydrodynamics computation

Coarsening is a crucial component of algebraic multigrid (AMG) methods for iteratively solving sparse linear systems arising from scientific and engineering applications. Its application largely determines the complexity of the AMG iteration operator. Usually, high operator complexities lead to fast convergence of the AMG method; however, they require additional memory and as such do not scale as well in parallel computation. In contrast, although low operator complexities improve parallel scalability, they often lead to deterioration in convergence. This study introduces a new type of coarsening strategy called algebraic interface‐based coarsening that yields a better balance between convergence and complexity for a class of multi‐scale sparse matrices. Numerical results for various model‐type problems and a radiation hydrodynamics practical application are provided to show the effectiveness of the proposed AMG solver.     

Improving the stability and robustness of incomplete symmetric indefinite factorization preconditioners

Sparse symmetric indefinite linear systems of equations arise in numerous practical applications. In many situations, an iterative method is the method of choice but a preconditioner is normally required for it to be effective. In this paper, the focus is on a class of incomplete factorization algorithms that can be used to compute preconditioners for symmetric indefinite systems. A limited memory approach is employed that incorporates a number of new ideas with the goal of improving the stability, robustness, and efficiency of the preconditioner. These include the monitoring of stability as the factorization proceeds and the incorporation of pivot modifications when potential instability is observed. Numerical experiments involving test problems arising from a range of real‐world applications demonstrate the effectiveness of our approach.     

A nonconvex approach to low‐rank matrix completion using convex optimization

This paper deals with the problem of recovering an unknown low‐rank matrix from a sampling of its entries. For its solution, we consider a nonconvex approach based on the minimization of a nonconvex functional that is the sum of a convex fidelity term and a nonconvex, nonsmooth relaxation of the rank function. We show that by a suitable choice of this nonconvex penalty, it is possible, under mild assumptions, to use also in this matrix setting the iterative forward–backward splitting method. Specifically, we propose the use of certain parameter dependent nonconvex penalties that with a good choice of the parameter value allow us to solve in the backward step a convex minimization problem, and we exploit this result to prove the convergence of the iterative forward–backward splitting algorithm. Based on the theoretical results, we develop for the solution of the matrix completion problem the efficient iterative improved matrix completion forward–backward algorithm, which exhibits lower computing times and improved recovery performance when compared with the best state‐of‐the‐art algorithms for matrix completion. Copyright © 2016 John Wiley & Sons, Ltd.     

A preconditioner for generalized saddle point problems: Application to 3D stationary Navier‐Stokes equations

In this article we consider the stationary Navier‐Stokes system discretized by finite element methods which do not satisfy the inf‐sup condition. These discretizations typically take the form of a variational problem with stabilization terms. Such a problem may be transformed by iteration methods into a sequence of linear, Oseen‐type variational problems. On the algebraic level, these problems belong to a certain class of linear systems with nonsymmetric system matrices (“generalized saddle point problems”). We show that if the underlying finite element spaces satisfy a generalized inf‐sup condition, these problems have a unique solution. Moreover, we introduce a block triangular preconditioner and we show how the eigenvalue bounds of the preconditioned system matrix depend on the coercivity constant and continuity bounds of the bilinear forms arising in the variational problem. Finally we prove that the stabilized P1‐P1 finite element method proposed by Rebollo is covered by our theory and we show that the condition number of the preconditioned system matrix is independent of the mesh size. Numerical tests with 3D stationary Navier‐Stokes flows confirm our results. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006     

An algebraic preconditioning method for M‐matrices: linear versus non‐linear multilevel iteration

In a recent work, the author introduced a robust multilevel incomplete factorization algorithm using spanning trees of matrix graphs (Proceedings of the 1999 International Conference on Preconditioning Techniques for Large Sparse Matrix Problems in Industrial Applications, Hubert H. Humphrey Center, University of Minnesota, 1999, 251–257). Based on this idea linear and non‐linear algebraic multilevel iteration (AMLI) methods are investigated in the present paper. In both cases, the preconditioner is constructed recursively from the coarsest to finer and finer levels. The considered W‐cycles only need diagonal solvers on all levels and additionally evaluate a second‐degree matrix polynomial (linear case), or, perform ν inner GCG‐type iterations (non‐linear case) on every other level. This involves the same type of preconditioner for the corresponding Schur complement. The non‐linear variant has the additional benefit of being free from any method parameters to be estimated. Based on the same type of approximation property similar convergence rates are obtained for linear and non‐linear AMLI, even for a very small number ν of inner iterations, e.g. ν =2,3. The presented methods are robust with respect to anisotropy and discontinuities in the coefficients of the PDEs and can also be applied to unstructured‐grid problems. Copyright © 2002 John Wiley & Sons, Ltd.