Cholesky-Like Factorization of Symmetric Indefinite Matrices and Orthogonalization with Respect to Bilinear Forms
Miroslav Rozložńık, Felicja Okulicka-Dłużewska, Agata Smoktunowicz · SIAM Journal on Matrix Analysis and Applications · 2015
It is well known that orthogonalization of column vectors in a rectangular matrix $B$ with respect to the bilinear form induced by a nonsingular symmetric indefinite matrix $A$ can be eventually seen as its factorization $B=QR$ that is equivalent to the Cholesky-like factorization in the form $B^TAB=R^T \Omega R$, where $R$ is upper triangular and $\Omega$ is a signature matrix. Under the assumption of nonzero principal minors of the matrix $M=B^T A B$ we give bounds for the conditioning of the triangular factor $R$ in terms of extremal singular values of $M$ and of only those principal submatrices of $M$ where there is a change of sign in $\Omega$. Using these results we study the numerical behavior of two types of orthogonalization schemes and we give the worst-case bounds for quantities computed in finite precision arithmetic. In particular, we analyze the implementation based on the Cholesky-like factorization of $M$ and the Gram--Schmidt process with respect to the bilinear form induced by the matrix $A$. To improve the accuracy of computed results we consider also the Gram--Schmidt process with reorthogonalization and show that its behavior is similar to the scheme based on the Cholesky-like factorization with one step of iterative refinement.