Further analysis of Kahan's algorithm for the accurate computation of 2 x 2 determinants

Claude-Pierre Jeannerod 1, 2, * Nicolas Louvet 2, 1 Jean-Michel Muller 2, 1
* Auteur correspondant
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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.
Type de document :
Article dans une revue
Mathematics of Computation, American Mathematical Society, 2013, 82 (284), pp.2245-2264. 〈10.1090/S0025-5718-2013-02679-8〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00649347
Contributeur : Claude-Pierre Jeannerod <>
Soumis le : samedi 13 juillet 2013 - 11:23:53
Dernière modification le : samedi 21 avril 2018 - 01:27:16
Document(s) archivé(s) le : mercredi 5 avril 2017 - 10:57:25

Fichier

JeannerodLouvetMuller13.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Claude-Pierre Jeannerod, Nicolas Louvet, Jean-Michel Muller. Further analysis of Kahan's algorithm for the accurate computation of 2 x 2 determinants. Mathematics of Computation, American Mathematical Society, 2013, 82 (284), pp.2245-2264. 〈10.1090/S0025-5718-2013-02679-8〉. 〈ensl-00649347v4〉

Partager

Métriques

Consultations de la notice

291

Téléchargements de fichiers

186