The factorability of symmetric matrices and some implications for statistical linear models. (English) Zbl 0987.15006
The paper is concerned with the Cholesky factorization for a symmetric indefinite matrix \(K\). The theoretical background that involves both the existence and the numerical stability of the factorization is presented but an applicability of the theoretical results is emphasized.
The existence of the Cholesky factorization is not assured when the matrix \(K\) is not positive definite. Conditions are stated under which a symmetric permutation \(PKP^{T}\) of the matrix \(K\) is factorizable.
The existence of the Cholesky factorization is shown for matrix structures that appear in statistical applications. The author demonstrates how the Cholesky factorization of an indefinite matrix relates to Kalman filtering, recursive least squares or to a likelihood function in linear statistical models.
The existence of the Cholesky factorization is not assured when the matrix \(K\) is not positive definite. Conditions are stated under which a symmetric permutation \(PKP^{T}\) of the matrix \(K\) is factorizable.
The existence of the Cholesky factorization is shown for matrix structures that appear in statistical applications. The author demonstrates how the Cholesky factorization of an indefinite matrix relates to Kalman filtering, recursive least squares or to a likelihood function in linear statistical models.
Reviewer: Jitka Drkošova (Praha)
MSC:
| 15A23 | Factorization of matrices |
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
| 62J12 | Generalized linear models (logistic models) |
Keywords:
Cholesky factorization; symmetric indefinite matrix; numerical stability; Kalman filtering; recursive least squares; linear statistical modelsReferences:
| [1] | Ashcraft, C.; Crimes, R.; Lewis, J., Accurate symmetric indefinite linear equation solvers, SIAM J. Matrix Anal. Appl., 22, 513-561 (1999) · Zbl 0923.65010 |
| [2] | Bailey, D. H., Multiprecision translation and execution of Fortran programs, ACM Trans. Math. Software, 19, 288-319 (1993) · Zbl 0889.68015 |
| [3] | Bunch, J. R.; Parlett, B. N., Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal., 8, 639-655 (1997) · Zbl 0199.49802 |
| [4] | Carter, R., Y-MP floating point and Cholesky factorization, Int. J. High Speed Comput., 3, 215-222 (1991) |
| [5] | Cheng, S. H.; Higham, J., A modified Cholesky algorithm based on a symmetric indefinite factorization, SIAM J. Matrix Anal. Appl., 19, 1097-1110 (1998) · Zbl 0949.65022 |
| [6] | Doman, B. G.S.; Pursglove, C. J.; Coen, W. M., A set of Ada packages for high-precision calculations, ACM Trans. Math. Software, 21, 416-431 (1995) · Zbl 0883.68018 |
| [7] | Duff, I. S.; Reid, J. K., Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems, ACM Trans. Math. Software, 22, 227-257 (1996) · Zbl 0884.65020 |
| [8] | George, A.; Liu, J. W.-H., Computer Solutions of Large Sparse Positive Definite Systems (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0516.65010 |
| [9] | Gill, P. E.; Saunders, M. A.; Shinnerl, J. R., On the stability of Cholesky factorization for symmetric quasidefinite systems, SIAM J. Matrix Anal. Appl., 17, 35-46 (1996) · Zbl 0878.49020 |
| [10] | Grewal, M. S.; Andrews, A. P., Kalman Filtering: Theory and Practice (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0848.93002 |
| [11] | Harville, D. A., Maximum likelihood approaches to variance component estimation and to related problems, J. Am. Statist. Soc., 72, 320-340 (1977) · Zbl 0373.62040 |
| [12] | Higham, N. J., Analysis of the Cholesky decomposition of a semi-definite matrix, (Cox, M. G.; Hammarling, S. J., Reliable Numerical Computation (1990), Oxford University Press: Oxford University Press Oxford, UK), 161-185 · Zbl 0721.65014 |
| [13] | Karp, A. H.; Markstein, P., High-precision division and square root, ACM Trans. Math. Software, 23, 561-589 (1997) · Zbl 0912.65038 |
| [14] | Kielbasinski, A., A note on rounding-error analysis of Cholesky factorization, Linear Algebra Appl., 88/89, 487-494 (1987) · Zbl 0617.65014 |
| [15] | Linnainmaa, S., Analysis of some known methods of improving the accuracy of floating-point sums, BIT, 14, 167-202 (1974) · Zbl 0282.65034 |
| [16] | Meinguet, J., Refined error analyses of Cholesky factorization, SIAM J. Numer. Anal., 20, 1243-1250 (1983) · Zbl 0528.65014 |
| [17] | Müller, M.; Rüb, C.; Rüling, E., A circuit for exact summation of floating-point numbers, Inform. Process. Lett., 57, 159-163 (1996) · Zbl 0900.68008 |
| [18] | Patterson, H. D.; Thompson, R., Recovery of inter-block information when block sizes are unequal, Biometrika, 58, 545-554 (1971) · Zbl 0228.62046 |
| [19] | D.M. Priest, Algorithm for arbitrary precision, in: Proceedings of the 10th Symposium on Computer Arithmetic, IEEE Computer Society Press, New York, 1991, pp. 132-143; D.M. Priest, Algorithm for arbitrary precision, in: Proceedings of the 10th Symposium on Computer Arithmetic, IEEE Computer Society Press, New York, 1991, pp. 132-143 |
| [20] | M.A. Saunders, Cholesky-based methods for least squares: the benefits of regularizations, in: L. Adams, J.L. Nazareth (Eds.), Linear and Nonlinear Conjugate Gradient-Related Methods, SIAM, Philadelphia, 1996, pp. 92-100; M.A. Saunders, Cholesky-based methods for least squares: the benefits of regularizations, in: L. Adams, J.L. Nazareth (Eds.), Linear and Nonlinear Conjugate Gradient-Related Methods, SIAM, Philadelphia, 1996, pp. 92-100 · Zbl 0865.65022 |
| [21] | Shewchuk, J. R., Adaptive precision floating-point arithmetic and fast robust geometric predicates, Discrete Comput. Geom., 18, 305-363 (1997) · Zbl 0892.68098 |
| [22] | Siegel, I. H., Deferment of computation in the method of least squares, Math. Comput., 19, 329-331 (1965) · Zbl 0143.17201 |
| [23] | Smith, S. P., Differentiation of the Cholesky algorithm, J. Comput. Graphical Statist., 4, 134-147 (1995) |
| [24] | S.P. Smith, Likelihood-based analysis of linear state-space models using the Cholesky decomposition, J. Comput. Graphical Statist., accepted; S.P. Smith, Likelihood-based analysis of linear state-space models using the Cholesky decomposition, J. Comput. Graphical Statist., accepted |
| [25] | Sun, J.-G., Rounding-error and perturbation bounds for the Cholesky and \(LDL^{ T}\) factorizations, Linear Algebra Appl., 173, 77-97 (1992) · Zbl 0808.65018 |
| [26] | Vanderbei, R. J., Symmetric quasi-definite matrices, SIAM J. Optim., 5, 100-113 (1995) · Zbl 0822.65017 |
| [27] | Vanderbei, R. J.; Carpenter, T. J., Symmetric indefinite systems for interior point methods, Math. Program., 58, 1-32 (1993) · Zbl 0791.90033 |
| [28] | J.H. Wilkinson, A priori error analysis of algebraic processes, in: Proceedings of the International Congress of Mathematicians, Mir, Moscow, 1968, pp. 629-639; J.H. Wilkinson, A priori error analysis of algebraic processes, in: Proceedings of the International Congress of Mathematicians, Mir, Moscow, 1968, pp. 629-639 · Zbl 0197.13301 |
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.
