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 numerical study of optimized sparse preconditioners

Preconditioning strategies based on incomplete factorizations and polynomial approximations are studied through extensive numerical experiments. We are concerned with the question of the optimal rate of convergence that can be achieved for these classes of preconditioners.Our conclusion is that the well-known Modified Incomplete Cholesky factorization (MIC), cf. e.g., Gustafsson [20], and the polynomial preconditioning based on the Chebyshev polynomials, cf. Johnson, Micchelli and Paul [22], have optimal order of convergence as applied to matrix systems derived by discretization of the Poisson equation. Thus for the discrete two-dimensional Poisson equation withn unknowns,O(n ^1/4) andO(n ^1/2) seem to be the optimal rates of convergence for the Conjugate Gradient (CG) method using incomplete factorizations and polynomial preconditioners, respectively. The results obtained for polynomial preconditioners are in agreement with the basic theory of CG, which implies that such preconditioners can not lead to improvement of the asymptotic convergence rate.By optimizing the preconditioners with respect to certain criteria, we observe a reduction of the number of CG iterations, but the rates of convergence remain unchanged.Supported by The Norwegian Research Council for Science and the Humanities (NAVF) under grants no. 413.90/002 and 412.93/005.Supported by The Royal Norwegian Council for Scientific and Industrial Research (NTNF) through program no. STP.28402: Toolkits in industrial mathematics.     

A block algorithm for computing rank-revealing QR factorizations

We present a block algorithm for computing rank-revealing QR factorizations (RRQR factorizations) of rank-deficient matrices. The algorithm is a block generalization of the RRQR-algorithm of Foster and Chan. While the unblocked algorithm reveals the rank by peeling off small singular values one by one, our algorithm identifies groups of small singular values. In our block algorithm, we use incremental condition estimation to compute approximations to the nullvectors of the matrix. By applying another (in essence also rank-revealing) orthogonal factorization to the nullspace matrix thus created, we can then generate triangular blocks with small norm in the lower right part ofR. This scheme is applied in an iterative fashion until the rank has been revealed in the (updated) QR factorization. We show that the algorithm produces the correct solution, under very weak assumptions for the orthogonal factorization used for the nullspace matrix. We then discuss issues concerning an efficient implementation of the algorithm and present some numerical experiments. Our experiments show that the block algorithm is reliable and successfully captures several small singular values, in particular in the initial block steps. Our experiments confirm the reliability of our algorithm and show that the block algorithm greatly reduces the number of triangular solves and increases the computational granularity of the RRQR computation.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US Department of Energy, under Contract W-31-109-Eng-38. The second author was also sponsored by a travel grant from the Knud Højgaards Fond.This work was partially completed while the author was visiting the IBM Scientific Center in Heidelberg, Germany.     

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     

Multiple LU factorizations of a singular matrix

A singular matrix A may have more than one LU factorizations. In this work the set of all LU factorizations of A is explicitly described when the lower triangular matrix L is nonsingular. To this purpose, a canonical form of A under left multiplication by unit lower triangular matrices is introduced. This canonical form allows us to characterize the matrices that have an LU factorization and to parametrize all possible LU factorizations. Formulae in terms of quotient of minors of A are presented for the entries of this canonical form.     

Analysis of incomplete factorizations for a nine-point approximation to a convection–diffusion model problem

We study the stability of zero-fill incomplete LU factorizations of a nine-point coefficient matrix arising from a high-order compact discretisation of a two-dimensional constant-coefficient convection–diffusion problem. Nonlinear recurrences for computing entries of the lower and upper triangular matrices are derived and we show that the sequence of diagonal entries of the lower triangular factor is unconditionally convergent. A theoretical estimate of the limiting value is derived and we show that this estimate is a good predictor of the computed value. The unconditional convergence of the diagonal sequence of the lower triangular factor to a positive limit implies that the incomplete factorization process never encounters a zero pivot and that the other diagonal sequences are also convergent. The characteristic polynomials associated with the lower and upper triangular solves that occur during the preconditioning step are studied and conditions for the stability of the triangular solves are derived in terms of the entries of the tridiagonal matrices appearing in the lower and upper subdiagonals of the block triangular system matrix and a triplet of parameters which completely determines the solution of the nonlinear recursions. Results of ILU-preconditioned GMRES iterations and the effects of orderings on their convergence are also described.     

Refinement of Two-Factor Factorizations of a Linear Partial Differential Operator of Arbitrary Order and Dimension

Given a right factor and a left factor of a Linear Partial Differential Operator (LPDO), under which conditions we can refine these two-factor factorizations into one three-factor factorization? This problem is solved for LPDOs of arbitrary order and number of variables. A more general result for the incomplete factorizations of LPDOs is proved as well.     

Rank reduction, factorization and conjugation

We investigate the rank reduction procedure, related factorizations and conjugation algorithms. An exact characterization of the full rank factorization produced by the rank reduction algorithm is given. This result is then used to derive matrix decompositions and conjugation procedures.     

On algebraic multi-level methods for non-symmetric systems - Comparison results

We establish theoretical comparison results for algebraic multi-level methods applied to non-singular non-symmetric M-matrices. We consider two types of multi-level approximate block factorizations or AMG methods, the AMLI and the MAMLI method. We compare the spectral radii of the iteration matrices of these methods. This comparison shows, that the spectral radius of the MAMLI method is less than or equal to the spectral radius of the AMLI method. Moreover, we establish how the quality of the approximations in the block factorization effects the spectral radii of the iteration matrices. We prove comparisons results for different approximations of the fine grid block as well as for the used Schur complement. We also establish a theoretical comparison between the AMG methods and the classical block Jacobi and block Gauss-Seidel methods.     

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.     

