×

Cholesky-like factorization of symmetric indefinite matrices and orthogonalization with respect to bilinear forms. (English) Zbl 1317.65105

Summary: 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.

MSC:

65F25 Orthogonalization in numerical linear algebra
65F05 Direct numerical methods for linear systems and matrix inversion
65F35 Numerical computation of matrix norms, conditioning, scaling
65G50 Roundoff error

Software:

mctoolbox; SLEPc
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] J. Barlow and A. Smoktunowicz, {\it Reorthogonalized block classical Gram-Schmidt}, Numer. Math., 123 (2013), pp. 395-423. · Zbl 1269.65042
[2] M. Benzi, G. H. Golub, and J. Liesen, {\it Numerical solution of saddle point problems}, Acta Numer., 14 (2005), pp. 1-137. · Zbl 1115.65034
[3] \AA. Björck, {\it Solving linear least squares problems by Gram-Schmidt orthogonalization}, BIT, 7 (1967), pp. 1-21. · Zbl 0183.17802
[4] A. Bojanczyk, N.J. Higham, and H. Patel, {\it Solving the indefinite least squares problem by hyperbolic QR factorization}, SIAM J. Matrix Anal. Appl., 24 (2003), pp. 914-931. · Zbl 1036.65035
[5] M.A. Brebner and J. Grad, {\it Eigenvalues of \(Ax = λ Bx\) for real symmetric matrices A and B computed by reduction to a pseudosymmetric form and the HR process}, Linear Algebra Appl., 43 (1982), pp. 99-118. · Zbl 0485.65029
[6] J.R. Bunch, {\it Analysis of the diagonal pivoting method}, SIAM J. Numer. Anal., 8 (1971), pp. 656-680.
[7] J.R. Bunch and B.N. Parlett, {\it Direct methods for solving symmetric indefinite systems of linear equations}, SIAM J. Numer. Anal., 8 (1971), pp. 639-655. · Zbl 0199.49802
[8] A. Bunse-Gerstner, {\it An analysis of the HR algorithm for computing the eigenvalues of a matrix}, Linear Algebra Appl., 35 (1981), pp. 155-173. · Zbl 0462.65021
[9] S. Chandrasekaran, M. Gu, and A.H. Sayed, {\it A stable and efficient algorithm for the indefinite linear least-squares problem}, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 354-362. · Zbl 0920.65024
[10] J. Della-Dora, {\it Numerical linear algorithms and group theory}, Linear Algebra Appl., 10 (1975), pp. 267-283. · Zbl 0308.65025
[11] J.W. Demmel, N.J. Higham, and R.S. Schreiber, {\it Stability of block LU factorization}, Numer. Linear Algebra Appl., 2 (1995), pp. 173-190. · Zbl 0834.65010
[12] L. Elsner, {\it On some algebraic problems in connection with general eigenvalue algorithms}, Linear Algebra Appl., 26 (1979), pp. 123-138. · Zbl 0412.15019
[13] P.E. Gill, M.A. Saunders, and J.R. Shinnerl, {\it On the stability of Cholesky factorization for symmetric quasidefinite systems}, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 35-46. · Zbl 0878.49020
[14] L. Giraud, J. Langou, M. Rozložník, and J. van den Eshof, {\it Rounding error analysis of the classical Gram-Schmidt orthogonalization process}, Numer. Math., 101 (2005), pp. 97-100. · Zbl 1075.65060
[15] I. Gohberg, P. Lancaster, and L. Rodman, {\it Matrices and Indefinite Scalar Products}, Oper. Theory Adv. Appl. 8, Birkhäuser Verlag, Basel, 1983. · Zbl 0513.15006
[16] M. Gulliksson, {\it Backward error analysis for the constrained and weighted linear least squares problem when using the weighted \(QR\) factorization}, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 675-687. · Zbl 0833.65035
[17] M. Gulliksson, {\it On the modified Gram-Schmidt algorithm for weighted and constrained linear least squares problems}, BIT, 35 (1995), pp. 453-468. · Zbl 0848.65026
[18] N.J. Higham, {\it Accuracy and Stability of Numerical Algorithms}, 2nd ed., SIAM, Philadelphia, 2002. · Zbl 1011.65010
[19] N.J. Higham, {\it \(J\)-orthogonal matrices: Properties and generation}, SIAM Rev., 45 (2003), pp. 504-519. · Zbl 1034.65026
[20] R.A. Horn and C.R. Johnson, {\it Matrix Analysis}, Cambridge University Press, Cambridge, 1990. · Zbl 0704.15002
[21] D. Kressner, M. Miloloźa Pandur, and M. Shao, {\it An indefinite variant of LOBPCG for definite matrix pencils}, Numer. Algorithms, 66 (2014), pp. 681-703. · Zbl 1297.65040
[22] B.R. Lowery and J. Langou, {\it Stability Analysis of QR Factorization in an Oblique Inner Product}, preprint, arXiv:1401.5171, 2014.
[23] N. Mastronardi and P. Van Dooren, {\it An algorithm for solving the indefinite least squares problem with equality constraints}, BIT, 54 (2014), pp. 201-218. · Zbl 1290.65033
[24] N. Mastronardi and P. Van Dooren, {\it A structurally backward stable algorithm for solving the indefinite least squares problem with equality constraints}, IMA J. Numer. Anal., 35 (2015), pp. 107-132. · Zbl 1309.65068
[25] E. Romero and J.E. Roman. {\it A parallel implementation of Davidson methods for large-scale eigenvalue problems in SLEPc}, ACM Trans. Math. Softw., 40 (2014), 13. · Zbl 1305.65124
[26] M. Rozložník, M. T\accent23uma, A. Smoktunowicz, and J. Kopal, {\it Numerical stability of orthogonalization methods with a non-standard inner product}, BIT, 52 (2012), pp. 1035-1058. · Zbl 1259.65069
[27] T. Rusten and R. Winther, {\it A preconditioned iterative method for saddlepoint problems}, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 887-904. · Zbl 0760.65033
[28] S. Singer, {\it Indefinite QR Factorization}, BIT, 46 (2006), pp. 141-161. · Zbl 1093.65029
[29] S. Singer and S. Singer, {\it Symmetric indefinite factorization of quasidefinite matrices}, Math. Commun., 4 (1999), pp. 19-25. · Zbl 0941.15006
[30] S. Singer and S. Singer, {\it Rounding-error and perturbation bounds for the indefinite QR factorization}, Linear Algebra Appl., 309 (2000), pp. 103-119. · Zbl 0948.65042
[31] I. Slapničar, {\it Componentwise analysis of direct factorization of real symmetric and Hermitian matrices}, Linear Algebra Appl., 272 (1998), pp. 227-275. · Zbl 0894.65009
[32] I. Slapničar and K. Veselić, {\it A bound for the condition of a hyperbolic eigenvector matrix}, Linear Algebra Appl., 290 (1999), pp. 247-255. · Zbl 0944.15002
[33] A. Smoktunowicz, J.L. Barlow, and J. Langou, {\it A note on the error analysis of classical Gram-Schmidt}, Numer. Math., 105 (2006), pp. 299-313. · Zbl 1108.65021
[34] S.J. Thomas and R.V.M. Zahar, {\it Efficient orthogonalization in the \(M\)-norm}, Congr. Numer., 80 (1991), pp. 23-32. · Zbl 0735.65024
[35] S.J. Thomas and R.V.M. Zahar, {\it An analysis of orthogonalization in elliptic norms}, Congr. Numer., 86 (1992), pp. 193-222. · Zbl 0761.65032
[36] R.J. Vanderbei, {\it Symmetric quasi-definite matrices}, SIAM J. Optim., 5 1995, pp. 100-113. · Zbl 0822.65017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.