Perturbation analysis of singular subspaces and deflating subspaces

Summary. Perturbation expansions for singular subspaces of a matrix and for deflating subspaces of a regular matrix pair are derived by using a technique previously described by the author. The perturbation expansions are then used to derive Fr\'echet derivatives, condition numbers, and th-order perturbation bounds for the subspaces. Vaccaro's result on second-order perturbation expansions for a special class of singular subspaces can be obtained from a general result of this paper. Besides, new perturbation bounds for singular subspaces and deflating subspaces are derived by applying a general theorem on solution of a system of nonlinear equations. The results of this paper reveal an important fact: Each singular subspace and each deflating subspace have individual perturbation bounds and individual condition numbers. Received July 26, 1994     

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     

Riccati-based preconditioner for computing invariant subspaces of large matrices

Summary. This paper introduces and analyzes the convergence properties of a method that computes an approximation to the invariant subspace associated with a group of eigenvalues of a large not necessarily diagonalizable matrix. The method belongs to the family of projection type methods. At each step, it refines the approximate invariant subspace using a linearized Riccati's equation which turns out to be the block analogue of the correction used in the Jacobi-Davidson method. The analysis conducted in this paper shows that the method converges at a rate quasi-quadratic provided that the approximate invariant subspace is close to the exact one. The implementation of the method based on multigrid techniques is also discussed and numerical experiments are reported. Received June 15, 2000 / Revised version received January 22, 2001 / Published online October 17, 2001     

Accurate singular values and differential qd algorithms

Summary. We have discovered a new implementation of the qd algorithm that has a far wider domain of stability than Rutishauser's version. Our algorithm was developed from an examination of the {Cholesky~LR} transformation and can be adapted to parallel computation in stark contrast to traditional qd. Our algorithm also yields useful a posteriori upper and lower bounds on the smallest singular value of a bidiagonal matrix. The zero-shift bidiagonal QR of Demmel and Kahan computes the smallest singular values to maximal relative accuracy and the others to maximal absolute accuracy with little or no degradation in efficiency when compared with the LINPACK code. Our algorithm obtains maximal relative accuracy for all the singular values and runs at least four times faster than the LINPACK code. Received August 8, 1993/Revised version received May 26, 1993     

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     

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     

Perturbation analysis for block downdating of a Cholesky decomposition

Summary. Let the Cholesky decomposition of be , where is upper triangular. The Cholesky block downdating problem is to determine such that , where is a block of rows from the data matrix . We analyze the sensitivity of this block downdating problem of the Cholesky factorization. A measure of conditioning for the Cholesky block downdating is presented and compared to the single row downdating case. Received September 15, 1993     

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     

Semiconvergence of nonnegative splittings for singular matrices

Summary. In this paper, we discuss semiconvergence of the matrix splitting methods for solving singular linear systems. The concepts that a splitting of a matrix is regular or nonnegative are generalized and we introduce the terminologies that a splitting is quasi-regular or quasi-nonnegative. The equivalent conditions for the semiconvergence are proved. Comparison theorem on convergence factors for two different quasi-nonnegative splittings is presented. As an application, the semiconvergence of the power method for solving the Markov chain is derived. The monotone convergence of the quasi-nonnegative splittings is proved. That is, for some initial guess, the iterative sequence generated by the iterative method introduced by a quasi-nonnegative splitting converges towards a solution of the system from below or from above. Received August 19, 1997 / Revised version received August 20, 1998 / Published online January 27, 2000     

The approximation of generalized turning points\newline by Krylov subspace methods

Summary. Certain types of singular solutions of nonlinear parameter-dependent operator equations were characterized by Griewank and Reddien [5, 6] as regular solutions of suitable augmented systems. For their numerical approximation an approach based on the use of Krylov subspaces is here presented. The application to boundary value problems is illustrated by numerical examples. Received March 8, 1993 / Revised version received December 13, 1993     

A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils

A new method is presented for the numerical computation of the generalized eigenvalues of real Hamiltonian or symplectic pencils and matrices. The method is numerically backward stable and preserves the structure (i.e., Hamiltonian or symplectic). In the case of a Hamiltonian matrix the method is closely related to the square reduced method of Van Loan, but in contrast to that method which may suffer from a loss of accuracy of order , where is the machine precision, the new method computes the eigenvalues to full possible accuracy. Received April 8, 1996 / Revised version received December 20, 1996     

Accurate computation of the zeros of the generalized Bessel polynomials

Summary. A general method for approximating polynomial solutions of second-order linear homogeneous differential equations with polynomial coefficients is applied to the case of the families of differential equations defining the generalized Bessel polynomials, and an algorithm is derived for simultaneously finding their zeros. Then a comparison with several alternative algorithms is carried out. It shows that the computational problem of approximating the zeros of the generalized Bessel polynomials is not an easy matter at all and that the only algorithm able to give an accurate solution seems to be the one presented in this paper. Received July 25, 1997 / Revised version received May 19, 1999 / Published online June 8, 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     

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     

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     

Regions of exact convergence of the USSOR method applied on generalized consistently ordered matrices

Summary. Using the theory of nonnegative matrices and regular splittings, exact convergence and divergence domains of the Unsymmetric Successive Overrelaxation (USSOR) method, as it pertains to the class of Generalized Consistently Ordered (GCO) matrices, are determined. Our recently derived upper bounds, for the convergence of the USSOR method, re also used as effective tools. Received October 17, 1993 / Revised version received December 19, 1994     

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     

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     

Necessary and sufficient conditions for the convergence of Orthomin(k) on singular and inconsistent linear systems

Summary. We consider the convergence of Orthomin(k) on singular and inconsistent linear systems. Criteria for the breakdown of Orthomin(k) are discussed and analyzed. Moreover, necessary and sufficient conditions for the convergence of Orthomin(k) for any right hand side are given, and a rate of convergence is provided as well. Finally, numerical experiments are shown to confirm the convergence theorem. Received April 1, 1995 / Revised version received October 1, 1997 / Published online July 12, 2000     

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