Approximate iterations for structured matrices

Important matrix-valued functions f (A) are, e.g., the inverse A ⁻¹, the square root and the sign function. Their evaluation for large matrices arising from pdes is not an easy task and needs techniques exploiting appropriate structures of the matrices A and f (A) (often f (A) possesses this structure only approximately). However, intermediate matrices arising during the evaluation may lose the structure of the initial matrix. This would make the computations inefficient and even infeasible. However, the main result of this paper is that an iterative fixed-point like process for the evaluation of f (A) can be transformed, under certain general assumptions, into another process which preserves the convergence rate and benefits from the underlying structure. It is shown how this result applies to matrices in a tensor format with a bounded tensor rank and to the structure of the hierarchical matrix technique. We demonstrate our results by verifying all requirements in the case of the iterative computation of A ⁻¹ and . This work was performed during the stay of the third author at the Max-Planck-Institute for Mathematics in the Sciences (Leipzig) and also supported by the Russian Fund of Basic Research (grants 05-01-00721, 04-07-90336) and a Priority Research Grant of the Department of Mathematical Sciences of the Russian Academy of Sciences.     

Krylov sequences of maximal length and convergence of GMRES

In most practical cases, the convergence of the GMRES method applied to a linear algebraic systemAx=b is determined by the distribution of eigenvalues ofA. In theory, however, the information about the eigenvalues alone is not sufficient for determining the convergence. In this paper the previous work of Greenbaum et al. is extended in the following direction. It is given a complete parametrization of the set of all pairs {A, b} for which GMRES(A, b) generates the prescribed convergence curve while the matrixA has the prescribed eigenvalues. Moreover, a characterization of the right hand sidesb for which the GMRES(A, b) converges exactly inm steps, wherem is the degree of the minimal polynomial ofA, is given. This work was supported by AS CR Grant A2030706. Part of the work was performed while the third author visited Instituto di Analisi Numerica (IAN CNR).     

A stationary iterative pseudoinverse algorithm

Iterative methods applied to the normal equationsA ^T Ax=A ^T b are sometimes used for solving large sparse linear least squares problems. However, when the matrix is rank-deficient many methods, although convergent, fail to produce the unique solution of minimal Euclidean norm. Examples of such methods are the Jacobi and SOR methods as well as the preconditioned conjugate gradient algorithm. We analyze here an iterative scheme that overcomes this difficulty for the case of stationary iterative methods. The scheme combines two stationary iterative methods. The first method produces any least squares solution whereas the second produces the minimum norm solution to a consistent system. This work was supported by the Swedish Research Council for Engineering Sciences, TFR.     

Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

We study the solutions of Toeplitz systemsA _n x=b by the preconditioned conjugate gradient method. Then ×n matrixA _n is of the forma ₀ I+H _n wherea ₀ is a real number,I is the identity matrix andH _n is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrixC _n and the skew-circulant matrixS _n whereA _n =1/2(C _n +S _n ). The convergence rate of the iterative method depends on the distribution of the singular values of the matricesC ^–1 _n A_n andS ^–1 _n A _n . For Toeplitz matricesA _n with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility ofC _n andS _n and prove that the singular values ofC ^–1 _n A _n andS ^–1 _n A _n are clustered around 1 for largen. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.     

Matrices, moments and quadrature II; How to compute the norm of the error in iterative methods

In this paper, we study the numerical computation of the errors in linear systems when using iterative methods. This is done by using methods to obtain bounds or approximations of quadratic formsu ^T A ⁻¹ u whereA is a symmetric positive definite matrix andu is a given vector. Numerical examples are given for the Gauss-Seidel algorithm. Moreover, we show that using a formula for theA-norm of the error from Dahlquist, Golub and Nash [1978] very good bounds of the error can be computed almost for free during the iterations of the conjugate gradient method leading to a reliable stopping criterion. The work of the first author was partially supported by NSF Grant CCR-950539.     

Functions of a matrix and Krylov matrices

