Stability of block algorithms with fast level-3 BLAS

ABSTRACT

Block algorithms are becoming increasingly popular in matrix computations. Since their basic unit of data is a submatrix rather than a scalar, they have a higher level of granularity than point algorithms, and this makes them well suited to high-performance computers. The numerical stability of the block algorithms in the new linear algebra program library LAPACK is investigated here. It is shown that these algorithms have backward error analyses in which the backward error bounds are commensurate with the error bounds for the underlying level-3 BLAS (BLAS3). One implication is that the block algorithms are as stable as the corresponding point algorithms when conventional BLAS3 are used. A second implication is that the use of BLAS3 based on fast matrix multiplication techniques affects the stability only insofar as it increases the constant terms in the normwise backward error bounds. For linear equation solvers employing LU factorization, it is shown that fixed precision iterative refinement helps to mitigate the effect of the larger error constants. Despite the positive results presented here, not all plausible block algorithms are stable; we illustrate this with the example of LU factorization with block triangular factors and describe how to check a block algorithm for stability without doing a full error analysis.

REFERENCES

• 1: ARIOLI, M., DEMMEL, J. W., AND DUFF, h S. Solving sparse linear systems with sparse backward error. SIAM J. Motrix Anal. Appl. lO (1989), 165-190.
• 2: Zhaojun Bai , James Demmel, On a block implementation of Hessenberg multishift QR iteration, International Journal of High Speed Computing, v.1 n.1, p.97-112, May 1989 [doi>10.1142/S0129053389000068]
• 3: David H. Bailey , King Lee , Horst D. Simon, Using Strassen's algorithm to accelerate the solution of linear systems, The Journal of Supercomputing, v.4 n.4, p.357-371, 1990 [doi>10.1007/BF00129836]
• 4: BISCHOF, C. H., AND DONGARRA, J.J. A project for developing a linear algebra library for high-performance computers. Preprint MCS-P105-0989, Mathematics and Computer Science Div., Argonne National Lab., 1989.
• 5: Christian Bischof , Charles van Loan, The WY representation for products of householder matrices, SIAM Journal on Scientific and Statistical Computing, v.8 n.1, p.2-13, January 2, 1987 [doi>10.1137/0908009]
• 6: BRENT, R.P. Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity. Numer. Math. 16 (1970), 145 156.
• 7: DAHLQUIST, G., AND BJORCK, A. Numerlcc~ Methods. Prentice-Hall, Englewood Cliffs, N.J., 1974.
• 8: DEMMEL, J.W. On floating point errors in Cholesky. LAPACK Working Note 14, Dept. of Computer Science, Univ. of Tennessee, Knoxville, 1989.
• 9: DEMMEL, J. ~~., DONGARRA, J J., DU CROZ, J. J., GREENBAUM, A., I-IAMMARLING, ~. J., AND SORENSEN, D.C. Prospectus for the development of a linear algebra library for high-performance computers. Tech. Mem. 97, Mathematics and Computer Science Div., Argonne National Lab., 1987.
• 10: DEMMEL, J W., DU CROZ, J. J., HAMMARLING, S. J., AND SORENSON, D.C. Guidelines for the design of symmetric eigenroutines, SVD, and iterative refinement and condition estimation for linear systems. LAPACK Working Note 4, Tech. Memor. Ill, Mathematics and Computer Science Dlv., Argonne National Lab., 1988.
• 11: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 12: J. J. Dongarra , Jermey Du Cruz , Sven Hammerling , I. S. Duff, Algorithm 679; a set of level 3 basic linear algebra subprograms: model implementation and test programs, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.18-28, March 1990 [doi>10.1145/77626.77627]
• 13: DONGARRA, J. J., HAMMARLING, S. J., AND SORENSEN, D. C. Block reduction of matrices to condensed forms for eigenvalue computations. J. Comput. Appl. Math. 27 (1989), 215 227.
• 14: DONGARRA, J. J., KAUFMAN, L., AND HAMMARLING, S.J. Squeezing the most out of eigenvalue solvers on high-performance computers. Linear Algebra Appl. 77 (1986), 113-136.
• 15: DuCRoz, J.J.,ANDHIGH~M,N.J. Stability of methods for matrix inversion. IMAJ. Numer. Anal. 12, (1992), 1-19.
• 16: GALLIVAN, K., JALBY, W., MEIER, U., AND SAMEH, A. H. Impact of hierarchical memory systems on linear algebra algorithm design. Int. J. Supercomput. Appl. 2 (1988), 12 48.
• 17: K. A. Gallivan , R. J. Plemmons , A. H. Sameh, Parallel algorithms for dense linear algebra computations, SIAM Review, v.32 n.1, p.54-135, March 1990 [doi>10.1137/1032002]
• 18: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 19: Nicholas J. Higham, Algorithm 694: a collection of test matrices in MATLAB, ACM Transactions on Mathematical Software (TOMS), v.17 n.3, p.289-305, Sept. 1991 [doi>10.1145/114697.116805]
• 20: Nicholas J. Higham, Bounding the error in Gaussian Elimination for Tridiagonal systems, SIAM Journal on Matrix Analysis and Applications, v.11 n.4, p.521-530, Oct. 1990 [doi>10.1137/0611036]
• 21: Nicholas J. Higham, Exploiting fast matrix multiplication within the level 3 BLAS, ACM Transactions on Mathematical Software (TOMS), v.16 n.4, p.352-368, Dec. 1990 [doi>10.1145/98267.98290]
• 22: HIGHAM, N. J. How accurate is Gaussian elimination? In Numerical Analysis 1989, In Proceedings of the 13th Dundee Conference, D. F. Griffiths and G. A. Watson, Eds., Pitman Research Notes in Mathematics 228, LongTnan, 1990, pp. 137-154.
• 23: H~GHAM, N.J. Is fast matrix multiplication of practical use? SIAM News. 23 (Nov. 1990), 12 +.
• 24: Nicholas J. Higham, Iterative refinement enhances the stability of QR factorization methods for solving linear equations, BIT, v.31 n.3, p.447-468, Summer 1991 [doi>10.1007/BF01933262]
• 25: HIGHAM, N. J. Stability of a method for multiplying complex matrices with three real matrix multiplications. Numerical Analysis Rep. No. 181, Univ. of Manchester, England, 1990; to appear in SIAM J. Matrix Anal App{.
• 26: M^YES, P., AND RADICATI, G. Banded Cholesky factorization using level 3 BLAS, LAPACK Working Note 12, Mathematics and Computer Science Div., Argonne National Lab. 1989.
• 27: OETTH, W., AND Pr~E~, W. Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Nvmer. Math. 6 (1964), 405-409.
• 28: Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 29: SC~REmER, R. S. Block algorithms for parallel machines. In Numerical Algorithms for Modern Parallel Computer Archztectures, M. H. Schultz, Ed., IMA Volumes In Mathematics and Its Applications 13, Springer-Verlag, Beriin~ 1988, pp. 197-207.
• 30: Robert Schreiber , Charles van Loan, A storage-efficient WY representation for products of householder transformations, SIAM Journal on Scientific and Statistical Computing, v.10 n.1, p.53-57, January 1989 [doi>10.1137/0910005]
• 31: SKEEL, R. D. Iterative refinement implies numerical stability for Gaussian elimination. Math. Comput. 35 (1980), 817 832.
• 32: ST~SSEN, V. Gaussian elimination is not optimal. Numer. Math. 13 (1969), 354 356.
• 33: WILKINSON~ J.H. Error analysis of eigenvalue techniques based on orthogonal transformations. J. Soc. Indust. Appl. Math. 10 (1962), 162-195.
• 34: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 35: WmK~NSON, J.H. Error analysis revisited. IMA Bull. 22 (1986), 192-200.
• 36: WINOGR~, S. A new algorithm for inner product. IEEE Trans. Comput. C-18 (1968), 693-694.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

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

General Terms:
Algorithms, Performance

Keywords:
LAPACK, LU factorization, QR factorization, backward error analysis, block algorithm, iterative refinement, level-3 BLAS