HSL_MC81: Randomized methods for low-rank matrix approximation

HSL_MC81 uses randomized algorithms to compute low-rank approximations of a given matrix. If \(A\) is \({n \times n}\) and symmetric positive definite it computes a truncated eigenvalue decomposition (EVD) \[A \approx X D X^T,\] where \(k < n\) is the target rank, \(X\) is an \({n \times k}\) orthonormal matrix and \(D\) is a \({k \times k}\) diagonal matrix whose entries approximate the eigenvalues of \(A\) with largest absolute value in descending order.

If \(A\) is a general \(m \times n\) matrix, it computes a truncated singular value decomposition (SVD) \[A \approx U \Sigma V^T,\] where \(k < \min(m,n)\) is the target rank, \(U\) is an \({m \times k}\) orthonormal matrix, \(V\) is an \({n \times k}\) orthonormal matrix and \(\Sigma\) is a \({k \times k}\) diagonal matrix whose entries approximate the largest singular values of \(A\) in descending order.

The package offers simple interfaces in which the user supplies the sparse matrix \(A\) in compressed sparse column (CSC) format and, for greater flexibility, matrix-free reverse communication interfaces that return control to the user when products with \(A\) are required.

Fortran, MATLAB. Real (single, double). January 2022. , KB08, BLAS subroutines _gemm, _gemv, _trsm, and the LAPACK subroutines _gesvd, _gemqrt, _geqrt, _potrf, _syev. J.A. Scott, Rutherford Appleton Laboratory. Fortran 95.