For a given nonderogatory matrix A, formulas are given for functions of A in terms of Krylov matrices of A. Relations between the coefficients of a polynomial of A and the generating vector of a Krylov matrix of A are provided. With the formulas, linear transformations between Krylov matrices and functions of A are introduced, and associated algebraic properties are derived. Hessenberg reduction forms are revisited equipped with appropriate inner products and related properties and matrix factorizations are given.     

Analysis of the generalized total least squares problemAX≈B when some columns ofA are free of error

Summary This paper studies the algebraic properties and perturbation theory of the generalized total least squares problem (GTLS)AXB in whichA =(A ₁,A ₂),A ₁ is free of error, and the error contained in (A ₂,B) is of the formEC withC a given nonsingular matrix. The problem was proposed by Van Huffel and Vandewalle in [15]. The solvability conditions, formulas for the GTLS solutions, their residuals, and the minimum norm correction matrices are obtained, and a perturbation theory for the GTLS problem is given.This author was supported by NSERC of Canada Grant No. A9236This author was supported by the National Natural Sciences Foundation, P.R. China. This work was carried out when this author was visiting the School of Computer Science. McGill University, Montreal, Quebec, Canada     

Convergence of block iterative methods for linear systems arising in the numerical solution of Euler equations

Summary We discuss block matrices of the formA=[A _ij ], whereA _ij is ak×k symmetric matrix,A _ij is positive definite andA _ij is negative semidefinite. These matrices are natural block-generalizations of Z-matrices and M-matrices. Matrices of this type arise in the numerical solution of Euler equations in fluid flow computations. We discuss properties of these matrices, in particular we prove convergence of block iterative methods for linear systems with such system matrices.     

Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations

Summary We introduce a class of n×n structured matrices which includes three well-known classes of generalized companion matrices: tridiagonal plus rank-one matrices (comrade matrices), diagonal plus rank-one matrices and arrowhead matrices. Relying on the structure properties of , we show that if A then A=RQ , where A=QR is the QR decomposition of A. This allows one to implement the QR iteration for computing the eigenvalues and the eigenvectors of any A with O(n) arithmetic operations per iteration and with O(n) memory storage. This iteration, applied to generalized companion matrices, provides new O(n²) flops algorithms for computing polynomial zeros and for solving the associated (rational) secular equations. Numerical experiments confirm the effectiveness and the robustness of our approach.The results of this paper were presented at the Workshop on Nonlinear Approximations in Numerical Analysis, June 22 – 25, 2003, Moscow, Russia, at the Workshop on Operator Theory and Applications (IWOTA), June 24 – 27, 2003, Cagliari, Italy, at the Workshop on Numerical Linear Algebra at Universidad Carlos III in Leganes, June 16 – 17, 2003, Leganes, Spain, at the SIAM Conference on Applied Linear Algebra, July 15 – 19, 2003, Williamsburg, VA and in the Technical Report [8]. This work was partially supported by MIUR, grant number 2002014121, and by GNCS-INDAM. This work was supported by NSF Grant CCR 9732206 and PSC CUNY Awards 66406-0033 and 65393-0034.     

Optimal preconditioners of a given sparsity pattern

We consider the problem of finding the symmetric positive definite preconditionerM of a given form- e.g., having nonzero elements only in specified positions — which minimizes the ratio of the largest to smallest eigenvalue ofM ^–1 A, for a given symmetric positive definitive matrixA. We show how this problem can be expressed as one of minimizing a convex function and how an optimization code can be used to solve the problem numerically. Results are presented showing optimal preconditioners of various sparsity patterns and comparing these to preconditioners that have been proposed in the literature. Several conjectures are made, based on results from the optimization code.This work was supported by the Advanced Research Projects Agency of the Department of Defense under contract F49620-87-C-0065 and by the Applied Mathematical Sciences Program of the U.S. Department of Energy under contract DE-AC02-76ER03077.     

On a class of matrices which arise in the numerical solution of Euler equations

