Scalar fused multiply-add instructions produce floating-point matrix arithmetic provably accurate to the penultimate digit

ABSTRACT

Combined with doubly compensated summation, scalar fused multiply-add instructions redefine the concept of floating-point arithmetic, because they allow for the computation of sums of real or complex matrix products accurate to the penultimate digit. Particular cases include complex arithmetic, dot products, cross products, residuals of linear systems, determinants of small matrices, discriminants of quadratic, cubic, or quartic equations, and polynomials.

REFERENCES

• 1: Abbott, P. H., Brash, D. G., Clark, C. W. III, Crone, C. J., Ehrman, J. R., Ewart, G. W., Goodrich, C. A., Hack, M., Kapernick, J. S., Minchau, B. J., Shepard, W. C., R. M. Smith, S., Tallman, R., Walkowiak, S., Watanabe, A., and White, W. R. 1999. Architecture and software support in IBM S/390 parallel enterprise servers for IEEE floating-point arithmetic. IBM J. Res. Develop. 43, 5/6 (Sept./Nov.), 723--760.
• 2: Apple Computer, Inc. 2002. Altivec instruction cross-reference. http://developer.apple.com/hardware/ve/instructions/vec_madd.html.
• 3: Birkhoff, G. and MacLane, S. 1977. A Survey of Modern Algebra, 4th ed. Macmillan, New York, NY.
• 4: Bleher, J. H. 2001. Elements of scientific computing. In Perspectives on Enclosure Methods, U. Kulisch, R. Lohner, and A. Facius, Eds. Springer-Verlag, New York, 99--103.
• 5: Chandrasekharan, K. 1985. Elliptic Functions. Springer-Verlag, Berlin-Heidelberg-New York.
• 6: Chorin, A. J. and Marsden, J. E. 1993. A Mathematical Introduction to Fluid Mechanics, 3rd ed. Texts in Applied Mathematics, vol. 4. Springer-Verlag, New York, N.Y.
• 7: James S. Coan, Advanced Basic: Applications and Problems, Macmillan Publishing Co., Inc., Indianapolis, IN, 1976
• 8: Coleman, T. F. and Van Loan, C. 1988. Handbook for Matrix Computations. Society for Industrial and Applied Mathematics, Philadelphia, Pa.
• 9: Dekker, T. J. 1971. A floating-point technique for extending the available precision. Num. Math. 18, 224--242.
• 10: James Demmel , W. Kahan, Accurate singular values of bidiagonal matrices, SIAM Journal on Scientific and Statistical Computing, v.11 n.5, p.873-912, September 1990 [doi>10.1137/0911052]
• 11: Dickson, L. E. 1914. Elementary Theory of Equations. Wiley, London, UK.
• 12: Duff, I. S. 1996. Foreword. In Lectures on Finite Precisikon Computations. Society for Industrial and Applied Mathematics, Philadelphia, Pa, xiii--xiv.
• 13: Forsythe, G. E. 1970. Pitfalls in computation, or why a math book isn't enough. Amer. Math. Monthly 77, 9 (Nov.), 931--956.
• 14: G Bohlender , K Gruner, Realization of an optimal computer arithmetic, Proc. of the symposium on A new approach to scientific computation, p.247-268, December 1983, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, United States
• 15: David Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys (CSUR), v.23 n.1, p.5-48, March 1991 [doi>10.1145/103162.103163]
• 16: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 17: Thomas A. Grandine, Applications of Contouring, SIAM Review, v.42 n.2, p.297-316, June 2000 [doi>10.1137/S003614459936403X]
• 18: Hammer, R., Neaga, M., and Ratz, D. 1993. PASCAL-XSC: New concepts for scientific computation and numerical data processing. In Scientific Computing with Automatic Result Verification, E. Adams and U. Kulisch, Eds. Mathematics in Science and Engineering, vol. 189. Academic Press, Orlando, Fla., 15--44.
• 19: Peter Henrici, Essentials of Numerical Analysis with Pocket Calculator Demonstrations, John Wiley & Sons, Inc., New York, NY, 1982
• 20: Hewlett-Packard Co. 1984. HP-15C Advanced Functions Handbook. Hewlett-Packard Co., Corvallis Division, 1000 NE Circle Blvd., Corvallis, OR 97330, USA.
• 21: Hewlett-Packard Co. 1986. HP-28C Reference Manual, 1st ed. Hewlett-Packard Co., Corvallis Division, 1000 NE Circle Blvd., Corvallis, OR 97330, USA.
• 22: Hewlett-Packard Co. 1987. HP-28S Reference Manual, 1st ed. Hewlett-Packard Co., Corvallis Division, 1000 NE Circle Blvd., Corvallis, OR 97330, USA.
• 23: Hewlett-Packard Co. 1990. HP 48SX Scientific Expandable Calculator Owner's Manual, 1st ed. Hewlett-Packard Co., Corvallis Division, 1000 NE Circle Blvd., Corvallis, OR 97330, USA.
• 24: Hewlett-Packard Co. 1994. HP 48G Series User's Guide, 7th ed. Hewlett-Packard Co., Corvallis Division, 1000 NE Circle Blvd., Corvallis, OR 97330, USA.
• 25: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996
• 26: E. Hokenek , R. K. Montoye, Leading-zero anticipator (LZA) in the IBM RISC System/6000 floating-point execution unit, IBM Journal of Research and Development, v.34 n.1, p.71-77, Jan. 1990
• 27: Institute of Electrical and Electronic Engineers. 1985. IEEE Standard for Binary Floating-Point Arithmetic (ANSI/IEEE Std 754-1985). Institute of Electrical and Electronic Engineers, 345 East 47th Street, New York, NY 10017.
• 28: Institute of Electrical and Electronic Engineers. 1987. IEEE Standard for Radix-Independent Floating-Point Arithmetic (ANSI/IEEE Std 854-1987). Institute of Electrical and Electronic Engineers, 345 East 47th Street, New York, NY 10017.
• 29: Intel Corporation. 2001. Introducing the Intel Itanium architecture. In 2001: http://developer.intel.com/software/products/itc/architec/itanium/arch_mod/index.htm; in 2002: http://www.intel.com/design/Itanium/index.htm.
• 30: Kahan, W. M. 1972. A survey of error analysis. In Information Processing 71: Proceedings of IFIP Congress 71, Volume 2---Applications, C. V. Freiman, Ed. 1214--1239.
• 31: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 32: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 33: U W Kulisch , W L Miranker, The arithmetic of the digital computer: A new approach, SIAM Review, v.28 n.1, p.1-40, March 1986 [doi>10.1137/1028001]
• 34: Lawo, C. 1993. C-XSC: A programming environment for verified scientific computating and numerical data processing. In Scientific Computing with Automatic Result Verification, E. Adams and U. Kulisch, Eds. Mathematics in Science and Engineering, vol. 189. Academic Press, Orlando, Fla., 71--86.
• 35: P. W. Markstein, Computation of elementary functions on the IBM RISC System/6000 processor, IBM Journal of Research and Development, v.34 n.1, p.111-119, Jan. 1990
• 36: R. K. Montoye , E. Hokenek , S. L. Runyon, Design of the IBM RISC System/6000 floating-point execution unit, IBM Journal of Research and Development, v.34 n.1, p.59-70, Jan. 1990
• 37: O'Connell, F. P. and White, S. W. 2000. POWER3: The next generation of PowerPC processors. IBM J. Res. Devel. 44, 6 (Nov.), 873--884.
• 38: R. R. Oehler , R. D. Groves, IBM RISC System/6000 processor architecture, IBM Journal of Research and Development, v.34 n.1, p.23-36, Jan. 1990
• 39: Joseph O'Rourke, Computational geometry in C, Cambridge University Press, New York, NY, 1994
• 40: Michael L. Overton, Numerical computing with IEEE floating point arithmetic, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 41: Douglas M. Priest, On properties of floating point arithmetics: numerical stability and the cost of accurate computations, University of California at Berkeley, Berkeley, CA, 1992
• 42: Schmookler, M. S. 1980. Design of large ALUs using multiple PLA macros. IBM J. Res. Devel. 24, 1 (Jan.), 2--14.
• 43: Scott, A. P., Burkhart, K. P., Kumar, A., Blumberg, R. M., and Ransen, G. L. 1997. Four-way superscalar PA-RISC processors. Hewlett-Packard J. 48, 2 (Aug.), 8--15.
• 44: Sterbenz, P. H. 1974. Floating-Point Computation. Prentice-Hall, Englewood Cliffs, N.J.
• 45: Walter, W. V. 1993. ACRITH-XSC: A Fortran-like language for verified scientific computating. In Scientific Computing with Automatic Result Verification, E. Adams and U. Kulisch, Eds. Mathematics in Science and Engineering, vol. 189. Academic Press, Orlando, Fla., 45--70.
• 46: H. S. Warren, Jr., Instruction scheduling for the IBM RISC System/6000 processor, IBM Journal of Research and Development, v.34 n.1, p.85-92, Jan. 1990
• 47: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994
• 48: I. R. Wilson , A. M. Addyman, A Practical Introduction to Pascal, Springer-Verlag New York, Inc., Secaucus, NJ, 1990
• 49: Stephen Wolfram, The Mathematica Book, Wolfram Media, Incorporated, 1996

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.0 General

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic; Multiple precision arithmetic; Numerical algorithms; Error analysis
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis; Certification and testing; Reliability and robustness

General Terms:
Algorithms, Design, Languages, Standardization, Theory

Keywords:
Doubly compensated summation, floating-point arithmetic, fused multiply-add instruction, matrix arithmetic, provable accuracy, rounding error