Fast verified solutions of linear systems. (English) Zbl 1184.65046
Summary: This paper aims to survey fast methods of verifying the accuracy of a numerical solution of a linear system. For the last decade, a number of fast verification algorithms have been proposed to obtain an error bound of a numerical solution of a dense or sparse linear system. Such fast algorithms rely on the verified numerical computation using floating-point arithmetic defined by IEEE standard 754. Some fast verification methods for dense and sparse linear systems are reviewed together with corresponding numerical results to show the practical use and efficiency of the verified numerical computation as much as possible.
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 65G20 | Algorithms with automatic result verification |
| 65G30 | Interval and finite arithmetic |
Keywords:
verified numerical computation; verified solutions of linear systems; self-validating methods; interval arithmetic; algorithms; error bound; numerical resultsReferences:
| [1] | G. Alefeld and J. Herzberger, Introduction to Interval Computations. Academic Press, New York, 1983. · Zbl 0552.65041 |
| [2] | ANSI/IEEE, IEEE Standard for Binary Floating Point Arithmetic, Std 754-1985 edition. IEEE, New York, 1985. |
| [3] | A. Berman and R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences. Classics Appl. Math.,9, SIAM, Philadelphia, 1994. · Zbl 0815.15016 |
| [4] | X. Chen and K. Hashimoto, Numerical validation of solutions of saddle point matrix equations. Numerical Linear Algebra with Applications,10 (2003), 661–672. · Zbl 1071.65068 · doi:10.1002/nla.342 |
| [5] | J.B. Demmel, On floating point errors in Cholesky. LAPACK Working Note 14 CS-89-87, Department of Computer Science, University of Tennessee, Knoxville, TN, USA, 1989. |
| [6] | J. Dongarra, Basic linear algebra subprograms technical forum standard. International Journal of High Performance Applications and Supercomputing,16 (2002), 1–111. · doi:10.1177/10943420020160010101 |
| [7] | K. Goto and R.A. van de Geijn, Anatomy of high-performance matrix multiplication. ACM Trans. Math. Softw.,34 (2008), 12:1–12:25. · Zbl 1190.65064 · doi:10.1145/1356052.1356053 |
| [8] | K. Goto and R.A. van de Geijn, High performance implementation of the Level-3 BLAS. ACM Trans. Math. Softw.,35 (2008), 4:1–4:14. · doi:10.1145/1377603.1377607 |
| [9] | A. Hadjidimos, An extended compact profile iterative method criterion for sparse H-matrix. Linear Alg. Appl.,389 (2004), 329–345. · Zbl 1058.65040 · doi:10.1016/j.laa.2004.03.011 |
| [10] | N.J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd edition. SIAM, Philadelphia, PA, 2002. · Zbl 1011.65010 |
| [11] | R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken. Computing,4 (1969), 187–201. · Zbl 0187.10001 · doi:10.1007/BF02234767 |
| [12] | G. Mayer, On regular and singular interval systems. J. Comp. Appl. Math.,199 (2007), 220–228. · Zbl 1108.65018 · doi:10.1016/j.cam.2005.07.033 |
| [13] | R.E. Moore, A test for existence of solutions for non-linear systems. SIAM J. Numer. Anal.,4 (1977), 611–615. · Zbl 0365.65034 · doi:10.1137/0714040 |
| [14] | A. Neumaier, A simple derivation of the Hansen-Bliek-Rohn-Ning-Kearfott enclosure for linear interval equations. Reliable Computing,5 (1999), 131–136; Erratum. Reliable Computing,6 (2000), 227. · Zbl 0936.65055 · doi:10.1023/A:1009997221089 |
| [15] | A. Neumaier, Grand challenges and scientific standards in interval analysis. Reliable Computing,8 (2002), 313–320. · Zbl 0999.65030 · doi:10.1023/A:1016341317043 |
| [16] | A. Neumaier, Interval Methods for Systems of Equations. Encyclopedia of Mathematics and its Applications, Cambridge University Press, 1990. · Zbl 0715.65030 |
| [17] | S. Ning and R.B. Kearfott, A comparison of some methods for solving linear interval equations. SIAM J. Numer. Anal.,34 (1997), 1289–1305. · Zbl 0889.65022 · doi:10.1137/S0036142994270995 |
| [18] | T. Ogita and S. Oishi, Fast verification method for large-scale linear systems. Trans. IPSJ,46 (2005), 10–18 (in Japanese). · Zbl 1072.65063 |
| [19] | T. Ogita and S. Oishi, Tight enclosures of solutions of linear systems. International Series of Numerical Mathematics,157 (2009), 167–178 (Inequalities and Applications, C. Bandle, A. Gilányi, L. Losonczi, Z. Páles and M. Plum eds., Birkhäuser Verlag). · Zbl 1266.65076 |
| [20] | T. Ogita, S. Oishi and Y. Ushiro, Fast verification of solutions for sparse monotone matrix equations. Computing Suppl.,15 (2001), 175–187. · Zbl 0994.65035 |
| [21] | T. Ogita, S. Oishi and Y. Ushiro, Computation of sharp rigorous componentwise error bounds for the approximate solutions of systems of linear equations. Reliable Computing,9 (2003), 229–239. · Zbl 1029.65045 · doi:10.1023/A:1024655416554 |
| [22] | T. Ogita, S.M. Rump and S. Oishi, Accurate sum and dot product. SIAM J. Sci. Comput.,26 (2005), 1955–1988. · Zbl 1084.65041 · doi:10.1137/030601818 |
| [23] | S. Oishi, Fast enclosure of matrix eigenvalues and singular values via rounding mode controlled computation Linear Alg. Appl.,324 (2001), 133–146. · Zbl 0978.65026 · doi:10.1016/S0024-3795(00)00272-X |
| [24] | S. Oishi, K. Tanabe, T. Ogita and S.M. Rump, Convergence of Rump’s method for inverting arbitrarily ill-conditioned matrices. J. Comp. Appl. Math.,205 (2007), 533–544. · Zbl 1120.65040 · doi:10.1016/j.cam.2006.05.022 |
| [25] | S. Oishi and S.M. Rump, Fast verification of matrix equations. Numer. Math.,90 (2002), 755–773. · Zbl 0999.65015 · doi:10.1007/s002110100310 |
| [26] | J. Rohn, A Handbook of Results on Interval Linear Problems. Internet text available at http://www.cs.cas.cz/rohn/handbook/ · Zbl 0810.65025 |
| [27] | S.M. Rump, A note on, epsilon-inflation. Reliable Computing,4 (1998), 371–375. · Zbl 0920.65031 · doi:10.1023/A:1024419816707 |
| [28] | S.M. Rump, Approximate inverses of almost singular matrices still contain useful information. Forschungsschwerpunktes Informations- und Kommunikationstechnik, Technical Report 90.1, Hamburg University of Technology, 1990. |
| [29] | S.M. Rump, Computer-Assisted Proofs and Self-Validating Methods. Accuracy and Reliability in Scientific Computing (Chapter 10) SIAM, Philadelphia, PA, 2005. |
| [30] | S.M. Rump, Fast and parallei interval arithmetic. BIT,39 (1999), 534–554. · Zbl 0942.65048 · doi:10.1023/A:1022374804152 |
| [31] | S.M. Rump, INTLAB-INTerval LABoratory. Developments in Reliable Computing, T. Csendes ed., Kluwer Academic Publishers, Dordrecht, 1999, 77–104. http://www.ti3.tu-harburg.de/rump/intlab/. · Zbl 0949.65046 |
| [32] | S.M. Rump, Kleine Fehlerschranken bei Matrixproblemen. Universität Karlsruhe, Ph.D. thesis, 1980. |
| [33] | S.M. Rump, Validated solution of large linear systems. Computing Suppl.,9 (1993), 191–212. · Zbl 0837.65013 |
| [34] | S.M. Rump, Verification methods for dense and sparse systems of equations. Topics in Validated Computations–Studies in Computational Mathematics, J. Herzberger ed., Elsevier, Amsterdam, 1994, 63–136. · Zbl 0813.65072 |
| [35] | S.M. Rump, Verification of positive definiteness. BIT Numerical Mathematics,46 (2006), 433–452. · Zbl 1101.65039 · doi:10.1007/s10543-006-0056-1 |
| [36] | S.M. Rump and T. Ogita, Super-fast validated solution of linear systems. J. Comp. Appl. Math.,199 (2007), 199–206. · Zbl 1108.65020 · doi:10.1016/j.cam.2005.07.038 |
| [37] | S.M. Rump, T. Ogita and S. Oishi, Accurate floating-point summation, Part I: Faithful rounding. SIAM J. Sci. Comput.,31 (2008), 189–224. · Zbl 1185.65082 · doi:10.1137/050645671 |
| [38] | S.M. Rump, T. Ogita and S. Oishi, Accurate floating-point summation., Part II: Sign,K-fold faithful and rounding to nearest. SIAM J. Sci. Comput.,31 (2008), 1269–1302. · Zbl 1190.65074 · doi:10.1137/07068816X |
| [39] | V. Strassen, Gaussian elimination is not optimal. Numer. Math.,13 (1969), 354–356. · Zbl 0185.40101 · doi:10.1007/BF02165411 |
| [40] | J.-G. Sun, Rounding-error and perturbation bounds for the Cholesky andLDL T factorizations. Linear Alg. Appl.,173 (1992), 77–97. · Zbl 0808.65018 · doi:10.1016/0024-3795(92)90423-8 |
| [41] | T. Yamamoto, Error bounds for approximate solutions of systems of equations. Japan J. Appl. Math.,1 (1984), 157–171. · Zbl 0571.65035 · doi:10.1007/BF03167865 |
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.