A direct active set algorithm for large sparse quadratic programs with simple bounds

We show how a direct active set method for solving definite and indefinite quadratic programs with simple bounds can be efficiently implemented for large sparse problems. All of the necessary factorizations can be carried out in a static data structure that is set up before the numeric computation begins. The space required for these factorizations is no larger than that required for a single sparse Cholesky factorization of the Hessian of the quadratic. We propose several improvements to this basic algorithm: a new way to find a search direction in the indefinite case that allows us to free more than one variable at a time and a new heuristic method for finding a starting point. These ideas are motivated by the two-norm trust region problem. Additionally, we also show how projection techniques can be used to add several constraints to the active set at each iteration. Our experimental results show that an algorithm with these improvements runs much faster than the basic algorithm for positive definite problems and finds local minima with lower function values for indefinite problems.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000.     

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     

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.     

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.     

Modified block-approximate factorization strategies

Summary Two variants of modified incomplete block-matrix factorization with additive correction are proposed for the iterative solution of large linear systems of equations. Both rigorous theoretical support and numerical evidence are given displaying their efficiency when applied to discrete second order partial differential equations (PDEs), even in the case of quasi-singular problems.Research supported by the A.B.O.S. (A.G.C.D.) under project 11, within the co-operation between Belgium and Zaire     

Hybrid reordering strategies for ILU preconditioning of indefinite sparse matrices

Incomplete LU factorization preconditioning techniques often have difficulty on indefinite sparse matrices. We present hybrid reordering strategies to deal with such matrices, which include new diagonal reorderings that are in conjunction with a symmetric nondecreasing degree algorithm. We first use the diagonal reorderings to efficiently search for entries of single element rows and columns and/or the maximum absolute value to be placed on the diagonal for computing a nonsymmetric permutation. To augment the effectiveness of the diagonal reorderings, a nondecreasing degree algorithm is applied to reduce the amount of fill-in during the ILU factorization. With the reordered matrices, we achieve a noticeable improvement in enhancing the stability of incomplete LU factorizations. Consequently, we reduce the convergence cost of the preconditioned Krylov subspace methods on solving the reordered indefinite matrices.     

Experimental comparison of three-dimensional point and line modified incomplete factorizations

We examine how the variations of the coefficients of 3-dimensional (3D) partial differential equations (PDEs) influence the convergence of the conjugate gradient method, preconditioned by standard pointwise and linewise modified incomplete factorizations. General analytical spectral bounds obtained previously are applied, which displays the conditions under which good performances could be expected. The arguments also reveal that, if the total number of unknowns is very large or the number of unknowns in one direction is much larger than in both other ones, or if there are strong jumps in the variation of the PDE coefficients or fewer Dirichlet boundary conditions, then linewise preconditionings could be significantly more efficient than the corresponding pointwise ones. We also discuss reasons to explain why in the case of constant PDE coefficients, the advantage of preferring linewise methods to pointwise ones is not as pronounced as in 2D problems. Results of numerical experiments are reported. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the eigenvalue distribution of a class of preconditioning methods

Summary A class of preconditioning methods depending on a relaxation parameter is presented for the solution of large linear systems of equationAx=b, whereA is a symmetric positive definite matrix. The methods are based on an incomplete factorization of the matrixA and include both pointwise and blockwise factorization. We study the dependence of the rate of convergence of the preconditioned conjugate gradient method on the distribution of eigenvalues ofC ^–1 A, whereC is the preconditioning matrix. We also show graphic representations of the eigenvalues and present numerical tests of the methods.     

Incomplete factorizations of singular linear systems

Recent works have shown that, whenA is a Stieltjes matrix, its so-called modified incomplete factorizations provide effective preconditioning matrices for solvingAx=b by polynomially accelerated iterative methods. We extend here these results to the singular case with the conclusion that the latter techniques are able to solve singular systems at the same speed as regular systems.Research supported by the Fonds National de la Recherche Scientifique (Belgium) — Aspirant.     

连续代数扩域上多项式因式分解的Trager算法

多项式的因式分解是符号计算中最基本的算法,二十世纪六十年代开始出现的关于多项式因式分解的工作被认为是符号计算领域的起源．目前多项式的因式分解已经成熟,并已在Maple等符号计算软件中实现,但代数扩域上的因式分解算法还有待进一步改进．代数扩域上的基本算法是Trager算法．Weinberger等提出了基于Hensel提升的算法．这些算法是在单个扩域上做因式分解．而在吴零点分解定理中,多个代数扩域上的因式分解是非常基本的一步,主要用于不可约升列的计算．为了解决这一问题,吴文俊,胡森、王东明分别提出了基于方程求解的多个扩域上的因式分解算法．王东明、林东岱提出了另外一个算法Trager算法相似,将问题化为有理数域上的分解．他们应用了吴的三角化算法,因此算法的终止性依赖于吴方法的计算．支丽红则将提升技巧用于多个扩域上的因式分解算法．本文将Trager的算法直接推广为连续扩域上的因式分解,只涉及结式计算与有理数域上的因式分解,给出了多个代数扩域上的因式分解一个直接的算法．