Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2010): 65G50
  • Retrieve articles in all journals with MSC (2010): 65G50
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