UBk+1V Block Sparse Householder Decomposition ∗

This paper describes Householder reduction of a rectangular sparse matrix to small band upper triangular form. Using block Householder transformations gives good orthogonality, is computationally efficient, and has good potential for parallelization. The algorithm is similar to the standard dense Householder reduction used as part of the usual dense SVD computation. For the sparse algorithm, the original sparse matrix is accessed only for sparse matrix dense matrix (SMDM) multi-plications. For a triangular bandwidth of k + 1, the dense matrices are the k rows or columns of a block Householder transformation. Using an initial random block Householder transformation allows re-liable computation of a collection of largest singular values. Some other potential applications are in finding low rank matrix approximations and in solving least squares problems.