On the componentwise accuracy of complex floating-point division with an FMA

Claude-Pierre Jeannerod 1, 2 Nicolas Louvet 1, 2 Jean-Michel Muller 1, 2
1 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : This paper deals with the accuracy of complex division in radix-two floating-point arithmetic. Assuming that a fused multiply-add (FMA) instruction is available and that no underflow/overflow occurs, we study how to ensure high relative accuracy in the componentwise sense. Since this essentially reduces to evaluating accurately three expressions of the form ac+bd, an obvious approach would be to perform three calls to Kahan's compensated algorithm for 2 by 2 determinants. However, in the context of complex division, two of those expressions are such that ac and bd have the same sign, suggesting that cheaper schemes should be used here (since cancellation cannot occur). We first give a detailed accuracy analysis of such schemes for the sum of two nonnegative products, providing not only sharp bounds on both their absolute and relative errors, but also sufficient conditions for the output of one of them to coincide with the output of Kahan's algorithm. By combining Kahan's algorithm with this particular scheme, we then deduce two new division algorithms. Our first algorithm is a straight-line program whose componentwise relative error is always at most 5u+13u^2 with u the unit roundoff; we also provide examples of inputs for which the error of this algorithm approaches 5u, thus showing that our upper bound is essentially the best possible. When tests are allowed we show with a second algorithm that the bound above can be further reduced to (9/2) u+9u^2, and that this improved bound is reasonably sharp.
Type de document :
Communication dans un congrès
21st IEEE Symposium on Computer Arithmetic, Apr 2013, Austin, TX, United States. IEEE Computer Society, pp.83--90, 2013
Liste complète des métadonnées

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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00734339
Contributeur : Jean-Michel Muller <>
Soumis le : jeudi 7 février 2013 - 08:55:21
Dernière modification le : lundi 5 octobre 2015 - 16:57:04
Document(s) archivé(s) le : mercredi 8 mai 2013 - 03:52:05

Fichier

Jeannerod_Louvet_Muller_final....
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00734339, version 2

Collections

Citation

Claude-Pierre Jeannerod, Nicolas Louvet, Jean-Michel Muller. On the componentwise accuracy of complex floating-point division with an FMA. 21st IEEE Symposium on Computer Arithmetic, Apr 2013, Austin, TX, United States. IEEE Computer Society, pp.83--90, 2013. 〈ensl-00734339v2〉

Partager

Métriques

Consultations de
la notice

534

Téléchargements du document

257