A method of obtaining verified solutions for linear systems suited for Java. (English) Zbl 1108.65019
Summary: Recent development of Java’s optimization techniques makes Java one of the most useful programming languages for numerical computations. This paper proposes a numerical method of obtaining verified approximate solutions of linear systems. Usual methods for verified computations use switches of rounding modes defined in IEEE standard 754. However, such switches of rounding modes have not been supported in Java. This method avoids using directed rounding, so that it is implementable on a wide range of programming languages including Java. Numerical experiments using Java illustrate that the method can give a very accurate error bound for an approximate solution of a linear system with almost same computational cost as that for calculating an approximate inverse by the Gaussian elimination.
MSC:
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
| 65G20 | Algorithms with automatic result verification |
| 65G50 | Roundoff error |
Keywords:
verified computation; linear system; directed rounding; numerical experiments; error bound; approximate inverse; Gaussian eliminationReferences:
| [1] | ANSI/IEEE, IEEE Standard for Binary Floating Point Arithmetic, Std 754-1985 edition, IEEE, New York, 1985.; ANSI/IEEE, IEEE Standard for Binary Floating Point Arithmetic, Std 754-1985 edition, IEEE, New York, 1985. |
| [2] | B. Blount, JLAPACK—The LAPACK library in Java. \( \langle;\) http://www.cs.unc.edu/Research/HARPOON/jlapack/\( \rangle;\); B. Blount, JLAPACK—The LAPACK library in Java. \( \langle;\) http://www.cs.unc.edu/Research/HARPOON/jlapack/\( \rangle;\) |
| [3] | Dekker, T. J., A floating-point technique for extending the available precision, Numer. Math., 18, 224-242 (1971) · Zbl 0226.65034 |
| [4] | S. Flynn-Hummel, V. Getov, F. Irigoin, Ch. Lengauer, High performance computing and Java, Report No. 284, Report of the Dagstuhl Seminar 00341, 2000.; S. Flynn-Hummel, V. Getov, F. Irigoin, Ch. Lengauer, High performance computing and Java, Report No. 284, Report of the Dagstuhl Seminar 00341, 2000. |
| [5] | Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore and London · Zbl 0865.65009 |
| [6] | Gosling, J.; Joy, B.; Steele, G.; Bracha, G., The Java Language Specification (2000), Addison-Wesley: Addison-Wesley Reading, MA |
| [7] | W. Kahan, J.D. Darcy, How Java’s Floating-Point Hurts Everyone Everywhere, manuscript, \(2001. \langle;\) http://www.cs.berkeley.edu/\( \sim;\rangle;\); W. Kahan, J.D. Darcy, How Java’s Floating-Point Hurts Everyone Everywhere, manuscript, \(2001. \langle;\) http://www.cs.berkeley.edu/\( \sim;\rangle;\) |
| [8] | D.E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, vol. 2, Addison-Wesley, Reading, MA, 1969.; D.E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, vol. 2, Addison-Wesley, Reading, MA, 1969. · Zbl 0191.18001 |
| [9] | MathWorks Inc., NIST, JAMA—A Java Matrix Package. \( \langle;\) http://math.nist.gov/javanumerics/jama/\( \rangle;\); MathWorks Inc., NIST, JAMA—A Java Matrix Package. \( \langle;\) http://math.nist.gov/javanumerics/jama/\( \rangle;\) |
| [10] | Ogita, T.; Rump, S. M.; Oishi, S., Accurate sum and dot product, SIAM J. Sci. Comput., 26, 6, 1955-1988 (2005) · Zbl 1084.65041 |
| [11] | T. Ogita, S.M. Rump, S. Oishi, Verified solution of linear systems without directed rounding, Technical Report, No. 2005-04, Advanced Research Institute for Science and Engineering, Waseda University.; T. Ogita, S.M. Rump, S. Oishi, Verified solution of linear systems without directed rounding, Technical Report, No. 2005-04, Advanced Research Institute for Science and Engineering, Waseda University. · Zbl 1185.65082 |
| [12] | Oishi, S.; Rump, S. M., Fast verification of solutions of matrix equations, Numer. Math., 90, 4, 755-773 (2002) · Zbl 0999.65015 |
| [13] | Rump, S. M., Verification methods for dense and sparse systems of equations, (Herzberger, J., Topics in Validated Computations—Studies in Computational Mathematics (1994), Elsevier: Elsevier Amsterdam), 63-136 · Zbl 0813.65072 |
| [14] | G.W. Stewart, JAMPACK—A Java Package for Matrix Computations. \( \langle;\) ftp://math.nist.gov/Jampack/Jampack/AboutJampack.html \(\rangle;\); G.W. Stewart, JAMPACK—A Java Package for Matrix Computations. \( \langle;\) ftp://math.nist.gov/Jampack/Jampack/AboutJampack.html \(\rangle;\) |
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.
