ISSN 1068-9613. STRONG RANK REVEALING CHOLESKY FACTORIZATION

Abstract. For any symmetric positive definite ¢¤£¥ ¢ matrix ¦ 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 semidefinite 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. Key words. Cholesky decomposition, LU decomposition, QR decomposition, rank revealing, numerical rank, singular values, strong rank revealing QR factorization. AMS subject classifications. 65F30. 1. Introduction. Cholesk