Eigenvalue bounds for block preconditioned matrices

In the symmetric positive definite case, two-sided eigenvalue bounds for block Jacobi scaled matrices and upper eigenvalue bounds for matrices preconditioned with an incomplete block factorization are derived. A quantitative characterization of block matrix partitionings is also suggested, which can be used when analyzing various block preconditioning methods. Bibliography: 13 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 5–41.     

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     

Eigenvalue estimates for a preconditioned Galerkin matrix arising from mixed finite element discretizations of viscous incompressible flows

The article deals with Galerkin matrices arising with finite element discretizations of the Navier–Stokes system. Usually these matrices are indefinite and nonsymmetric. They have to be preconditioned if a related linear system is to be solved efficiently by an iterative method. We consider preconditioning by a pressure mass matrix. It is shown how upper and lower bounds of the eigenvalues of a preconditioned Galerkin matrix may be found by variational arguments.     

Preconditioned iterative methods for a class of nonlinear eigenvalue problems

This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem.     

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.     

Parameterized preconditioning for generalized saddle point problems arising from the Stokes equation

A parameterized preconditioning framework is proposed to improve the conditions of the generalized saddle point problems. Based on the eigenvalue estimates for the generalized saddle point matrices, a strategy to minimize the upper bounds of the spectral condition numbers of the matrices is given, and the explicit expression of the quasi-optimal preconditioning parameter is obtained. In numerical experiment, parameterized preconditioning techniques are applied to the generalized saddle point problems derived from the mixed finite element discretization of the stationary Stokes equation. Numerical results demonstrate that the involved preconditioning procedures are efficient.     

Componentwise error analysis for the block LU factorization of totally nonnegative matrices

For the first time, perturbation bounds including componentwise perturbation bounds for the block LU factorization have been provided by Dopico and Molera (2005) [5]. In this paper, componentwise error analysis is presented for computing the block LU factorization of nonsingular totally nonnegative matrices. We present a componentwise bound on the equivalent perturbation for the computed block LU factorization. Consequently, combining with the componentwise perturbation results we derive componentwise forward error bounds for the computed block factors.     

Block LU factorizations of M–matrices

Summary. It is well known that any nonsingular M–matrix admits an LU factorization into M–matrices (with L and U lower and upper triangular respectively) and any singular M–matrix is permutation similar to an M–matrix which admits an LU factorization into M–matrices. Varga and Cai establish necessary and sufficient conditions for a singular M–matrix (without permutation) to allow an LU factorization with L nonsingular. We generalize these results in two directions. First, we find necessary and sufficient conditions for the existence of an LU factorization of a singular M-matrix where L and U are both permitted to be singular. Second, we establish the minimal block structure that a block LU factorization of a singular M–matrix can have when L and U are M–matrices. Received November 21, 1994 / Revised version received August 4, 1997     

Constraint preconditioning for nonsymmetric indefinite linear systems

This paper introduces and presents theoretical analyses of constraint preconditioning via a Schilders'‐like factorization for nonsymmetric saddle‐point problems. We extend the Schilders' factorization of a constraint preconditioner to a nonsymmetric matrix by using a different factorization. The eigenvalue and eigenvector distributions of the preconditioned matrix are determined. The choices of the parameter matrices in the extended Schilders' factorization and the implementation of the preconditioning step are discussed. An upper bound on the degree of the minimum polynomial for the preconditioned matrix and the dimension of the corresponding Krylov subspace are determined, as well as the convergence behavior of a Krylov subspace method such as GMRES. Numerical experiments are presented. Copyright © 2009 John Wiley & Sons, Ltd.     

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.     

Block ILU Preconditioners for a Nonsymmetric Block-Tridiagonal M-Matrix

We propose block ILU (incomplete LU) factorization preconditioners for a nonsymmetric block-tridiagonal M-matrix whose computation can be done in parallel based on matrix blocks. Some theoretical properties for these block ILU factorization preconditioners are studied and then we describe how to construct them effectively for a special type of matrix. We also discuss a parallelization of the preconditioner solver step used in nonstationary iterative methods with the block ILU preconditioners. Numerical results of the right preconditioned BiCGSTAB method using the block ILU preconditioners are compared with those of the right preconditioned BiCGSTAB using a standard ILU factorization preconditioner to see how effective the block ILU preconditioners are.     

Complexity reduction of least squares problems involving special vandermonde matrices

This paper presents a new QRD factorization of a rectangular Vandermonde matrix for a special point distribution, including the symmetric case, based on ak-dimensional block decomposition of the matrix and some properties of the Kronecker product. The computational reduction factor with respect to any QR method isk ², in the general case, and 4 in the symmetric one. By the resulting matrix factorization, new formulas are devised for the least squares system solution, whose implementation produces an algorithm of reduced computational cost and computer storage. Finally the perturbation bounds of this new factorization are devised.     

