research-article

Efficient Calculations of Faithfully Rounded l₂-Norms of n-Vectors

Authors:

Shin’ichi OishiAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 41, Issue 4

Article No.: 24, Pages 1 - 20

https://doi.org/10.1145/2699469

Published: 12 October 2015 Publication History

Get Access

Abstract

In this article, we present an efficient algorithm to compute the faithful rounding of the l₂-norm of a floating-point vector. This means that the result is accurate to within 1 bit of the underlying floating-point type. This algorithm does not generate overflows or underflows spuriously, but does so when the final result calls for such a numerical exception to be raised. Moreover, the algorithm is well suited for parallel implementation and vectorization. The implementation runs up to 3 times faster than the netlib version on current processors.

References

[1]

E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. J. Dongarra, J. Du Croz, S. Hammarling, A. Greenbaum, A. McKenney, and D. Sorensen. 1999. LAPACK Users’ Guide (3rd ed.). Society for Industrial and Applied Mathematics, Philadelphia, PA.

Digital Library

Google Scholar

[2]

J. L. Blue. 1978. A portable Fortran program to find the Euclidean norm of a vector. ACM Transactions on Mathematical Software 4, 1, 15--23.

Digital Library

Google Scholar

[3]

T. J. Dekker. 1971. A floating-point technique for extending the available precision. Numererische Mathematik 18, 224--242.

Digital Library

Google Scholar

[4]

N. J. Higham. 2002. Accuracy and Stability of Numerical Algorithms (2nd ed.). Society for Industrial and Applied Mathematics, Philadelphia, PA.

Digital Library

Google Scholar

[5]

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

Google Scholar

[6]

X. S. Li, J. W. Demmel, D. H. Bailey, G. Henry, Y. Hida, J. Iskandar, W. Kahan, S. Y. Kang, A. Kapur, M. C. Martin, B. J. Thompson, T. Tung, and D. J. Yoo. 2002. Design, implementation and testing of extended and mixed precision BLAS. ACM Transactions on Mathematical Software 28, 2, 152--205.

Digital Library

Google Scholar

[7]

MPFR. MPFR (Multiple Precision Floating-Point Reliable Library). Retrieved August 25, 2015 from http://www.mpfr.org.

Google Scholar

[8]

J.-M. Muller, N. Brisebarre, F. de Dinechin, C.-P. Jeannerod, V. Lefèvre, G. Melquiond, N. Revol, D. Stehlé, and S. Torres. 2010. Handbook of Floating-Point Arithmetic. Birkhäuser Boston Inc., Boston, MA.

Digital Library

Google Scholar

[9]

T. Ogita, S. M. Rump, and S. Oishi. 2005. Accurate sum and dot product. SIAM Journal on Scientific Computing 26, 6, 1955--1988.

Digital Library

Google Scholar

[10]

S. M. Rump. 2009. Ultimately fast accurate summation. SIAM Journal on Scientific Computing 31, 5, 3466--3502.

Digital Library

Google Scholar

[11]

S. M. Rump, T. Ogita, and S.i Oishi. 2008a. Accurate floating-point summation. I. Faithful rounding. SIAM Journal on Scientific Computing 31, 1, 189--224.

Digital Library

Google Scholar

[12]

S. M. Rump, T. Ogita, and S. Oishi. 2008b. Accurate floating-point summation. II. Sign, K-fold faithful and rounding to nearest. SIAM Journal on Scientific Computing 31, 2, 1269--1302.

Digital Library

Google Scholar

[13]

Y.-K. Zhu and W. B. Hayes. 2009. Correct rounding and a hybrid approach to exact floating-point summation. SIAM Journal on Scientific Computing 31, 4, 2981--3001.

Digital Library

Google Scholar

[14]

Y.-K. Zhu and W. B. Hayes. 2010. Algorithm 908: Online exact summation of floating-point streams. ACM Transactions on Mathematical Software 37, 3.

Digital Library

Google Scholar

Cited By

