Further analysis of Kahan’s algorithm for the accurate computation of $2\times 2$ determinants
HTML articles powered by AMS MathViewer
- by Claude-Pierre Jeannerod, Nicolas Louvet and Jean-Michel Muller PDF
- Math. Comp. 82 (2013), 2245-2264 Request permission
Abstract:
We provide a detailed analysis of Kahan’s algorithm for the accurate computation of the determinant of a $2 \times 2$ matrix. This algorithm requires the availability of a fused multiply-add instruction. Assuming radix-$\beta$, precision-$p$ floating-point arithmetic with $\beta$ even, $p \geq 2$, and barring overflow or underflow we show that the absolute error of Kahan’s algorithm is bounded by $(\beta +1)/2$ ulps of the exact result and that the relative error is bounded by $2u$ with $u=\frac {1}{2}\beta ^{1-p}$ the unit roundoff. Furthermore, we provide input values showing that i) when $\beta /2$ is odd—which holds for $2$ and $10$, the two radices that matter in practice—the absolute error bound is optimal; ii) the relative error bound is asymptotically optimal, that is, for such input the ratio (relative error)/$2u$ has the form $1-O(\beta ^{-p})$. We also give relative error bounds parametrized by the relative order of magnitude of the two products in the determinant, and we investigate whether the error bounds can be improved when adding constraints: When the products in the determinant have opposite signs, which covers the computation of a sum of squares, or when Kahan’s algorithm is used for computing the discriminant of a quadratic equation.References
- Sylvie Boldo, Kahan’s algorithm for a correct discriminant computation at last formally proven, IEEE Trans. Comput. 58 (2009), no. 2, 220–225. MR 2655570, DOI 10.1109/TC.2008.200
- Richard Brent, Colin Percival, and Paul Zimmermann, Error bounds on complex floating-point multiplication, Math. Comp. 76 (2007), no. 259, 1469–1481. MR 2299783, DOI 10.1090/S0025-5718-07-01931-X
- M. Cornea, J. Harrison, and P. T. P. Tang, Scientific computing on Itanium®-based systems, Intel Press, Hillsboro, OR, 2002.
- Y. Hida, X. S. Li, and D. H. Bailey, Algorithms for quad-double precision floating-point arithmetic, Proceedings of the 15th IEEE Symposium on Computer Arithmetic (ARITH-16) (Vail, CO) (N. Burgess and L. Ciminiera, eds.), June 2001, pp. 155–162.
- Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629
- Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606, DOI 10.1137/1.9780898718027
- E. Hokenek, R. K. Montoye, and P. W. Cook, Second-generation RISC floating point with multiply-add fused, IEEE Journal of Solid-State Circuits 25 (1990), no. 5, 1207–1213.
- IEEE Computer Society, IEEE standard for floating-point arithmetic, IEEE Standard 754-2008, August 2008, available at http://ieeexplore.ieee.org/servlet/opac?punumber=4610933.
- R. M. Jessani and C. H. Olson, The floating-point unit of the PowerPC 603e microprocessor, IBM Journal of Research and Development 40 (1996), no. 5, 559–566.
- W. Kahan, Lecture notes on the status of IEEE-754, PDF file accessible at http://www.cs.berkeley.edu/~wkahan/ieee754status/IEEE754.PDF, 1996.
- —, Matlab’s loss is nobody’s gain, Available at http://www.cs.berkeley.edu/~wkahan/MxMulEps.pdf, 1998.
- —, On the cost of floating-point computation without extra-precise arithmetic, Available at http://http.cs.berkeley.edu/~wkahan/Qdrtcs.pdf, 2004.
- Alan H. Karp and Peter Markstein, High-precision division and square root, ACM Trans. Math. Software 23 (1997), no. 4, 561–589. MR 1671702, DOI 10.1145/279232.279237
- Guillaume Melquiond and Sylvain Pion, Formally certified floating-point filters for homogeneous geometric predicates, Theor. Inform. Appl. 41 (2007), no. 1, 57–69. MR 2330043, DOI 10.1051/ita:2007005
- R. K. Montoye, E. Hokonek, and S. L. Runyan, Design of the IBM RISC System/6000 floating-point execution unit, IBM Journal of Research and Development 34 (1990), no. 1, 59–70.
- Yves Nievergelt, Scalar fused multiply-add instructions produce floating-point matrix arithmetic provably accurate to the penultimate digit, ACM Trans. Math. Software 29 (2003), no. 1, 27–48. MR 2001452, DOI 10.1145/641876.641878
- Siegfried Rump, Takeshi Ogita, and Shin’ichi Oishi, Accurate floating-point summation. I. Faithful rounding, SIAM J. Sci. Comput. 31 (2008), no. 1, 189–224. MR 2460776, DOI 10.1137/050645671
Additional Information
- Claude-Pierre Jeannerod
- Affiliation: INRIA, Laboratoire LIP (CNRS, ENS de Lyon, INRIA, UCBL), Université de Lyon — 46, allée d’Italie, 69364 Lyon cedex 07, France
- MR Author ID: 644190
- Email: claude-pierre.jeannerod@ens-lyon.fr
- Nicolas Louvet
- Affiliation: UCBL, Laboratoire LIP (CNRS, ENS de Lyon, INRIA, UCBL), Université de Lyon — 46, allée d’Italie, 69364 Lyon cedex 07, France
- MR Author ID: 893389
- Email: nicolas.louvet@ens-lyon.fr
- Jean-Michel Muller
- Affiliation: CNRS, Laboratoire LIP (CNRS, ENS de Lyon, INRIA, UCBL), Université de Lyon — 46, allée d’Italie, 69364 Lyon cedex 07, France
- Email: jean-michel.muller@ens-lyon.fr
- Received by editor(s): December 7, 2011
- Received by editor(s) in revised form: January 17, 2012
- Published electronically: March 4, 2013
- © Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 82 (2013), 2245-2264
- MSC (2010): Primary 65G50
- DOI: https://doi.org/10.1090/S0025-5718-2013-02679-8
- MathSciNet review: 3073198