research-article

Accurate Calculation of Euclidean Norms Using Double-word Arithmetic

Authors:

Vincent Lefèvre,

Nicolas Louvet,

Jean-Michel Muller,

Laurence RideauAuthors Info & Claims

ACM Transactions on Mathematical Software, Volume 49, Issue 1

Article No.: 1, Pages 1 - 34

https://doi.org/10.1145/3568672

Published: 21 March 2023 Publication History

Abstract

We consider the computation of the Euclidean (or L2) norm of an n-dimensional vector in floating-point arithmetic. We review the classical solutions used to avoid spurious overflow or underflow and/or to obtain very accurate results. We modify a recently published algorithm (that uses double-word arithmetic) to allow for a very accurate solution, free of spurious overflows and underflows. To that purpose, we use a double-word square-root algorithm of which we provide a tight error analysis. The returned L2 norm will be within very slightly more than 0.5 ulp from the exact result, which means that we will almost always provide correct rounding.

Supplementary Material

3568672.supp (3568672.supp.pdf)

Supplementary material

Download
272.09 KB

References

[1]

E. Anderson. 2017. Algorithm 978: Safe scaling in the level 1 BLAS. ACM Trans. Math. Softw. 44, 1 (July2017). DOI:

Digital Library

[2]

N. H. F. Beebe. 2017. The Mathematical-function Computation Handbook: Programming Using the MathCW Portable Software Library. Springer. 978-3-319-64109-6 (hardcover), 978-3-319-64110-2 (e-book)DOI:

[3]

Yves Bertot and Pierre Castéran. 2004. Interactive Theorem Proving and Program Development. Coq’Art: The Calculus of Inductive Constructions. Springer.

Digital Library

[4]

J. L. Blue. 1978. A portable Fortran program to find the Euclidean norm of a vector. ACM Trans. Math. Softw. 4, 1 (Mar.1978), 15–23. DOI:

Digital Library

[5]

G. Bohlender, W. Walter, P. Kornerup, and D. W. Matula. 1991. Semantics for exact floating point operations. In Proceedings of the 10th IEEE Symposium on Computer Arithmetic. IEEE Computer Society Press, 22–26.

[6]

S. Boldo and M. Daumas. 2003. Representable correcting terms for possibly underflowing floating point operations. In Proceedings of the 16th Symposium on Computer Arithmetic. IEEE Computer Society Press, 79–86.

[7]

S. Boldo, S. Graillat, and J.-M. Muller. 2017. On the robustness of the 2Sum and Fast2Sum algorithms. ACM Trans. Math. Softw. 44, 1 (July2017). DOI:

Digital Library

[8]

Sylvie Boldo, Jacques-Henri Jourdan, Xavier Leroy, and Guillaume Melquiond. 2015. Verified compilation of floating-point computations. J. Autom. Reason. 54, 2 (2015), 135–163. DOI:

Digital Library

[9]

S. Boldo, C. Q. Lauter, and J.-M. Muller. 2021. Emulating round-to-nearest-ties-to-zero “augmented” floating-point operations using round-to-nearest-ties-to-even arithmetic. IEEE Trans. Comput. 70, 7 (July2021), 1046–1058.

[10]

S. Boldo, C. Lelay, and G. Melquiond. 2016. Formalization of real analysis: A survey of proof assistants and libraries. Math. Struct. Comput. Sci. 26, 7 (2016), 1196–1233. Retrieved from https://hal.inria.fr/hal-00806920.

[11]

S. Boldo and G. Melquiond. 2011. Flocq: A unified library for proving floating-point algorithms in Coq. In Proceedings of the IEEE 20th Symposium on Computer Arithmetic. 243–252. DOI:

Digital Library

[12]

S. Boldo and G. Melquiond. 2017. Computer Arithmetic and Formal Proofs: Verifying Floating-point Algorithms with the Coq System. Elsevier.

[13]

C. F. Borges. 2020. Algorithm 1014: An improved algorithm for hypot(x,y). ACM Trans. Math. Softw. 47, 1 (Dec.2020). DOI:

Digital Library

[14]

F. de Dinechin, C. Lauter, J.-M. Muller, and S. Torres. 2013. On Ziv’s rounding test. ACM Trans. Math. Softw. 39, 4 (2013).

Digital Library

[15]

T. J. Dekker. 1971. A floating-point technique for extending the available precision. Numer. Math. 18, 3 (1971), 224–242.

Digital Library

[16]

J. Demmel and H. D. Nguyen. 2013. Numerical reproducibility and accuracy at ExaScale. In Proceedings of the 21st IEEE Symposium on Computer Arithmetic. 235–237.

Digital Library

[17]

