Updating incomplete factorization preconditioners for model order reduction

When solving a sequence of related linear systems by iterative methods, it is common to reuse the preconditioner for several systems, and then to recompute the preconditioner when the matrix has changed significantly. Rather than recomputing the preconditioner from scratch, it is potentially more efficient to update the previous preconditioner. Unfortunately, it is not always known how to update a preconditioner, for example, when the preconditioner is an incomplete factorization. A recently proposed iterative algorithm for computing incomplete factorizations, however, is able to exploit an initial guess, unlike existing algorithms for incomplete factorizations. By treating a previous factorization as an initial guess to this algorithm, an incomplete factorization may thus be updated. We use a sequence of problems from model order reduction. Experimental results using an optimized GPU implementation show that updating a previous factorization can be inexpensive and effective, making solving sequences of linear systems a potential niche problem for the iterative incomplete factorization algorithm.     

A multilevel block incomplete cholesky preconditioner for solving normal equations in linear least squares problems

An incomplete factorization method for preconditioning symmetric positive definite matrices is introduced to solve normal equations. The normal equations are form to solve linear least squares problems. The procedure is based on a block incomplete Cholesky factorization and a multilevel recursive strategy with an approximate Schur complement matrix formed implicitly. A diagonal perturbation strategy is implemented to enhance factorization robustness. The factors obtained are used as a preconditioner for the conjugate gradient method. Numerical experiments are used to show the robustness and efficiency of this preconditioning technique, and to compare it with two other preconditioners.     

On Axelsson's perturbations

A nice perturbation technique was introduced by Axelsson and further developed by Gustafsson to prove that factorization iterative methods are able, under appropriate conditions, to reach a convergence rate larger by an order of magnitude than that of classical schemes. Gustafsson observed however that the perturbations introduced to prove this result seemed actually unnecessary to reach it in practice. In the present work, on the basis of eigenvalue bounds recently obtained by the author, we offer an alternative approach which brings a partial confirmation of Gustafsson's conjecture.     

非对称稀疏线性方程组的快速外存解法及其在无网格法计算中的应用

针对局部Petrov-Galerkin无网格法(MLPG)等无网格方法的计算所产生的大型非对称稀疏线性方程组,介绍了一种新的直接解法．与一般非对称求解过程不同,该解法从现有的对称正定解法中演变出来,其分解过程在矩阵的上、下三角阵中对称进行．新的矩阵分解算法可以通过修改对称矩阵分解算法的代码来实现,这提供了从对称解法到非对称解法的快捷转换．还针对MLGP法以及有限元法所产生的方程组开发了多块外存算法(multi-blocked out-of-core strategy)来扩大求解规模．测试结果证明该方法大幅度提高了大型非对称稀疏线性方程组的求解速度．     

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 variant of block incomplete factorization preconditioners for a symmetricH-matrix

We propose a variant of parallel block incomplete factorization preconditioners for a symmetric block-tridiagonalH-matrix. Theoretical properties of these block preconditioners are compared with those of block incomplete factorization preconditioners for the corresponding comparison matrix. Numerical results of the preconditioned CG(PCG) method using these block preconditioners are compared with those of PCG using other types of block incomplete factorization preconditioners. Lastly, parallel computations of the block incomplete factorization preconditioners are carried out on the Cray C90.     

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.     

The importance of structure in incomplete factorization preconditioners

In this paper, we consider level-based preconditioning, which is one of the basic approaches to incomplete factorization preconditioning of iterative methods. It is well-known that while structure-based preconditioners can be very useful, excessive memory demands can limit their usefulness. Here we present an improved strategy that considers the individual entries of the system matrix and restricts small entries to contributing to fewer levels of fill than the largest entries. Using symmetric positive-definite problems arising from a wide range of practical applications, we show that the use of variable levels of fill can yield incomplete Cholesky factorization preconditioners that are more efficient than those resulting from the standard level-based approach. The concept of level-based preconditioning, which is based on the structural properties of the system matrix, is then transferred to the numerical incomplete decomposition. In particular, the structure of the incomplete factorization determined in the symbolic factorization phase is explicitly used in the numerical factorization phase. Further numerical results demonstrate that our level-based approach can lead to much sparser but efficient incomplete factorization preconditioners.     

Conditioning analysis of block incomplete factorizations and its application to elliptic equations

Summary. The paper deals with eigenvalue estimates for block incomplete factorization methods for symmetric matrices. First, some previous results on upper bounds for the maximum eigenvalue of preconditioned matrices are generalized to each eigenvalue. Second, upper bounds for the maximum eigenvalue of the preconditioned matrix are further estimated, which presents a substantial improvement of earlier results. Finally, the results are used to estimate bounds for every eigenvalue of the preconditioned matrices, in particular, for the maximum eigenvalue, when a modified block incomplete factorization is used to solve an elliptic equation with variable coefficients in two dimensions. The analysis yields a new upper bound of type for the condition number of the preconditioned matrix and shows clearly how the coefficients of the differential equation influence the positive constant . Received March 27, 1996 / Revised version received December 27, 1996     

Pivoting strategy for rank-one modification ofLDM t-like factorization

The rank-one modification algorithm of theLDM ^t factorization was given by Bennett [1]. His method, however, could break down even when the matrix is nonsingular and well-conditioned. We introduce a pivoting strategy for avoiding possible break-down as well as for suppressing error growth in the modification process. The method is based on a symbolic formula of the rank-one modification of the factorization of a possibly singular nonsymmetric matrix. A new symbolic formula is also obtained for the inverses of the factor matrices. Repeated application of our method produces theLDM ^t-like product form factorization of a matrix. A numerical example is given to illustrate our pivoting method. An incomplete factorization algorithm is also introduced for updating positive definite matrix useful in quasi-Newton methods, in which the Fletcher and Powell algorithm [2] and the Gill, Murray and Saunders algorithm [4] are usually used.This paper is presented at the Japan SIAM Annual Meeting held at University of Tokyo, Japan, October 7–9, 1991.     