View all

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
Hernandez FCortes DRamirez-Salinas MVilla-Vargas L(2023)A Tool for Control Research Using Evolutionary Algorithm That Generates Controllers with a Pre-Specified MorphologyAlgorithms10.3390/a1607032916:7(329)Online publication date: 8-Jul-2023
https://doi.org/10.3390/a16070329
Lefèvre VLouvet NMuller JPicot JRideau L(2023)Accurate Calculation of Euclidean Norms Using Double-word ArithmeticACM Transactions on Mathematical Software10.1145/356867249:1(1-34)Online publication date: 21-Mar-2023
https://dl.acm.org/doi/10.1145/3568672
Show More Cited By

Index Terms

Efficient Calculations of Faithfully Rounded l₂-Norms of n-Vectors
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Arbitrary-precision arithmetic

Recommendations

Accurate Calculation of Euclidean Norms Using Double-word Arithmetic
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 ...
What every computer scientist should know about floating-point arithmetic

Floating-point arithmetic is considered as esoteric subject by many people. This is rather surprising, because floating-point is ubiquitous in computer systems: Almost every language has a floating-point datatype; computers from PCs to supercomputers ...
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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 41, Issue 4

October 2015

160 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/2835205

Editor:
Michael A. Heroux
Sandia National Laboratories, 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: 12 October 2015

Accepted: 01 November 2014

Revised: 01 July 2014

Received: 01 December 2013

Published in TOMS Volume 41, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

CNRS/JSPS Exchange Scientist

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
252
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Hernandez FCortes DRamirez-Salinas MVilla-Vargas L(2023)A Tool for Control Research Using Evolutionary Algorithm That Generates Controllers with a Pre-Specified MorphologyAlgorithms10.3390/a1607032916:7(329)Online publication date: 8-Jul-2023
https://doi.org/10.3390/a16070329
Lefèvre VLouvet NMuller JPicot JRideau L(2023)Accurate Calculation of Euclidean Norms Using Double-word ArithmeticACM Transactions on Mathematical Software10.1145/356867249:1(1-34)Online publication date: 21-Mar-2023
https://dl.acm.org/doi/10.1145/3568672
Rump S(2023)Fast and accurate computation of the Euclidean norm of a vectorJapan Journal of Industrial and Applied Mathematics10.1007/s13160-023-00593-840:3(1391-1419)Online publication date: 6-Jun-2023
https://doi.org/10.1007/s13160-023-00593-8
Li CDu PLi KLiu YJiang HQuan Z(2022)Accurate Goertzel Algorithm: Error Analysis, Validations and ApplicationsMathematics10.3390/math1011178810:11(1788)Online publication date: 24-May-2022
https://doi.org/10.3390/math10111788
Novaković VSinger S(2020)Implicit Hari–Zimmermann algorithm for the generalized SVD on the GPUsThe International Journal of High Performance Computing Applications10.1177/1094342020972772(109434202097277)Online publication date: 10-Dec-2020
https://doi.org/10.1177/1094342020972772
Borges C(2020)Algorithm 1014ACM Transactions on Mathematical Software10.1145/342844647:1(1-12)Online publication date: 8-Dec-2020
https://dl.acm.org/doi/10.1145/3428446
Lange MRump S(2020)Faithfully Rounded Floating-point ComputationsACM Transactions on Mathematical Software10.1145/329095546:3(1-20)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.1145/3290955
Rump S(2019)Error Bounds for Computer Arithmetics2019 IEEE 26th Symposium on Computer Arithmetic (ARITH)10.1109/ARITH.2019.00011(1-14)Online publication date: Jun-2019
https://doi.org/10.1109/ARITH.2019.00011
Hanson RHopkins T(2017)Remark on Algorithm 539ACM Transactions on Mathematical Software10.1145/313444144:3(1-23)Online publication date: 18-Dec-2017
https://dl.acm.org/doi/10.1145/3134441
Show More Cited By

View Options

Login options

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

Cited By

Index Terms

Recommendations

Accurate Calculation of Euclidean Norms Using Double-word Arithmetic

What every computer scientist should know about floating-point arithmetic

Options for Denormal Representation in Logarithmic Arithmetic