The condition number of real Vandermonde, Krylov and positive definite Hankel matrices

Summary. We show that the Euclidean condition number of any positive definite Hankel matrix of order may be bounded from below by with , and that this bound may be improved at most by a factor . Similar estimates are given for the class of real Vandermonde matrices, the class of row-scaled real Vandermonde matrices, and the class of Krylov matrices with Hermitian argument. Improved bounds are derived for the case where the abscissae or eigenvalues are included in a given real interval. Our findings confirm that all such matrices – including for instance the famous Hilbert matrix – are ill-conditioned already for “moderate” order. As application, we describe implications of our results for the numerical condition of various tasks in Numerical Analysis such as polynomial and rational i nterpolation at real nodes, determination of real roots of polynomials, computation of coefficients of orthogonal polynomials, or the iterative solution of linear systems of equations. Received December 1, 1997 / Revised version received February 25, 1999 / Published online 16 March 2000     

Fast accurate eigenvalue methods for graded positive definite matrices

Summary. Let where is a positive definite matrix and is diagonal and nonsingular. We show that if the condition number of is much less than that of then we can use algorithms based on the Cholesky factorization of to compute the eigenvalues of to high relative accuracy more efficiently than by Jacobi's method. The new methods are generally slower than tridiagonalization methods (which do not deliver the eigenvalues to maximal relative accuracy) but can be up to 4 times faster when the condition number of is very large. Received April 13, 1995     

Convergence of block two-stage iterative methods for symmetric positive definite systems

Summary. We study the convergence of two-stage iterative methods for solving symmetric positive definite (spd) systems. The main tool we used to derive the iterative methods and to analyze their convergence is the diagonally compensated reduction (cf. [1]). Received December 11, 1997 / Revised version received March 25, 1999 / Published online May 30, 2001     

A formula for the 2-norm distance from a matrix to the set of matrices with multiple eigenvalues

Summary. We prove that the 2-norm distance from an matrix A to the matrices that have a multiple eigenvalue is equal to where the singular values are ordered nonincreasingly. Therefore, the 2-norm distance from A to the set of matrices with multiple eigenvalues is Received February 19, 1998 / Revised version received July 15, 1998 / Published online: July 7, 1999     

On worst-case condition numbers of a nondefective multiple eigenvalue

Summary. This paper is a continuation of the author [6] in Numerische Mathematik. Let be a nondefective multiple eigenvalue of multiplicity of an complex matrix , and let be the secants of the canonical angles between the left and right invariant subspaces of corresponding to the multiple eigenvalue . The analysis of this paper shows that the quantities are the worst-case condition numbers of the multiple eigenvalue . Received September 28, 1992 / Revised version received January 18, 1994     

Symmetric Gaussian elimination for cauchy-type matrices with application to positive definite Toeplitz matrices

The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show that this new algorithm is fast and reliable. Received March 24, 1995 / Revised version received December 13, 1995     

On the distance to uncontrollability and the distance to instability and their relation to some condition numbers in control

Summary. According to the methodology of [6], many measures of distance arising in problems in numerical linear algebra and control can be bounded by a factor times the reciprocal of an appropriate condition number, where the distance is thought of as the distance between a given problem to the nearest ill-posed problem. In this paper, four major problems in numerical linear algebra and control are further considered: the computation of system Hessenberg form, the solution of the algebraic Riccati equation, the pole assignment problem and the matrix exponential. The distances considered here are the distance to uncontrollability and the distance to instability. Received November 4, 1995 / Revised version received March 4, 1996     

Computing the generalized singular values/vectors of large sparse or structured matrix pairs

Summary. We present a numerical algorithm for computing a few extreme generalized singular values and corresponding vectors of a sparse or structured matrix pair . The algorithm is based on the CS decomposition and the Lanczos bidiagonalization process. At each iteration step of the Lanczos process, the solution to a linear least squares problem with as the coefficient matrix is approximately computed, and this consists the only interface of the algorithm with the matrix pair . Numerical results are also given to demonstrate the feasibility and efficiency of the algorithm. Received April 1, 1994 / Revised version received December 15, 1994     

A matrix analysis of Arnoldi and Lanczos methods

Summary. In this paper we propose a matrix analysis of the Arnoldi and Lanczos procedures when used for approximating the eigenpairs of a non-normal matrix. By means of a new relation between the respective representation matrices, we relate the corresponding eigenvalues and eigenvectors. Moreover, backward error analysis is used to theoretically justify some unexpected experimental behaviors of non-normal matrices and in particular of banded Toeplitz matrices. Received June 19, 1996 / Revised version received November 3, 1997     

A unifying approach to abstract matrix algebra preconditioning

In earlier papers Tyrtyshnikov [42] and the first author [14] considered the analysis of clustering properties of the spectra of specific Toeplitz preconditioned matrices obtained by means of the best known matrix algebras. Here we generalize this technique to a generic Banach algebra of matrices by devising general preconditioners related to “convergent” approximation processes [36]. Finally, as case study, we focus our attention on the Tau preconditioning by showing how and why the best matrix algebra preconditioners for symmetric Toeplitz systems can be constructed in this class. Received April 25, 1997 / Revised version received March 13, 1998     

Componentwise perturbation analyses for the QR factorization