The effect of ordering on preconditioned conjugate gradients

We investigate the effect of the ordering of the unknowns on the convergence of the preconditioned conjugate gradient method. We examine a wide range of ordering methods including nested dissection, minimum degree, and red-black and consider preconditionings without fill-in. We show empirically that there can be a significant difference in the number of iterations required by the conjugate gradient method and suggest reasons for this marked difference in performance.We also consider the effect of orderings when an incomplete factorization which allows some fill-in is performed. We consider the effect of automatically controlling the sparsity of the incomplete factorization through drop tolerances and level of fill-in.     

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.     

Numerical study on incomplete orthogonal factorization preconditioners

We design, analyse and test a class of incomplete orthogonal factorization preconditioners constructed from Givens rotations, incorporating some dropping strategies and updating tricks, for the solution of large sparse systems of linear equations. Comprehensive accounts about how the preconditioners are coded, what storage is required and how the computation is executed for a given accuracy are presented. A number of numerical experiments show that these preconditioners are competitive with standard incomplete triangular factorization preconditioners when they are applied to accelerate Krylov subspace iteration methods such as GMRES and BiCGSTAB.     

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     

Weighted graph based ordering techniques for preconditioned conjugate gradient methods

We describe the basis of a matrix ordering heuristic for improving the incomplete factorization used in preconditioned conjugate gradient techniques applied to anisotropic PDE's. Several new matrix ordering techniques, derived from well-known algorithms in combinatorial graph theory, which attempt to implement this heuristic, are described. These ordering techniques are tested against a number of matrices arising from linear anisotropic PDE's, and compared with other matrix ordering techniques. A variation of RCM is shown to generally improve the quality of incomplete factorization preconditioners.This work was supported by by the Natural Sciences and Engineering Research Council of Canada, and by the Information Technology Research Center, which is funded by the Province of Ontario.     

Combination of numerical and structured approaches to the construction of a second-order incomplete triangular factorization in parallel preconditioning methods

Parallel versions of the stabilized second-order incomplete triangular factorization conjugate gradient method in which the reordering of the coefficient matrix corresponding to the ordering based on splitting into subdomains with separators are considered. The incomplete triangular factorization is organized using the truncation of fill-in “by value” at internal nodes of subdomains, and “by value” and ‘by positions” on the separators. This approach is generalized for the case of constructing a parallel version of preconditioning the second-order incomplete LU factorization for nonsymmetric diagonally dominant matrices with. The reliability and convergence rate of the proposed parallel methods is analyzed. The proposed algorithms are implemented using MPI, results of solving benchmark problems with matrices from the collection of the University of Florida are presented.     

Preconditioner based on the Sherman-Morrison formula for regularized least squares problems

We propose a sparse approximate inverse preconditioner based on the Sherman-Morrison formula for Tikhonov regularized least square problems. Theoretical analysis shows that, the factorization method can take the advantage of the symmetric property of the coefficient matrix and be implemented cheaply. Combined with dropping rules, the incomplete factorization leads to a preconditioner for Krylov iterative methods to solve regularized least squares problems. Numerical experiments show that our preconditioner is competitive compared to existing methods, especially for ill-conditioned and rank deficient least squares problems.     

基于时序矩阵分解的缺失销售数据估计

企业的历史销售记录是供应链优化研究的基础数据来源,然而,在日常的研究中,几乎所有可以通过公开途径获得的销售记录都是高度不完整的,这为研究者开展工作带来了极大的不便。为解决此问题,本文提出,以销售数据集中已有的数据为基础,使用面向时序数据的矩阵分解模型MAFTIS对其缺失的部分进行估算,从而把残缺的数据集补全完整。进一步地,为提高MAFTIS的计算效率,本文还为该模型设计了一种基于交替最小二乘法的求解策略MAFTIS^ALS。在评估实验中,MAFTIS^ALS被用于三个真实销售数据集的缺失记录估计,结果显示,与其它估计模型相比,MAFTIS^ALS能获得更准确的估计结果,并且具有更高的收敛速度。     

On the rate of convergence of the preconditioned conjugate gradient method

Summary We derive new estimates for the rate of convergence of the conjugate gradient method by utilizing isolated eigenvalues of parts of the spectrum. We present a new generalized version of an incomplete factorization method and compare the derived estimates of the number of iterations with the number actually found for some elliptic difference equations and for a similar problem with a model empirical distribution function.     

A nearly optimal preconditioning based on recursive red–black orderings

Considering matrices obtained by the application of a five-point stencil on a 2D rectangular grid, we analyse a preconditioning method introduced by Axelsson and Eijkhout, and by Brand and Heinemann. In this method, one performs a (modified) incomplete factorization with respect to a so-called ‘repeated’ or ‘recursive’ red–black ordering of the unknowns while fill-in is accepted provided that the red unknowns in a same level remain uncoupled. Considering discrete second order elliptic PDEs with isotropic coefficients, we show that the condition number is bounded by 𝒪(n ${}^{\text{½ log}{}_{\text{2}}\text{(√(5) −1)}}$ ) where n is the total number of unknowns (½ log₂(√(5) − 1) = 0.153), and thus, that the total arithmetic work for the solution is bounded by 𝒪(n^1.077). Our condition number estimate, which turns out to be better than standard 𝒪(log² n) estimates for any realistic problem size, is purely algebraic and holds in the presence of Neumann boundary conditions and/or discontinuities in the PDE coefficients. Numerical tests are reported, displaying the efficiency of the method and the relevance of our analysis. © 1997 John Wiley & Sons, Ltd.