×

Precise numerical computation. (English) Zbl 1075.68104

Summary: Arithmetic systems such as those based on IEEE standards currently make no attempt to track the propagation of errors. A formal error analysis, however, can be complicated and is often confined to the realm of experts in numerical analysis. In recent years, there has been a resurgence of interest in automated methods for accurately monitoring the error propagation. In this article, a floating-point system based on significance arithmetic will be described. Details of the implementation in Mathematica will be given along with examples that illustrate the design goals and differences over conventional fixed-precision floating-point systems.

MSC:

68W30 Symbolic computation and algebraic computation
65G20 Algorithms with automatic result verification
65G30 Interval and finite arithmetic
65G50 Roundoff error
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aberth, O., Precise Numerical Methods Using C++ (1998), Academic Press: Academic Press San Diego · Zbl 0932.65001
[2] Andrews, G. E., The Theory of Partitions (1998), Cambridge University Press: Cambridge University Press UK · Zbl 0906.05004
[3] Ashenhurst, R. L., Techniques for automatic error monitoring and control, (Rall, L. B., Error in Digital Computation, vol. 1 (1965), Wiley: Wiley New York), 43-59 · Zbl 0216.49601
[4] Bevilacqua, R.; Bini, D.; Capovani, M.; Menchi, O., Metodi Numerici (1992), Zanichelli: Zanichelli Bologna
[5] Chaitin-Chatelin, F.; Fraysse’, V., Lectures on Finite Precision Computations (1996), SIAM: SIAM Philadelphia · Zbl 0846.65020
[6] G.F. Corliss, Guaranteed error bounds for ODEs, in: M. Ainsworth, J. Levesley, W.A. Light, M. Marletta (Eds.), Theory and Numerics of Ordinary and Partial Differential Equations, Advances in Numerical Analysis IV, Oxford Science Publications, Clarendon Press, Oxford, 1995, pp. 1-75; G.F. Corliss, Guaranteed error bounds for ODEs, in: M. Ainsworth, J. Levesley, W.A. Light, M. Marletta (Eds.), Theory and Numerics of Ordinary and Partial Differential Equations, Advances in Numerical Analysis IV, Oxford Science Publications, Clarendon Press, Oxford, 1995, pp. 1-75
[7] Cuyt, A.; Verdonk, B.; Becuwe, S.; Kuterna, P., A remarkable example of catastrophic cancellation unraveled, Computing, 66, 309-320 (2001) · Zbl 0999.65031
[8] H.L. Gray, C. Harrison, Normalized floating point arithmetic with an index of significance, in: Proceedings of the Eastern Joint Computer Conference 16, Boston, MA, December 1-3, 1959, PP. 244-248; H.L. Gray, C. Harrison, Normalized floating point arithmetic with an index of significance, in: Proceedings of the Eastern Joint Computer Conference 16, Boston, MA, December 1-3, 1959, PP. 244-248
[9] Fateman, R. J., A review of Mathematica, J. Symbolic Comput., 13, 545-579 (1992) · Zbl 0762.68034
[10] Hairer, E.; Wanner, G., Analysis by Its History (1995), Springer: Springer New York · Zbl 0842.26002
[11] Hammer, R.; Hocks, M.; Kulisch, U.; Ratz, D., C++ Toolbox for Verified Computing. Basic Numerical Problems (1995), Springer: Springer Berlin · Zbl 0828.68041
[12] Hansen, E., Global Optimization Using Interval Analysis (1992), M. Dekker Inc.: M. Dekker Inc. New York · Zbl 0762.90069
[13] Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), SIAM: SIAM Philadelphia · Zbl 1011.65010
[14] Hunter, G., A quantitative measure of precision, Comput. J., 18, 3, 231-233 (1975) · Zbl 0306.65022
[15] Jones, C. B., A significance rule for multiple precision arithmetic, ACM Trans. Math. Softw., 10, 1, 97-107 (1984) · Zbl 0582.65034
[16] Lichtblau, D., Groebner bases in Mathematica 3.0, Math. J., 6, 4, 81-88 (1996)
[17] D. Lichtblau, Solving finite algebraic systems using numeric Gröbner bases and eigenvalues, in: M. Torres, J. Molero, Y. Kurihara, A. David (Eds.), SCI2000 Proceedings of the World Conference on Systemics, Cybernetics and Informatics, 10, International Institute of Informatics and Systemics, 2000, pp. 555-560; D. Lichtblau, Solving finite algebraic systems using numeric Gröbner bases and eigenvalues, in: M. Torres, J. Molero, Y. Kurihara, A. David (Eds.), SCI2000 Proceedings of the World Conference on Systemics, Cybernetics and Informatics, 10, International Institute of Informatics and Systemics, 2000, pp. 555-560
[18] Loh, E.; Walster, G. W., Rump’s example revisited, Reliab. Comput., 8, 245-248 (2002) · Zbl 1001.65043
[19] Knuth, D. E., The Art of Computer Programming II: Seminumerical Algorithms (1998), Addison-Wesley: Addison-Wesley London · Zbl 0895.65001
[20] Koren, I., Computer Arithmetic Algorithms (2002), A.K. Peters Ltd.: A.K. Peters Ltd. Natick, MA · Zbl 0994.68186
[21] S. Krishnan, M. Foskey, T. Culver, J. Keyser, D. Manocha, Precise: Efficient multiprecision evaluation of algebraic roots and predicates for reliable geometric computations, Tech. Rep. TR00-008, Dept. Computer Science, Univ. North Carolina, 2000. Available from: <http://citeseer.nj.nec.com/krishnan00precise.html; S. Krishnan, M. Foskey, T. Culver, J. Keyser, D. Manocha, Precise: Efficient multiprecision evaluation of algebraic roots and predicates for reliable geometric computations, Tech. Rep. TR00-008, Dept. Computer Science, Univ. North Carolina, 2000. Available from: <http://citeseer.nj.nec.com/krishnan00precise.html · Zbl 1378.65059
[22] Metropolis, N.; Ashenhurst, R. L., Significant digit computer arithmetic, IRE Trans. Electron. Comput., EC-7, 265-267 (1958)
[23] Metropolis, N.; Ashenhurst, R. L., Unnormalized floating point arithmetic, J. ACM, 6, 3, 415-428 (1959) · Zbl 0121.12102
[24] Metropolis, N.; Rota, G. C.; Tanny, S. M., Significance arithmetic: the carrying algorithm, J. Comb. Theory (A), 14, 3, 386-421 (1973) · Zbl 0259.00001
[25] Metropolis, N.; Rota, G. C., Significance arithmetic: on the algebra of binary strings, (Collection: Studies in Numerical Analysis (1974), Academic Press: Academic Press London), 241-251
[26] Metropolis, N., Methods of significance arithmetic, (The State of the Art in Numerical Analysis, Proc. Conf., Univ. York, Heslington, 1976 (1977), Academic Press: Academic Press London), 179-192
[27] Metropolis, N.; Tanny, S. M., Significance arithmetic: the probability of carrying, Comput. Math. Appl., 3, 1, 77-81 (1977) · Zbl 0371.60015
[28] Details of the Multiple Precision Floating-point Reliable project can be found at <http://www.mpfr.org/; Details of the Multiple Precision Floating-point Reliable project can be found at <http://www.mpfr.org/
[29] Mutrie, M. P.W.; Bartels, R. H.; Char, B. W., An approach for floating-point error analysis using computer algebra, Proc. ISSAC, 284-293 (1992) · Zbl 0919.65033
[30] Neumaier, A., Interval Methods for Systems of Equations (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0706.15009
[31] Overton, M. L., Numerical Computing with IEEE Floating Point Arithmetic (2001), SIAM: SIAM Philadelphia · Zbl 0981.68057
[32] T.H. Rowan, Functional stability analysis of numerical algorithms, Ph.D. Thesis, University of Texas, Austin, USA, 1990; T.H. Rowan, Functional stability analysis of numerical algorithms, Ph.D. Thesis, University of Texas, Austin, USA, 1990
[33] S.M. Rump, Kleine Fehlerschranken bei Matrixproblemen, Ph.D. Thesis, University of Karlsruhe, Germany, 1980; S.M. Rump, Kleine Fehlerschranken bei Matrixproblemen, Ph.D. Thesis, University of Karlsruhe, Germany, 1980
[34] Rump, S. M., Algorithm for verified inclusions: theory & practice, (Moore, R. E., Reliability in Computing (1988), Academic Press: Academic Press San Diego), 109-126
[35] S.M. Rump, INTerval LABoratory, 2000, The INTLAB home page is located at <http://www.ti3.tu-harburg.de/ rump/intlab/index.html; S.M. Rump, INTerval LABoratory, 2000, The INTLAB home page is located at <http://www.ti3.tu-harburg.de/ rump/intlab/index.html
[36] Rump, S. M., Self-validating methods, Linear Algebra Appl., 324, 3-13 (2001) · Zbl 0978.65037
[37] Skeel, R. D.; Keiper, J. B., Elementary Numerical Computing with Mathematica (1993), McGraw-Hill: McGraw-Hill New York
[38] Sofroniou, M., Numerics in Mathematica 3.0, Math. J., 6, 4, 64-73 (1996)
[39] M. Sofroniou, G. Spaletta, Efficient computation of continued fractions, in press; M. Sofroniou, G. Spaletta, Efficient computation of continued fractions, in press · Zbl 1075.68104
[40] Sterbenz, P. H., Floating Point Computation (1974), Prentice Hall: Prentice Hall Englewood Cliffs, NJ, USA
[41] Strzebonski, A., Algebraic numbers in Mathematica 3.0, Math. J., 6, 4, 74-80 (1996)
[42] Strzebonski, A., Computing in the field of complex algebraic numbers, J. Symbolic Comput., 24, 647-656 (1997) · Zbl 0910.65029
[43] Strzebonski, A., A real polynomial decision algorithm using arbitrary-precision floating point arithmetic, Reliab. Comput., 5, 3, 337-346 (1999) · Zbl 1097.65526
[44] A. Strzebonski, Cylindrical algebraic decomposition using validated numerics, J. Symbolic Comput., submitted for publication; A. Strzebonski, Cylindrical algebraic decomposition using validated numerics, J. Symbolic Comput., submitted for publication · Zbl 1124.68123
[45] S.M. Tanny, Studies in significance arithmetic, Ph.D. Thesis, MIT, 1973; S.M. Tanny, Studies in significance arithmetic, Ph.D. Thesis, MIT, 1973
[46] C. Yap, K. Ouchi, The Real/Expr package home page is located at <http://www.cs.nyu.edu/exact/realexpr/; C. Yap, K. Ouchi, The Real/Expr package home page is located at <http://www.cs.nyu.edu/exact/realexpr/
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.