Exploiting fast hardware floating point in high precision computation

ABSTRACT

We apply an iterative refinement method based on a linear Newton iteration to solve a particular group of high precision computation problems. The method generates an initial solution at hardware floating point precision using a traditional method and then repeatedly refines this solution to higher precision, exploiting hardware floating point computation in each iteration. This is in contrast to direct solution of the high precision problem completely in software floating point. Theoretical cost analysis, as well as experimental evidence, shows a significant reduction in computational cost is achieved by the iterative refinement method on this group of problems.

REFERENCES

• 1: Richard P. Brent, A Fortran Multiple-Precision Arithmetic Package, ACM Transactions on Mathematical Software (TOMS), v.4 n.1, p.57-70, March 1978 [doi>10.1145/355769.355775]
• 2: Germund Dahlquist , Ake Bjorck, Numerical Methods, Dover Publications, Incorporated, 2003
• 3: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 4: George E. Forsythe , Michael A. Malcolm , Cleve B. Moler, Computer Methods for Mathematical Computations, Prentice Hall Professional Technical Reference, 1977
• 5: Forsythe, G. and Moler, C. Computer Solution of Linear Algebraic Systems. Prentice-Hall, Englewood Cliffs, NJ, 1967.
• 6: Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
• 7: Geddes, K. and Zheng, W. Exploiting fast hardware floating point in high precision computation. Technical Report CS-2002-41, School of Computer Science, University of Waterloo, Waterloo, Canada, 2002. {http://www.uwaterloo.ca/˜kogeddes/papers/TR200241.ps.}
• 8: Golub, G. and Van Loan, C. Matrix Computations. The Johns Hopkins University Press, Baltimore, MD, 1989.
• 9: Granlund, T. GNU MP: The GNU Multiple Precision Arithmetic Library, 2003. Version 4.1.2, http://www.swox.com/gmp/.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms

Keywords:
arbitrary precision, floating point, iterative refinement, least squares, linear systems, multiple precision, nonlinear systems