Volume 5, pp. 29-47, 1997.

A new algorithm for the SVD of a long product of matrices and the stability of products

David E. Stewart

Abstract

Lyapunov exponents can be estimated by accurately computing the singular values of long products of matrices, with perhaps 1000 or more factor matrices. These products have extremely large ratios between the largest and smallest eigenvalues. A variant of Rutishauser's Cholesky LR algorithm for computing eigenvalues of symmetric matrices is used to obtain a new algorithm for computing the singular values and vectors of long products of matrices with small backward error in the factor matrices. The basic product SVD algorithm can also be accelerated using hyperbolic Givens' rotations. The method is competitive with Jacobi-based methods for certain problems as numerical results indicate. Some properties of the product SVD factorization are also discussed, including uniqueness and stability. The concept of a stable product is introduced; for such products, all singular values can be computed to high relative accuracy.

Full Text (PDF) [148 KB]

Key words

SVD, products of matrices, Lyapunov exponents.

AMS subject classifications

65F15, 34D08.

Links to the cited ETNA articles

[23]Vol. 3 (1995), pp. 39-49 G. W. Stewart: On graded QR decompositions of products of matrices

< Back