M. Fasi, N. J. Higham, F. Lopez, T. Mary, and M. Mikaitis. 2022. Matrix Multiplication in Multiword Arithmetic: Error Analysis and Application to GPU Tensor Cores. (Jan.2022). Retrieved from https://hal.archives-ouvertes.fr/hal-03543925.

[18]

S. Graillat, C. Lauter, P. T. P. Tang, N. Yamanaka, and S. Oishi. 2015. Efficient calculations of faithfully rounded L2-norms of n-Vectors. ACM Trans. Math. Softw. 41, 4 (Oct.2015), 1–20.

Digital Library

[19]

R. J. Hanson and T. Hopkins. 2017. Remark on algorithm 539: A modern Fortran reference implementation for carefully computing the Euclidean norm. ACM Trans. Math. Softw. 44, 3 (Dec.2017). DOI:

Digital Library

[20]

J. R. Hauser. 1996. Handling floating-point exceptions in numeric programs. ACM Trans. Program. Lang. Syst. 18, 2 (1996), 139–174. DOI:

Digital Library

[21]

G. Henry, P. T. P. Tang, and A. Heinecke. 2019. Leveraging the bfloat16 artificial intelligence datatype for higher-precision computations. In Proceedings of the IEEE 26th Symposium on Computer Arithmetic (ARITH’19). 69–76. DOI:

[22]

Y. Hida, X. S. Li, and D. H. Bailey. 2012. C++/Fortran-90 Double-double and Quad-double Package, Release 2.3.17. (Mar.2012). Retrieved from https://www.davidhbailey.com/dhbsoftware/.

[23]

Y. Hida, X. S. Li, and D. H. Bailey. 2001. Algorithms for quad-double precision floating-point arithmetic. In Proceedings of the IEEE Symposium on Computer Arithmetic. 155–162. DOI:

[24]

N. J. Higham. 2002. Accuracy and Stability of Numerical Algorithms (2nd ed.). SIAM, Philadelphia, PA.

Digital Library

[25]

N. J. Higham and T. Mary. 2019. A new approach to probabilistic rounding error analysis. SIAM J. Sci. Computing 41, 5 (2019), A2815–A2835. DOI:

[26]

T. E. Hull, T. F. Fairgrieve, and P. T. P. Tang. 1994. Implementing complex elementary functions using exception handling. ACM Trans. Math. Softw. 20, 2 (June1994), 215–244.

Digital Library

[27]

IEEE. 2019. IEEE Standard for Floating-Point Arithmetic (IEEE Std 754-2019). DOI:

[28]

C.-P. Jeannerod, N. Louvet, J.-M. Muller, and A. Panhaleux. 2011. Midpoints and exact points of some algebraic functions in floating-point arithmetic. IEEE Trans. Comput. 60, 2 (Feb.2011), 228–241. DOI:

Digital Library

[29]

C.-P. Jeannerod, J.-M. Muller, and P. Zimmermann. 2018. On various ways to split a floating-point number. In Proceedings of the 25th IEEE Symposium on Computer Arithmetic. 53–60. DOI:

[30]

C.-P. Jeannerod and S. M. Rump. 2018. On relative errors of floating-point operations: Optimal bounds and applications. Math. Comput. 87 (2018), 803–819. DOI:

[31]

F. Johansson. 2017. Arb: Efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Trans. Comput. 66, 8 (2017), 1281–1292. DOI:

Digital Library

[32]

M. Joldes, J.-M. Muller, and V. Popescu. 2017. Tight and rigorous error bounds for basic building blocks of double-word arithmetic. ACM Trans. Math. Softw. 44, 2 (Oct.2017), 27. DOI:

Digital Library

[33]

W. Kahan. 1996. Lecture Notes on the Status of IEEE-754. Retrieved from https://people.eecs.berkeley.edu/wkahan/ieee754status/IEEE754.PDF.

[34]

D. Knuth. 1998. The Art of Computer Programming (3rd ed.). Vol. 2. Addison-Wesley, Reading, MA.

[35]

T. Kouya. 2021. Acceleration of LU decomposition supporting double-double, triple-double, and quadruple-double precision floating-point arithmetic with AVX2. In Proceedings of the IEEE 28th Symposium on Computer Arithmetic (ARITH’21). 54–61. DOI:

[36]

X. Li, J. Demmel, D. H. Bailey, G. Henry, Y. Hida, J. Iskandar, W. Kahan, A. Kapur, M. Martin, T. Tung, and D. J. Yoo. 2000. Design, Implementation and Testing of Extended and Mixed Precision BLAS. Technical Report 45991. Lawrence Berkeley National Laboratory. Retrieved from https://www.netlib.org/lapack/lawnspdf/lawn149.pdf.

[37]

O. Møller. 1965. Quasi double-precision in floating-point addition. BIT Numer. Math. 5 (1965), 37–50.

Digital Library

[38]

