Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix

Summary. In this paper we propose four algorithms to compute truncated pivoted QR approximations to a sparse matrix. Three are based on the Gram–Schmidt algorithm and the other on Householder triangularization. All four algorithms leave the original matrix unchanged, and the only additional storage requirements are arrays to contain the factorization itself. Thus, the algorithms are particularly suited to determining low-rank approximations to a sparse matrix. Received February 23, 1998 / Revised version received April 16, 1998