A tearing-based hybrid parallel sparse linear system solver

We propose a hybrid sparse system solver for handling linear systems using algebraic domain decomposition-based techniques. The solver consists of several stages. The first stage uses a reordering scheme that brings as many of the largest matrix elements as possible closest to the main diagonal. This is followed by partitioning the coefficient matrix into a set of overlapped diagonal blocks that contain most of the largest elements of the coefficient matrix. The only constraint here is to minimize the size of each overlap. Separating these blocks into independent linear systems with the constraint of matching the solution parts of neighboring blocks that correspond to the overlaps, we obtain a balance system. This balance system is not formed explicitly and has a size that is much smaller than the original system. Our novel solver requires only a one-time factorization of each diagonal block, and in each outer iteration, obtaining only the upper and lower tips of a solution vector where the size of each tip is equal to that of the individual overlap. This scheme proves to be scalable on clusters of nodes in which each node has a multicore architecture. Numerical experiments comparing the scalability of our solver with direct and preconditioned iterative methods are also presented.     

The {\cal {D Q R}} algorithm, basic theory, convergence, and conditional stability

Summary. We describe a fast matrix eigenvalue algorithm that uses a matrix factorization and reverse order multiply technique involving three factors and that is based on the symmetric matrix factorization as well as on –orthogonal reduction techniques where is computed from the given matrix . It operates on a similarity reduction of a real matrix to general tridiagonal form and computes all of 's eigenvalues in operations, where the part of the operations is possibly performed over , instead of the 7–8 real flops required by the eigenvalue algorithm. Potential breakdo wn of the algorithm can occur in the reduction to tridiagonal form and in the –orthogonal reductions. Both, however, can be monitored during the computations. The former occurs rather rarely for dimensions and can essentially be bypassed, while the latter is extremely rare and can be bypassed as well in our conditionally stable implementation of the steps. We prove an implicit theorem which allows implicit shifts, give a convergence proof for the algorithm and show that is conditionally stable for general balanced tridiagonal matrices . Received April 25, 1995 / Revised version received February 9, 1996     

The Lidskii-Mirsky-Wielandt theorem – additive and multiplicative versions

Summary. We use a simple matrix splitting technique to give an elementary new proof of the Lidskii-Mirsky-Wielandt Theorem and to obtain a multiplicative analog of the Lidskii-Mirsky-Wielandt Theorem, which we argue is the fundamental bound in the study of relative perturbation theory for eigenvalues of Hermitian matrices and singular values of general matrices. We apply our bound to obtain numerous bounds on the matching distance between the eigenvalues and singular values of matrices. Our results strengthen and generalize those in the literature. Received November 20, 1996 / Revised version received January 27, 1998     

Direct and iterative solution of the generalized Dirichlet–Neumann map for elliptic PDEs on square domains

In this work we derive the structural properties of the Collocation coefficient matrix associated with the Dirichlet–Neumann map for Laplace’s equation on a square domain. The analysis is independent of the choice of basis functions and includes the case involving the same type of boundary conditions on all sides, as well as the case where different boundary conditions are used on each side of the square domain. Taking advantage of said properties, we present efficient implementations of direct factorization and iterative methods, including classical SOR-type and Krylov subspace (Bi-CGSTAB and GMRES) methods appropriately preconditioned, for both Sine and Chebyshev basis functions. Numerical experimentation, to verify our results, is also included.     

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.     

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.     

On the analysis of the unsymmetric successive overrelaxation method when applied top-cyclic matrices

Summary A Determinantal Invariance, associated with consistently ordered weakly cyclic matrices, is given. The DI is then used to obtain a new functional equation which relates the eigenvalues of a particular block Jacobi iteration matrix to the eigenvalues of its associated Unsymmetric Successive Overrelaxation (USSOR) iteration matrix. This functional equation as well as the theory of nonnegative matrices and regular splittings are used to obtain convergence and divergence regions of the USSOR method.     

Using the Sherman-Morrison-Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems

A fast numerical algorithm for solving systems of linear equations with tridiagonal block Toeplitz matrices is presented. The algorithm is based on a preliminary factorization of the generating quadratic matrix polynomial associated with the Toeplitz matrix, followed by the Sherman-Morrison-Woodbury inversion formula and solution of two bidiagonal and one diagonal block Toeplitz systems. Tight estimates of the condition numbers are provided for the matrix system and the main matrix systems generated during the preliminary factorization. The emphasis is put on rigorous stability analysis to rounding errors of the Sherman-Morrison-Woodbury inversion. Numerical experiments are provided to illustrate the theory.