Summary We study block matricesA=[A_ij], where every blockA _ij ^k,k is Hermitian andA _ii is positive definite. We call such a matrix a generalized H-matrix if its block comparison matrix is a generalized M-matrix. These matrices arise in the numerical solution of Euler equations in fluid flow computations and in the study of invariant tori of dynamical systems. We discuss properties of these matrices and we give some equivalent conditions for a matrix to be a generalized H-matrix.Research supported by the Graduiertenkolleg mathematik der Universität Bielefeld     

A practical termination criterion for the conjugate gradient method

The conjugate gradient method for the iterative solution of a set of linear equationsAx=b is essentially equivalent to the Lanczos method, which implies that approximations to certain eigen-values ofA can be obtained at low cost. In this paper it is shown how the smallest active eigenvalue ofA can be cheaply approximated, and the usefulness of this approximation for a practical termination criterion for the conjugate gradient method is studied. It is proved that this termination criterion is reliable in many relevant situations.     

Numerical behaviour of the modified gram-schmidt GMRES implementation

In [6] the Generalized Minimal Residual Method (GMRES) which constructs the Arnoldi basis and then solves the transformed least squares problem was studied. It was proved that GMRES with the Householder orthogonalization-based implementation of the Arnoldi process (HHA), see [9], is backward stable. In practical computations, however, the Householder orthogonalization is too expensive, and it is usually replaced by the modified Gram-Schmidt process (MGSA). Unlike the HHA case, in the MGSA implementation the orthogonality of the Arnoldi basis vectors is not preserved near the level of machine precision. Despite this, the MGSA-GMRES performs surprisingly well, and its convergence behaviour and the ultimately attainable accuracy do not differ significantly from those of the HHA-GMRES. As it was observed, but not explained, in [6], it is thelinear independence of the Arnoldi basis, not the orthogonality near machine precision, that is important. Until the linear independence of the basis vectors is nearly lost, the norms of the residuals in the MGSA implementation of GMRES match those of the HHA implementation despite the more significant loss of orthogonality. In this paper we study the MGSA implementation. It is proved that the Arnoldi basis vectors begin to lose their linear independenceonly after the GMRES residual norm has been reduced to almost its final level of accuracy, which is proportional to κ(A)ε, where κ(A) is the condition number ofA and ε is the machine precision. Consequently, unless the system matrix is very ill-conditioned, the use of the modified Gram-Schmidt GMRES is theoretically well-justified. This work was supported by the GA AS CR under grants 230401 and A 2030706, by the NSF grant Int 921824, and by the DOE grant DEFG0288ER25053. Part of the work was performed while the third author visited Department of Mathematics and Computer Science, Emory University, Atlanta, USA.     

Weighted max norms, splittings, and overlapping additive Schwarz iterations

Summary. Weighted max-norm bounds are obtained for Algebraic Additive Schwarz Iterations with overlapping blocks for the solution of Ax = b, when the coefficient matrix A is an M-matrix. The case of inexact local solvers is also covered. These bounds are analogous to those that exist using A-norms when the matrix A is symmetric positive definite. A new theorem concerning P-regular splittings is presented which provides a useful tool for the A-norm bounds. Furthermore, a theory of splittings is developed to represent Algebraic Additive Schwarz Iterations. This representation makes a connection with multisplitting methods. With this representation, and using a comparison theorem, it is shown that a coarse grid correction improves the convergence of Additive Schwarz Iterations when measured in weighted max norm. Received March 13, 1998 / Revised version received January 26, 1999     

Factoring matrices with a tree-structured sparsity pattern

Let A be a matrix whose sparsity pattern is a tree with maximal degree d_max. We show that if the columns of A are ordered using minimum degree on |A|+|A|^∗, then factoring A using a sparse LU with partial pivoting algorithm generates only O(d_maxn) fill, requires only O(d_maxn) operations, and is much more stable than LU with partial pivoting on a general matrix. We also propose an even more efficient and just-as-stable algorithm called sibling-dominant pivoting. This algorithm is a strict partial pivoting algorithm that modifies the column preordering locally to minimize fill and work. It leads to only O(n) work and fill. More conventional column pre-ordering methods that are based (usually implicitly) on the sparsity pattern of |A|^∗|A| are not as efficient as the approaches that we propose in this paper.     