J.-M. Muller, N. Brunie, F. de Dinechin, C.-P. Jeannerod, M. Joldes, V. Lefèvre, G. Melquiond, N. Revol, and S. Torres. 2018. Handbook of Floating-point Arithmetic, 2nd Edition. Birkhäuser, Boston.

Digital Library

[39]

J.-M. Muller and L. Rideau. 2022. Formalization of double-word arithmetic, and comments on “Tight and rigorous error bounds for basic building blocks of double-word arithmetic.” ACM Trans. Math. Softw. 46, 1 (Mar.2022), 1–24.

Digital Library

[40]

Y. Nievergelt. 2003. Scalar fused multiply-add instructions produce floating-point matrix arithmetic provably accurate to the penultimate digit. ACM Trans. Math. Softw. 29, 1 (2003), 27–48.

Digital Library

[41]

E. J. Riedy and J. Demmel. 2018. Augmented arithmetic operations proposed for IEEE-754 2018. In Proceedings of the 25th IEEE Symposium on Computer Arithmetic. 45–52. DOI:

[42]

S. M. Rump and M. Lange. 2017. Error estimates for the summation of real numbers with application to floating-point summation. BIT Numer. Math. 57 (2017), 927–941.

Digital Library

[43]

S. M. Rump and M. Lange. 2020. Faithfully rounded floating-point computation. ACM Trans. Math. Softw. 46, 3 (July2020), 1–20. DOI:

Digital Library

Cited By

Mahdavi M(2024)Hardware Realization of Vector and Matrix Norm Calculation for Signal Processing Applications2024 11th International Conference on Wireless Networks and Mobile Communications (WINCOM)10.1109/WINCOM62286.2024.10655769(1-7)Online publication date: 23-Jul-2024
https://doi.org/10.1109/WINCOM62286.2024.10655769
Hubrecht TJeannerod CMuller J(2024)Useful applications of correctly-rounded operators of the form ab + cd + e2024 IEEE 31st Symposium on Computer Arithmetic (ARITH)10.1109/ARITH61463.2024.00015(32-39)Online publication date: 10-Jun-2024
https://doi.org/10.1109/ARITH61463.2024.00015
Novaković V(2024)Accurate complex Jacobi rotationsJournal of Computational and Applied Mathematics10.1016/j.cam.2024.116003450:COnline publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1016/j.cam.2024.116003

Index Terms

Accurate Calculation of Euclidean Norms Using Double-word Arithmetic
1. Mathematics of computing
  1. Mathematical software

Recommendations

Formalization of Double-Word Arithmetic, and Comments on “Tight and Rigorous Error Bounds for Basic Building Blocks of Double-Word Arithmetic”
Recently, a complete set of algorithms for manipulating double-word numbers (some classical, some new) was analyzed [16]. We have formally proven all the theorems given in that article, using the Coq proof assistant. The formal proof work led us to: (i) ...
Tight and Rigorous Error Bounds for Basic Building Blocks of Double-Word Arithmetic

We analyze several classical basic building blocks of double-word arithmetic (frequently called “double-double arithmetic” in the literature): the addition of a double-word number and a floating-point number, the addition of two double-word numbers, the ...
Options for Denormal Representation in Logarithmic Arithmetic
Abstract
Economical hardware often uses a FiXed-point Number System (FXNS), whose constant absolute precision is acceptable for many signal-processing algorithms. The almost-constant relative precision of the more expensive Floating-Point (FP) number ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 49, Issue 1

March 2023

250 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/3587918

Editors:
Zhaojun Bai
University of California at Davis, USA
,
Wolfgang Bangerth
Colorado State University, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 March 2023

Online AM: 25 October 2022

Accepted: 30 September 2022

Revised: 11 July 2022

Received: 17 December 2021

Published in TOMS Volume 49, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

French Agence Nationale de la Recherche

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
303
Total Downloads

Downloads (Last 12 months)95
Downloads (Last 6 weeks)6

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mahdavi M(2024)Hardware Realization of Vector and Matrix Norm Calculation for Signal Processing Applications2024 11th International Conference on Wireless Networks and Mobile Communications (WINCOM)10.1109/WINCOM62286.2024.10655769(1-7)Online publication date: 23-Jul-2024
https://doi.org/10.1109/WINCOM62286.2024.10655769
Hubrecht TJeannerod CMuller J(2024)Useful applications of correctly-rounded operators of the form ab + cd + e2024 IEEE 31st Symposium on Computer Arithmetic (ARITH)10.1109/ARITH61463.2024.00015(32-39)Online publication date: 10-Jun-2024
https://doi.org/10.1109/ARITH61463.2024.00015
Novaković V(2024)Accurate complex Jacobi rotationsJournal of Computational and Applied Mathematics10.1016/j.cam.2024.116003450:COnline publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1016/j.cam.2024.116003

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents