Cache efficient bidiagonalization using BLAS 2.5 operators

ABSTRACT

On cache based computer architectures using current standard algorithms, Householder bidiagonalization requires a significant portion of the execution time for computing matrix singular values and vectors. In this paper we reorganize the sequence of operations for Householder bidiagonalization of a general m × n matrix, so that two (_GEMV) vector-matrix multiplications can be done with one pass of the unreduced trailing part of the matrix through cache. Two new BLAS operations approximately cut in half the transfer of data from main memory to cache, reducing execution times by up to 25 per cent. We give detailed algorithm descriptions and compare timings with the current LAPACK bidiagonalization algorithm.

REFERENCES

• 1: 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
• 2: Barlow, J. L., Bosner, N., and Drmač, Z. 2000. A new stable bidiagonal reduction algorithm. Lin. Alg. Appl. 397, 35--84.
• 3: Berry, M. 1992. Large scale singular value computations. Internat. J. Supercomput. Appl. 6, 13--49.
• 4: Michael Berry , Theresa Do , Gavin O''Brien , Vijay K %A , Sowmini Varadhan, SVDPACKC (Version 1.0) User''s Guide, University of Tennessee, Knoxville, TN, 1993
• 5: Michael W. Berry , Susan T. Dumais , Gavin W. O'Brien, Using linear algebra for intelligent information retrieval, SIAM Review, v.37 n.4, p.573-595, Dec. 1995 [doi>10.1137/1037127]
• 6: 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]
• 7: Blackford, S. and Dongarra, J. 1999. Installation guide for LAPACK, LAPACK Working Note 41.
• 8: Blackford, L. S., Corliss, G., Demmel, J., Dongarra, J., Duff, I., Hammarling, S., Henry, G., Heroux, M., Hu, C., Kahan, W., Kaufmann, L., Kearfott, B., Frogh, F., Li, X., Maany, Z., Petitet, A., Pozo, R., Remington, K., Walster, W., Whaley, C., Wolff, V., Gudenberg, J., and Lumsdaine, A. 2002. Basic linear algebra subprograms technical (BLAST) forum standard, Int. J. High Perform. Comput. 12, 1--2 (www.netlib.org/blas/blast-forum).
• 9: An updated set of basic linear algebra subprograms (BLAS), ACM Transactions on Mathematical Software (TOMS), v.28 n.2, p.135-151, June 2002 [doi>10.1145/567806.567807]
• 10: Bosner, N. and Barlow, J. L. 2005. Block and parallel versions of one-sided bidiagonalization. preprint http://www.cse.psu.edu/barlow/block_bidiag.pdf.
• 11: Choi, J., Dongarra, J., and Walker, D. 1995. The design of a parallel dense linear algebra software library: reduction to Hessenberg, tridiagonal, and bidiagonal form. (LAPACK Working Note # 92) Num. Alg., 10, 379--399.
• 12: Inderjit Singh Dhillon, A new O (N(2)) algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem, University of California at Berkeley, Berkeley, CA, 1998
• 13: Dongarra, J., Hammarling, S., and Sorensen, D. 1989. Block reduction of matrices to condensed forms for eigenvalue computations. J. Comput. Appl. Math. 27, 215--227.
• 14: Jack J. Dongarra , Lain S. Duff , Danny C. Sorensen , Henk A. Vander Vorst, Numerical Linear Algebra for High Performance Computers, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998
• 15: Douglas, C. C., Haase, G., Hu, J., Kowarschik, M., Rüde, U., and Weiss, C. 2000. Portable memory heirarchy techniques for PDE solvers: Part I. SIAM News, 33, 5.
• 16: Fernando, V., Parlett, B., and Dhillon, I. 1995. A way to find the most redundant equation in a tridiagonal system. Mathematics Department, University of California, Berkeley.
• 17: Performance optimization of numerically intensive codes, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 18: Golub, G. and Kahan, W. 1965. Calculating the singular Values and pseudo-inverse of a matrix, SIAM J. Num. Anal., 2, 205--224.
• 19: Golub, G. and Reinsch, C. 1970. Singular value decomposition and least squares solution. Numer. Math. 14, 403--420.
• 20: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 21: Grösser, B. and Lang, B. 1988. Efficient parallel reduction to bidiagonal form, Preprint BUGHW-SC 98/2. http://www.math.uni-wuppertal/org/SciComp/Preprint/SC9802ips.gz.
• 22: Howell, G. W. 2001. Sparse Householder bidiagonalization. CERFACS Sparse Days. http://ncsu. edu/itd/hpc/Documents/Publications/gary_howell/cerfacs01.ps
• 23: Bruno Lang, Parallel reduction of banded matrices to bidiagonal form, Parallel Computing, v.22 n.1, p.1-18, Jan. 1996 [doi>10.1016/0167-8191(95)00064-X]
• 24: Owens, B. 2003. A Matlab script for 2-blocking to speed Ralha-Barlow one-sided bidiagonalization. Summer intern project at ERDC, MSRC, Vicksburg, MS. http://ncsu.edu/itd/hpc/Documents/Publications/gary_howell/barlow3.m.
• 25: Christopher C. Paige , Michael A. Saunders, LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares, ACM Transactions on Mathematical Software (TOMS), v.8 n.1, p.43-71, March 1982 [doi>10.1145/355984.355989]
• 26: Parlett, B. and Dhillon, I. 1997. Fernando's solution to Wilkinson's problem: An application of double factorization. Lin. Alg. Appl. 267, 247--279.
• 27: Ralha, R. M. S. 2003. One-sided reduction to bidiagonal form. Lin. Alg. Appl. 358, 219--238.
• 28: 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]
• 29: Kendall Swenson Stanley , James Demmel, Execution time of symmetric eigensolvers, University of California, Berkeley, 1997
• 30: R. Clint Whaley , Jack J. Dongarra, Automatically tuned linear algebra software, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-27, November 07-13, 1998, San Jose, CA

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Singular value decomposition

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

General Terms:
Algorithms, Performance

Keywords:
BLAS 2.5, Householder reflections, SVD, bidiagonalization, cache-efficient, matrix factorization, singular values