Computing enclosures for the inverse square root and the sign function of a matrix. (English) Zbl 1293.65071
Summary: We study computational methods for obtaining rigorous a posteriori error bounds for the inverse square root and the sign function of an \(n \times n\) matrix \(A\). Given a computed approximation for the inverse square root of \(A\), our methods work by using interval arithmetic to obtain a narrow interval matrix which, with mathematical certainty, is known to contain the exact inverse square root. Particular emphasis is put on the computational efficiency of the method which has complexity \(\mathcal{O}(n^3)\) and which uses almost exclusively matrix-matrix operation, a key to the efficient use of available software for interval computations. The standard formulation of the method assumes that \(A\) can be diagonalized and that the eigenvector matrix of \(A\) is well-conditioned. A modification relying on a stable similarlity transformation to block diagonal form is also developed.
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 15A24 | Matrix equations and identities |
| 65G30 | Interval and finite arithmetic |
| 65G20 | Algorithms with automatic result verification |
Keywords:
matrix inverse square root; matrix sign function; interval arithmetic; Krawczyk’s method; verified computation; a posteriori error bounds; interval matrix; computational efficiency; complexityReferences:
| [1] | Higham, N. J., Functions of Matrices: Theory and Computation (2008), SIAM: SIAM Philadelphia · Zbl 1167.15001 |
| [2] | Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0801.15001 |
| [3] | Sherif, N., On the computation of a matrix inverse square root, Computing, 46, 295-305 (1991) · Zbl 0741.65039 |
| [4] | Laasonen, P., On the iterative solution of the matrix equation \(A X^2 - I = 0\), Math. Tables Other Aids Comput., 12, 109-116 (1958) · Zbl 0083.11704 |
| [5] | Byers, R., Solving the algebraic Riccati equation with the matrix sign function, Linear Algebra Appl., 85, 267-279 (1987) · Zbl 0611.65027 |
| [6] | (Frommer, A.; Lippert, T.; Medeke, B.; Schilling, K., Numerical Challenges in Lattice Quantum Chromodynamics. Numerical Challenges in Lattice Quantum Chromodynamics, Lect. Notes Comput. Sci. Eng., vol. 15 (2000), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0957.00052 |
| [7] | Alefeld, G., Zur numerischen Auflösung der Matrizengleichung \(A X^2 - I = 0\), Beitr. Numer. Math., 9, 13-19 (1981) · Zbl 0462.65022 |
| [8] | Boriçi, A., A Lanczos approach to the inverse square root of a large and sparse matrix, J. Comput. Phys., 162, 1, 123-131 (2000) · Zbl 0960.65048 |
| [9] | Guo, C.-H.; Higham, N. J., A Schur-Newton method for the matrix \(p\) th root and its inverse, SIAM J. Matrix Anal. Appl., 28, 3, 788-804 (2006) · Zbl 1128.65030 |
| [10] | Lakić, S., An iterative method for the computation of a matrix inverse square root, ZAMM Z. Angew. Math. Mech., 75, 11, 867-873 (1995) · Zbl 0862.65026 |
| [11] | Frommer, A.; Hashemi, B., Verified computation of square roots of a matrix, SIAM J. Matrix Anal. Appl., 31, 1279-1302 (2009) · Zbl 1194.65069 |
| [12] | Kearfott, R. B.; Nakao, M.; Neumaier, A.; Rump, S.; Shary, S.; van Hentenryck, P., Standardized notation in interval analysis, Reliab. Comput., 15, 1, 7-13 (2010) · Zbl 1196.65088 |
| [13] | Alefeld, G.; Herzberger, J., Introduction to Interval Computations, Comput. Sci. Appl. Math. (1983), Academic Press: Academic Press New York · Zbl 0552.65041 |
| [14] | Moore, R. E.; Kearfott, R. B.; Cloud, M. J., Introduction to Interval Analysis (2009), SIAM: SIAM Philadelphia · Zbl 1168.65002 |
| [15] | Klatte, R.; Kulisch, U. W.; Wiethoff, A.; Lawo, C.; Rauch, M., C-XSC: A C++ Class Library for Extended Scientific Computing (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0814.68035 |
| [16] | Hofschuster, W.; Krämer, W., C-XSC 2.0: A C++ library for extended scientific computing, (Numerical Software With Result Verification. Numerical Software With Result Verification, Lecture Notes in Comput. Sci., vol. 2991 (2004), Springer: Springer Berlin), 15-35 · Zbl 1126.65328 |
| [17] | Rump, S. M., INTLAB - INTerval LABoratory, (Csendes, T., Developments in Reliable Computing (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 77-104 · Zbl 0949.65046 |
| [18] | Krawczyk, R., Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing, 4, 187-201 (1969) · Zbl 0187.10001 |
| [19] | Rump, S. M., Kleine Fehlerschranken bei Matrixproblemen (1980), Fakultät für Mathematik, Universität Karlsruhe, Ph.D. thesis · Zbl 0437.65036 |
| [20] | Sablik, T., Verifizierte Berechnung der inversen Matrixwurzelfunktion (2011), Department of Mathematics, University of Wuppertal, Master thesis |
| [21] | Rump, S. M., Solving algebraic problems with high accuracy, (Miranker, W.; Kaucher, E., A New Approach to Scientific Computation. A New Approach to Scientific Computation, Comput. Sci. Appl. Math., vol. 7 (1983), Academic Press: Academic Press New York), 51-120 · Zbl 0597.65018 |
| [22] | Rump, S. M., Verification methods for dense and sparse systems of equations, (Herzberger, J., Topics in Validated Computations. Topics in Validated Computations, Stud. Comput. Math., vol. 5 (1994), Elsevier: Elsevier Amsterdam), 63-135 · Zbl 0813.65072 |
| [23] | Bavely, A.; Stewart, G., An algorithm for computing reducing subspaces by block diagonalization, SIAM J. Numer. Anal., 16, 359-367 (1979) · Zbl 0413.65034 |
| [24] | Bai, Z.; Demmel, J., Using the matrix sign function to compute invariant subspaces, SIAM J. Matrix Anal. Appl., 19, 1, 205-225 (1998) · Zbl 0914.65035 |
| [25] | Stickel, E. U., Separating eigenvalues using the matrix sign function, Linear Algebra Appl., 148, 75-88 (1991) · Zbl 0718.15009 |
| [26] | Iannazzo, B., The geometric mean of two matrices from a computational viewpoint, Tech. rep., available on · Zbl 1374.65083 |
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.
