Mixed and componentwise condition numbers for matrix decompositions. (English) Zbl 1375.65048
Summary: We present normwise and componentwise perturbation bounds for the \(LU\), the Cholesky, the \(L D L^{\operatorname{T}}\) and the \(QR\) decompositions by using a new approach. The explicit expressions of mixed and componentwise condition numbers for these matrix decompositions are derived. The condition numbers improve known results of the normwise and componentwise cases and reveal the characterizations of the structured perturbations. The exact explicit perturbation expressions are derived for the factors \(L\) and \(U\) of the \(LU\) decomposition, and the rigorous normwise and componentwise perturbation bounds are presented for the \(LU\) decomposition.
MSC:
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
| 15A23 | Factorization of matrices |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
Keywords:
mixed; componentwise; condition numbers; \(LU\) decomposition; Cholesky decomposition; \(L D L^{\operatorname{T}}\) decomposition; \(QR\) decompositionReferences:
| [1] | Gupta, A., Improved symbolic and numerical factorization algorithms for unsymmetric sparse matrices, SIAM J. Matrix Anal. Appl., 24, 529-552 (2002) · Zbl 1021.65014 |
| [2] | (Bai, Z.; Demmel, J.; Dongarra, J.; Ruhe, A.; van der Vorst, H., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Software, Environments, and Tools, vol. 11 (2000), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA) · Zbl 0965.65058 |
| [3] | Barrlund, A., Perturbation bounds for the \(L D L^T\) and LU decompositions, BIT, 31, 358-363 (1991) · Zbl 0733.65017 |
| [4] | Bhatia, R., Matrix factorization and their perturbations, Linear Algebra Appl., 197/198, 245-276 (1994) · Zbl 0794.15006 |
| [5] | Brandt, R., Polynomial Matrix Decompositions: Evaluation of Algorithms with an Application to Wideband MIMO Communications (2010), Uppsala University, Ph.D. thesis |
| [6] | Bürgisser, P.; Cucker, F., Condition: The Geometry of Numerical Algorithms (2013), Springer: Springer Heidelberg · Zbl 1280.65041 |
| [7] | Chang, X.-W., Perturbation Analysis of Some Matrix Factorizations (February 1997), McGill University: McGill University Montreal, Canada, Ph.D. thesis, Computer Science |
| [8] | Chang, X.-W., On the perturbation of the Q-factor of the QR factorization, Numer. Linear Algebra Appl., 19, 607-619 (2012) · Zbl 1274.65119 |
| [9] | Chang, X.-W.; Li, R.-C., Multiplicative perturbation analysis for QR factorizations, Numer. Algebra Control Optim., 1, 301-316 (2011) · Zbl 1247.65038 |
| [10] | Chang, X.-W.; Paige, C. C., A Perturbation Analysis for \(R\) in the QR Factorization (1995), School of Computer Science, McGill University: School of Computer Science, McGill University Montreal, Canada, 20 pages |
| [11] | Chang, X.-W.; Paige, C. C., On the sensitivity of the LU factorization, BIT, 38, 486-501 (1998) · Zbl 0924.65038 |
| [12] | Chang, X.-W.; Paige, C. C., Componentwise perturbation analysis for the QR factorization, Numer. Math., 88, 319-345 (2001) · Zbl 0989.65049 |
| [13] | Chang, X.-W.; Paige, C. C.; Stewart, G. W., New perturbation analyses for the Cholesky factorization, IMA J. Numer. Anal., 16, 457-484 (1996) · Zbl 0861.65020 |
| [14] | Chang, X.-W.; Paige, C. C.; Stewart, G. W., Perturbation analyses for the QR factorization, SIAM J. Matrix Anal. Appl., 18, 775-791 (1997) · Zbl 0876.15010 |
| [15] | Chang, X.-W.; Stehlé, D., Rigorous perturbation bounds of some matrix factorizations, SIAM J. Matrix Anal. Appl., 31, 2841-2859 (2010) · Zbl 1216.65051 |
| [16] | Chang, X.-W.; Stehlé, D.; Villard, G., Perturbation analysis of the QR factor R in the context of LLL lattice basis reduction, Math. Comp., 81, 1487-1511 (2012) · Zbl 1260.11082 |
| [17] | Corless, R. M.; Watt, S. M.; Zhi, L., QR factoring to compute the GCD of univariate approximate polynomials, IEEE Trans. Signal Process., 52, 3394-3402 (2004) · Zbl 1372.65120 |
| [18] | Cucker, F.; Diao, H.; Wei, Y., Smoothed analysis of some condition numbers, Numer. Linear Algebra Appl., 13, 71-84 (2006) · Zbl 1198.65084 |
| [19] | Cucker, F.; Diao, H.; Wei, Y., On mixed and componentwise condition numbers for Moore-Penrose inverse and linear least squares problems, Math. Comp., 76, 947-963 (2007) · Zbl 1115.15004 |
| [20] | Demmel, J., On condition numbers and the distance to the nearest ill-posed problem, Numer. Math., 51, 251-289 (1987) · Zbl 0597.65036 |
| [21] | Demmel, J., The probability that a numerical analysis problem is difficult, Math. Comp., 50, 449-480 (1988) · Zbl 0657.65066 |
| [22] | Demmel, J.; Higham, N.; Schreiber, R., Stability of block LU factorization, Numer. Linear Algebra Appl., 2, 173-190 (1995) · Zbl 0834.65010 |
| [23] | Dongarra, J.; Bunch, J.; Moler, G.; Stewart, G., Introduction from Linpack Users Guide (1979), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 0476.68025 |
| [24] | Drmač, Z.; Omladič, M.; Veselič, K., On the perturbation of the Cholesky factorization, SIAM J. Matrix Anal. Appl., 15, 1319-1332 (1994) · Zbl 0809.15005 |
| [25] | Eisenstat, S. C.; Liu, J. W.H., Exploiting structural symmetry in unsymmetric sparse symbolic factorization, SIAM J. Matrix Anal. Appl., 13, 202-211 (1992) · Zbl 0746.65023 |
| [26] | Galántai, A., Componentwise perturbation bounds for the LU, LDU and \(L D L^T\) decompositions, Miskolc Math. Notes, 1, 109-118 (2000) · Zbl 0973.65034 |
| [27] | Galántai, A., Perturbation bounds for triangular and full rank factorizations, Comput. Math. Appl., 50, 1061-1068 (2005) · Zbl 1087.65023 |
| [28] | George, A.; Heath, M. T.; Ng, E.; Liu, J., Symbolic Cholesky factorization on a local-memory multiprocessor, SIAM J. Sci. Stat. Comput., 5, 85-95 (1987) · Zbl 0618.65023 |
| [29] | George, A.; Ng, E., Symbolic factorization for sparse Gaussian elimination with partial pivoting, SIAM J. Sci. Stat. Comput., 8, 877-898 (1987) · Zbl 0632.65021 |
| [30] | Gohberg, I.; Koltracht, I., Mixed, componentwise and structured condition numbers, SIAM J. Matrix Anal. Appl., 14, 688-704 (1993) · Zbl 0780.15004 |
| [31] | Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 1268.65037 |
| [32] | Grabmeier, J.; Kaltofen, E.; Weispfenning, V., Computer Algebra Handbook: Foundations, Applications, Systems (2003), Springer-Verlag: Springer-Verlag Berlin · Zbl 1017.68162 |
| [33] | Grigori, L.; Demmel, J. W.; Li, X., Parallel symbolic factorization for sparse LU with static pivoting, SIAM J. Sci. Comput., 29, 1289-1314 (2007) · Zbl 1141.65354 |
| [34] | Grigori, L.; Gilbert, J. R.; Cosnard, M., Symbolic and exact structure prediction for sparse Gaussian elimination with partial pivoting, SIAM J. Matrix Anal. Appl., 30, 1520-1545 (2008) · Zbl 1176.65025 |
| [35] | Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 1011.65010 |
| [36] | Jin, X.; Wei, Y.; Zhao, Z., Numerical Linear Algebra and Its Applications (2012), Science Press: Science Press Beijing: Alpha Science International Ltd.: Science Press: Science Press Beijing: Alpha Science International Ltd. UK, and |
| [37] | Langer, U.; Paule, P., Numerical and Symbolic Scientific Computing (2011), Springer: Springer New York |
| [38] | Li, H.; Wei, Y., Improved rigorous perturbation bounds for the LU and QR factorizations, Numer. Linear Algebra Appl., 22, 1115-1130 (2015) · Zbl 1374.65032 |
| [39] | Li, H.; Wei, Y.; Yang, Y., New rigorous perturbation bounds for the Cholesky-like factorization of skew-symmetric matrix, Linear Algebra Appl., 491, 83-100 (2016) · Zbl 1330.15015 |
| [40] | Liu, X.-G., Sensitivity analysis of some matrix decompositions, Math. Numer. Sin., 23, 279-288 (2001), (in Chinese) · Zbl 1495.65056 |
| [41] | Marcos, A.; Bates, D. G.; Postlethwaite, I., A symbolic matrix decomposition algorithm for reduced order linear fractional transformation modelling, Automatica, 43, 1211-1218 (2007) · Zbl 1123.93030 |
| [42] | Robbiano, L.; Abbott, J., Approximate Commutative Algebra (2009), Springer: Springer New York · Zbl 1176.13001 |
| [43] | Rump, S., Structured perturbations part II: componentwise distances, SIAM J. Matrix Anal. Appl., 25, 31-56 (2003) · Zbl 1061.15005 |
| [44] | Rump, S.; Jeannerod, C., Improved backward error bounds for LU and Cholesky factorizations, SIAM J. Matrix Anal. Appl., 35, 684-698 (2014) · Zbl 1309.65031 |
| [45] | Sankar, A.; Spielman, D. A.; Teng, S.-H., Smoothed analysis of the condition numbers and growth factors of matrices, SIAM J. Matrix Anal. Appl., 28, 446-476 (2006) · Zbl 1179.65033 |
| [46] | Stewart, G. W., Perturbation bounds for the QR factorization of a matrix, SIAM J. Numer. Anal., 14, 509-518 (1977) · Zbl 0358.65038 |
| [47] | Stewart, G. W., On the perturbation of LU, Cholesky and QR factorizations, SIAM J. Matrix Anal. Appl., 14, 1141-1145 (1993) · Zbl 0785.65017 |
| [48] | Stewart, G. W., On the perturbation of LU and Cholesky factors, IMA J. Numer. Anal., 17, 1-6 (1997) · Zbl 0876.65016 |
| [49] | Stewart, G. W., Matrix Algorithms, Vol. 1: Basic Decompositions (1998), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 0910.65012 |
| [50] | Sun, J.-G., Perturbation bounds for the Cholesky and QR factorizations, BIT, 31, 341-352 (1991) · Zbl 0728.65032 |
| [51] | Sun, J.-G., Componentwise perturbation bounds for some matrix decompositions, BIT, 32, 702-714 (1992) · Zbl 0764.65016 |
| [52] | Sun, J.-G., Rounding-error and perturbation bounds for Cholesky and \(L D L^T\) factorizations, Linear Algebra Appl., 173, 77-97 (1992) · Zbl 0808.65018 |
| [53] | Sun, J.-G., On perturbation bounds for the QR factorization, Linear Algebra Appl., 215, 95-111 (1995) · Zbl 0816.15010 |
| [54] | Tao, T.; Vu, V., Smooth analysis of the condition number and the least singular value, Math. Comp., 79, 2333-2352 (2010) · Zbl 1253.65067 |
| [55] | Wang, D.; Zhi, L., Symbolic-Numeric Computation (2007), Springer: Springer Basel |
| [56] | Zha, H., A componentwise perturbation analysis of the QR factorization, SIAM J. Matrix Anal. Appl., 14, 1124-1131 (1993) · Zbl 0787.65014 |
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.