Summary. This paper gives componentwise perturbation analyses for Q and R in the QR factorization A=QR, , R upper triangular, for a given real $m\times n$ matrix A of rank n. Such specific analyses are important for example when the columns of A are badly scaled. First order perturbation bounds are given for both Q and R. The analyses more accurately reflect the sensitivity of the problem than previous such results. The condition number for R is bounded for a fixed n when the standard column pivoting strategy is used. This strategy also tends to improve the condition of Q, so usually the computed Q and R will both have higher accuracy when we use the standard column pivoting strategy. Practical condition estimators are derived. The assumptions on the form of the perturbation are explained and extended. Weaker rigorous bounds are also given. Received April 11, 1999 / Published online October 16, 2000     

Detection of Hopf points by counting sectors in the complex plane

Summary. Let ( real) be a family of real by matrices. A value of is called a Hopf value if has a conjugate pair of purely imaginary eigenvalues , . We describe a technique for detecting Hopf values based on the evolution of the Schur complement of in a bordered extension of where varies along the positive imaginary axis of the complex plane. We compare the efficiency of this method with more obvious methods such as the use of the QR algorithm and of the determinant function of as well as with recent work on the Cayley transform. In particular, we show the advantages of the Schur complement method in the case of large sparse matrices arising in dynamical problems by discretizing boundary value problems. The Hopf values of the Jacobian matrices are important in this setting because they are related to the Hopf bifurcation phenomenon where steady state solutions bifurcate into periodic solutions. Received September 15, 1994 / Revised version received July 7, 1995     

A note on properties of splittings of singular symmetric positive semidefinite matrices

Summary. Recently, Benzi and Szyld have published an important paper [1] concerning the existence and uniqueness of splittings for singular matrices. However, the assertion in Theorem 3.9 on the inheriting property of P-regular splitting for singular symmetric positive semidefinite matrices seems to be incorrect. As a complement of paper [1], in this short note we point out that if a matrix T is resulted from a P-regular splitting of a symmetric positive semidefinite matrix A, then splittings induced by T are not all P-regular. Received January 7, 1999 / Published online December 19, 2000     

Upper bound and stability of scaled pseudoinverses

Summary. For given matrices and where is positive definite diagonal, a weighed pseudoinverse of is defined by and an oblique projection of is defined by . When is of full column rank, Stewart [3] and O'Leary [2] found sharp upper bound of oblique projections which is independent of , and an upper bound of weighed pseudoinverse by using the bound of . In this paper we discuss the sharp upper bound of over a set of positive diagonal matrices which does not depend on the upper bound of , and the stability of over . Received September 29, 1993 / Revised version received October 31, 1994     

Entrywise perturbation theory for diagonally dominant M-matrices with applications

Summary. This paper introduces a new perspective on the study of computational problems related to diagonally dominant M-matrices by establishing some new entrywise perturbation results. If a diagonally dominant M-matrix is perturbed in a way that each off-diagonal entry and its row sums (i.e. the quantities of diagonal dominance) have small relative errors, we show that its determinant, cofactors, each entry of the inverse and the smallest eigenvalue all have small relative errors. The error bounds are given and they do not depend on any condition number. Applying this result to the studies of electrical circuits and tail probabilities of a queue whose embedded Markov chains is of GI/M/1 type, we discuss the relative sensitivity of the operating speed of circuits and of the percentile of the queue length, respectively. Received January 17, 2000 / Published online June 7, 2001     

Bounds on the error of an approximate invariant subspace for non-self-adjoint matrices

Summary. Suppose one approximates an invariant subspace of an matrix in which in not necessarily self--adjoint. Suppose that one also has an approximation for the corresponding eigenvalues. We consider the question of how good the approximations are. Specifically, we develop bounds on the angle between the approximating subspace and the invariant subspace itself. These bounds are functions of the following three terms: (1) the residual of the approximations; (2) singular--value separation in an associated matrix; and (3) the goodness of the approximations to the eigenvalues. Received December 1, 1992 / Revised version received October 20, 1993     

Backward errors for the inverse eigenvalue problem

Backward errors for the symmetric matrix inverse eigenvalue problem with respect to an approximate solution are defined, and explicit expressions of the backward errors are derived. The expressions may be useful for testing the stability of practical algorithms. Received August 4, 1997 / Revised version received May 11, 1998     

An efficient and accurate parallel algorithm for the singular value problem of bidiagonal matrices

Summary. In this paper we propose an algorithm based on Laguerre's iteration, rank two divide-and-conquer technique and a hybrid strategy for computing singular values of bidiagonal matrices. The algorithm is fully parallel in nature and evaluates singular values to tiny relative error if necessary. It is competitive with QR algorithm in serial mode in speed and advantageous in computing partial singular values. Error analysis and numerical results are presented. Received March 15, 1993 / Revised version received June 7, 1994     

Iteration schemes for the divide-and-conquer eigenvalue solver

Summary. We propose globally convergent iteration schemes for updating the eigenvalues of a symmetric matrix after a rank-1 modification. Such calculations are the core of the divide-and-conquer technique for the symmetric tridiagonal eigenvalue problem. We prove the superlinear convergence right from the start of our schemes which allows us to improve the complexity bounds of [3]. The effectiveness of our algorithms is confirmed by numerical results which are reported and discussed. Received September 22, 1993     

A note on the pivoted symmetric LR iteration

Summary. We prove that the diagonally pivoted symmetric LR algorithm on a positive definite matrix is globally convergent. Received December 23, 1997 / Revised version received August 3, 1998 / Published online August 19, 1999