Quadratically constrained least squares and quadratic problems

Summary We consider the following problem: Compute a vectorx such that Ax–b₂=min, subject to the constraint x₂=. A new approach to this problem based on Gauss quadrature is given. The method is especially well suited when the dimensions ofA are large and the matrix is sparse.It is also possible to extend this technique to a constrained quadratic form: For a symmetric matrixA we consider the minimization ofx ^T A x–2b ^T x subject to the constraint x₂=.Some numerical examples are given.This work was in part supported by the National Science Foundation under Grant DCR-8412314 and by the National Institute of Standards and Technology under Grant 60NANB9D0908.     

Solution of augmented linear systems using orthogonal factorizations

We consider solvingx+Ay=b andA ^T x=c for givenb, c andm ×n A of rankn. This is called the augmented system formulation (ASF) of two standard optimization problems, which include as special cases the minimum 2-norm of a linear underdetermined system (b=0) and the linear least squares problem (c=0), as well as more general problems. We examine the numerical stability of methods (for the ASF) based on the QR factorization ofA, whether by Householder transformations, Givens rotations, or the modified Gram-Schmidt (MGS) algorithm, and consider methods which useQ andR, or onlyR. We discuss the meaning of stability of algorithms for the ASF in terms of stability of algorithms for the underlying optimization problems.We prove the backward stability of several methods for the ASF which useQ andR, inclusing a new one based on MGS, and also show under what circumstances they may be regarded as strongly stable. We show why previous methods usingQ from MGS were not backward stable, but illustrate that some of these methods may be acceptable-error stable. We point out that the numerical accuracy of methods that do not useQ does not depend to any significant extent on which of of the above three QR factorizations is used. We then show that the standard methods which do not useQ are not backward stable or even acceptable-error stable for the general ASF problem, and discuss how iterative refinement can be used to counteract these deficiencies.Dedicated to Carl-Eric Fröberg on the occasion of his 75th birthdayThis research was partially supported by NSERC of Canada Grant No. A9236.     

A numerical procedure for computing the Moore-Penrose inverse

An algorithm for computing the Moore-Penrose inverse of an arbitraryn×m real matrixA is presented which uses a Gram-Schmidt like procedure to form anA-orthogonal set of vectors which span the subspace perpendicular to the kernel ofA. This one procedure will work for any value ofn andm, and for any value of rank (A).     

A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations

Summary We present here a new hybrid method for the iterative solution of large sparse nonsymmetric systems of linear equations, say of the formAx=b, whereA ^{N, N} , withA nonsingular, andb ^N are given. This hybrid method begins with a limited number of steps of the Arnoldi method to obtain some information on the location of the spectrum ofA, and then switches to a Richardson iterative method based on Faber polynomials. For a polygonal domain, the Faber polynomials can be constructed recursively from the parameters in the Schwarz-Christoffel mapping function. In four specific numerical examples of non-normal matrices, we show that this hybrid algorithm converges quite well and is approximately as fast or faster than the hybrid GMRES or restarted versions of the GMRES algorithm. It is, however, sensitive (as other hybrid methods also are) to the amount of information on the spectrum ofA acquired during the first (Arnoldi) phase of this procedure.     

The product-product singular value decomposition of matrix triplets

A new decomposition of a matrix triplet (A, B, C) corresponding to the singular value decomposition of the matrix productABC is developed in this paper, which will be termed theProduct-Product Singular Value Decomposition (PPSVD). An orthogonal variant of the decomposition which is more suitable for the purpose of numerical computation is also proposed. Some geometric and algebraic issues of the PPSVD, such as the variational and geometric interpretations, and uniqueness properties are discussed. A numerical algorithm for stably computing the PPSVD is given based on the implicit Kogbetliantz technique. A numerical example is outlined to demonstrate the accuracy of the proposed algorithm.The work was partially supported by NSF grant DCR-8412314.