Using Mixed Precision for Sparse Matrix Computations to Enhance the Performance while Achieving 64-bit Accuracy

ABSTRACT

By using a combination of 32-bit and 64-bit floating point arithmetic, the performance of many sparse linear algebra algorithms can be significantly enhanced while maintaining the 64-bit accuracy of the resulting solution. These ideas can be applied to sparse multifrontal and supernodal direct techniques and sparse iterative techniques such as Krylov subspace methods. The approach presented here can apply not only to conventional processors but also to exotic technologies such as Field Programmable Gate Arrays (FPGA), Graphical Processing Units (GPU), and the Cell BE processor.

REFERENCES

• 1: Amestoy, P. R., Duff, I. S., and L'Excellent, J.-Y. 2000. Multifrontal parallel distributed symmetric and unsymmetric solvers. Comput. Meth. Appl. Mech. Eng. 184, 501--520.
• 2: Patrick R. Amestoy , Iain S. Duff , Jean-Yves L'Excellent , Jacko Koster, A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling, SIAM Journal on Matrix Analysis and Applications, v.23 n.1, p.15-41, 2001 [doi>10.1137/S0895479899358194]
• 3: Patrick R. Amestoy , Abdou Guermouche , Jean-Yves L'Excellent , Stéphane Pralet, Hybrid scheduling for the parallel solution of linear systems, Parallel Computing, v.32 n.2, p.136-156, February 2006 [doi>10.1016/j.parco.2005.07.004]
• 4: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 5: Ashcraft, C., Grimes, R., Lewis, J., Peyton, B. W., and Simon, H. 1987. Progress in sparse matrix methods in large sparse linear systems on vector supercomputers. Intern. J. of Supercomput. Appl. 1, 10--30.
• 6: O. Axelsson , P. S. Vassilevski, A black box generalized conjugate gradient solver with inner iterations and variable-step preconditioning, SIAM Journal on Matrix Analysis and Applications, v.12 n.4, p.625-644, Oct. 1991 [doi>10.1137/0612048]
• 7: Balay, S., Buschelman, K., Gropp, W. D., Kaushik, D., Knepley, M. G., McInnes, L. C., Smith, B. F., and Zhang, H. 2001. PETSc Web page. http://www.mcs.anl.gov/petsc.
• 8: Barrett, R., Berry, M., Chan, T. F., Demmel, J., Donato, J. M., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., and der Vorst, H. V. 1994. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. Society for Industrial and Applied Mathematics, Philadelphia, PA. http://www.netlib.org/templates/Templates.html.
• 9: Björck, A. 1990. Iterative refinement and reliable computing. In Reliable Numerical Computation, M. G. Cox and S. Hammarling, Eds. Oxford University Press, Oxford, UK, 249--266.
• 10: Buttari, A., Dongarra, J., Kurzak, J., Luszczek, P., and Tomov, S. 2006. Computations to enhance the performance while achieving the 64-bit accuracy. Tech. rep. UT-CS-06-584, University of Tennessee Knoxville. LAPACK Working Note 180.
• 11: Timothy A. Davis , Iain S. Duff, A combined unifrontal/multifrontal method for unsymmetric sparse matrices, ACM Transactions on Mathematical Software (TOMS), v.25 n.1, p.1-20, March 1999 [doi>10.1145/305658.287640]
• 12: Timothy A. Davis, A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, ACM Transactions on Mathematical Software (TOMS), v.30 n.2, p.165-195, June 2004 [doi>10.1145/992200.992205]
• 13: Demmel, J., Dongarra, J., Eijkhout, V., Fuentes, E., Petitet, A., Vuduc, R., Whaley, R. C., and Yelick, K. 2005. Self-adapting linear algebra algorithms and software. Proc. IEEE 93, 2. http://www.spiral.net/ieee-special-issue/overview.html.
• 14: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 15: James W. Demmel , Stanley C. Eisenstat , John R. Gilbert , Xiaoye S. Li , Joseph W. H. Liu, A Supernodal Approach to Sparse Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.720-755, July 1999 [doi>10.1137/S0895479895291765]
• 16: James W. Demmel , John R. Gilbert , Xiaoye S. Li, An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.915-952, Oct. 1999 [doi>10.1137/S0895479897317685]
• 17: Dongarra, J. J. and Eijkhout, V. 2002. Self-adapting numerical software for next generation applications. Tech. rep. ICL-UT-02-07, Innovative Computing Lab, University of Tennessee, Lapack Working Note 157. http://icl.cs.utk.edu/iclprojects/pages/sans.html.
• 18: I. S. Duff , J. K. Reid, The Multifrontal Solution of Indefinite Sparse Symmetric Linear, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.302-325, Sept. 1983 [doi>10.1145/356044.356047]
• 19: Timothy A. Davis , Iain S. Duff, An Unsymmetric-Pattern Multifrontal Method for Sparse LU Factorization, SIAM Journal on Matrix Analysis and Applications, v.18 n.1, p.140-158, Jan. 1997 [doi>10.1137/S0895479894246905]
• 20: Embree, M. 2003. The tortoise and the hare restart gmres. SIAM Rev. 45, 259--266.
• 21: Forsythe, G. E. and Moler, C. B. 1967. Computer Solution of Linear Algebraic Systems. Prentice-Hall, Englewood Cliffs, NJ.
• 22: Göddeke, D., Strzodka, R., and Turek, S. 2005. Accelerating double precision FEM simulations with GPUs. In Simulationstechnique 18th Symposium in Erlangen. F. Hülsemann, M. Kowarschik, and U. Rüde, Eds. Vol. Frontiers in Simulation. SCS Publishing House e.V., 139--144.
• 23: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 24: Gene H. Golub , Qiang Ye, Inexact Preconditioned Conjugate Gradient Method with Inner-Outer Iteration, SIAM Journal on Scientific Computing, v.21 n.4, p.1305-1320, Dec. 1999—March 2000 [doi>10.1137/S1064827597323415]
• 25: Gropp, W. D., Kaushik, D. K., Keyes, D. E., and Smith, B. F. 2000. Latency, bandwidth, and concurrent issue limitations in high-performance CFD. Tech. rep. ANL/MCS-P850-1000, Argonne National Laboratory.
• 26: William D. Gropp , Dinesh K. Kaushik , David E. Keyes , Barry F. Smith, High-performacne parallel implicit CFD, Parallel Computing, v.27 n.4, p.337-362, March 1, 2001 [doi>10.1016/S0167-8191(00)00075-2]
• 27: Gurtin, M. E. 1981. An Introduction to Continuum Mechanics. Academic Press, New York, NY.
• 28: Hackbusch, W. 1985. Multigrid Methods and Applications. Springer Series in Computational Mathematics, Vol. 4, Springer-Verlag, Berlin, Germany.
• 29: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
• 30: Julie Langou , Julien Langou , Piotr Luszczek , Jakub Kurzak , Alfredo Buttari , Jack Dongarra, Exploiting the performance of 32 bit floating point arithmetic in obtaining 64 bit accuracy (revisiting iterative refinement for linear systems), Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188573]
• 31: Li, X. S. 1996. SuperLU software, Ph.D. thesis, Computer Science Department, University of California at Berkeley. http://www.nersc.gov/ xiaoye/SuperLU/.
• 32: Xiaoye S. Li , James W. Demmel, SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Transactions on Mathematical Software (TOMS), v.29 n.2, p.110-140, June 2003 [doi>10.1145/779359.779361]
• 33: Cleve B. Moler, Iterative Refinement in Floating Point, Journal of the ACM (JACM), v.14 n.2, p.316-321, April 1967 [doi>10.1145/321386.321394]
• 34: Yvan Notay, Flexible Conjugate Gradients, SIAM Journal on Scientific Computing, v.22 n.4, p.1444-1460, 2000 [doi>10.1137/S1064827599362314]
• 35: Quarteroni, A. and Valli, A. 1999. Domain Decomposition Methods for Partial Differential Equations. Oxford University Press, Cambridge, UK.
• 36: Saad, Y. 1991. A flexible inner-outer preconditioned GMRES algorithm. Tech. rep. 91-279, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN.
• 37: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 38: Youcef Saad , Martin H Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.856-869, July 1986 [doi>10.1137/0907058]
• 39: Saad, Y. and Wu, K. 1996. DQGMRES: a direct quasi-minimal residual algorithm based on incomplete orthogonalization. Num. Linear Algeb. Appl. 3, 4, 329--343.
• 40: Simoncini, V. and Szyld, D. 2002a. Theory of inexact Krylov subspace methods and applications to scientific computing. Tech. rep. 02-4-12, Department of Mathematics, Temple University.
• 41: Valeria Simoncini , Daniel B. Szyld, Flexible Inner-Outer Krylov Subspace Methods, SIAM Journal on Numerical Analysis, v.40 n.6, p.2219-2239, 2002 [doi>10.1137/S0036142902401074]
• 42: Valeria Simoncini , Daniel B. Szyld, The effect of non-optimal bases on the convergence of Krylov subspace methods, Numerische Mathematik, v.100 n.4, p.711-733, June 2005 [doi>10.1007/s00211-005-0603-8]
• 43: G. W. Stewart, Matrix algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 44: Strzodka, R. and Göddeke, D. 2006a. Mixed precision methods for convergent iterative schemes. EDGE'06, 23.-24. Chapel Hill, NC.
• 45: Robert Strzodka , Dominik Goddeke, Pipelined Mixed Precision Algorithms on FPGAs for Fast and Accurate PDE Solvers from Low Precision Components, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.259-270, April 24-26, 2006 [doi>10.1109/FCCM.2006.57]
• 46: Kathryn Turner , Homer F. Walker, Efficient high accuracy solutions with GMRES(m), SIAM Journal on Scientific and Statistical Computing, v.13 n.3, p.815-825, May 1992 [doi>10.1137/0913048]
• 47: van den Eshof, J., Sleijpen, G. L. G., and van Gijzen, M. B. 2003. Relaxation strategies for nested Krylov methods. Technical report TR/PA/03/27, CERFACS, Toulouse, France.
• 48: van der Vorst, H. A. and Vuik, C. 1994. GMRESR: a family of nested GMRES methods. Num. Linear Algeb. Appl. 1, 4, 369--386.
• 49: C. Vuik, New insights in GMRES-like methods with variable preconditioners, Journal of Computational and Applied Mathematics, v.61 n.2, p.189-204, July 31, 1995 [doi>10.1016/0377-0427(94)00067-B]
• 50: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic

Additional Classification:
  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.3 Numerical Linear Algebra
          Subjects: Error analysis
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Performance

Keywords:
Linear systems, floating point, iterative refinement, precision