Volume 17, pp. 76-92, 2004.

Strong rank revealing Cholesky factorization

M. Gu and L. Miranian

Abstract

For any symmetric positive definite $n\times n$ matrix $A$ we introduce a definition of strong rank revealing Cholesky (RRCh) factorization similar to the notion of strong rank revealing QR factorization developed in the joint work of Gu and Eisenstat. There are certain key properties attached to strong RRCh factorization, the importance of which is discussed by Higham in the context of backward stability in his work on Cholesky decomposition of semi-definite matrices. We prove the existence of a pivoting strategy which, if applied in addition to standard Cholesky decomposition, leads to a strong RRCh factorization, and present two algorithms which use pivoting strategies based on the idea of local maximum volumes to compute a strong RRCh decomposition.

Full Text (PDF) [200 KB]

Key words

Cholesky decomposition, LU decomposition, QR decomposition, rank revealing, numerical rank, singular values, strong rank revealing QR factorization.

AMS subject classifications

65F30.

< Back