heat.linalg.randomized

Randomized linear algebra algorithms, including randomized SVD (rSVD) and randomized EIGH (reigh).

Module Contents

rsvd(A: heat.core.dndarray.DNDarray, svd_rank: int, n_oversamples: int = 10, power_iter: int = 0, qr_procs_to_merge: int = 2) → Tuple[heat.core.dndarray.DNDarray, heat.core.dndarray.DNDarray, heat.core.dndarray.DNDarray] | Tuple[heat.core.dndarray.DNDarray, heat.core.dndarray.DNDarray][source]

Randomized SVD (rSVD) with prescribed truncation rank svd_rank. If \(A = U \operatorname{diag}(S) V^T\) is the true SVD of A, this routine computes an approximation for U[:,:svd_rank] (and S[:svd_rank], V.T[:,:svd_rank]).

The accuracy of this approximation depends on the structure of A (“low-rank” is best) and appropriate choice of parameters.

Parameters:

  • A (DNDarray) – 2D-array (float32/64) of which the rSVD has to be computed.

  • svd_rank (int) – truncation rank of the SVD. (This parameter corresponds to n_components in scikit-learn’s TruncatedSVD.)

  • n_oversamples (int, optional) – number of oversamples. The default is 10.

  • power_iter (int, optional) – number of power iterations. The default is 0. Choosing power_iter > 0 can improve the accuracy of the SVD approximation in the case of slowly decaying singular values, but increases the computational cost.

  • qr_procs_to_merge (int, optional) – number of processes to merge at each step of QR decomposition in the power iteration (if power_iter > 0). The default is 2. See the corresponding remarks for heat.linalg.qr() for more details.

Notes

Memory requirements: the SVD computation of a matrix of size (svd_rank + n_oversamples) x (svd_rank + n_oversamples) must fit into the memory of a single process. The implementation follows Algorithm 4.4 (randomized range finder) and Algorithm 5.1 (direct SVD) in [1].

Please note that “rank” in the context of SVD always refers to the number of singular values/vectors to compute (i.e., “rank” refers to the mathematical rank of a matrix). This is completely different from the notion of “(MPI-)rank”, i.e., the ID given to a process, in a parallel MPI-application.

References

[1] Halko, N., Martinsson, P. G., & Tropp, J. A. (2011). Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2), 217-288.

reigh(A: heat.core.dndarray.DNDarray, n_eigenvalues: int, n_oversamples: int = 10, power_iter: int = 0, qr_procs_to_merge: int = 2) → Tuple[heat.core.dndarray.DNDarray, heat.core.dndarray.DNDarray][source]

Randomized eigenvalue decomposition (rEIGH). Only the top n_eigenvalues eigenvalues (ordered by magnitude) and corresponding eigenvectors are computed.

Parameters:

  • A (DNDarray) – 2D-array (float32/64) of which the rEIGH has to be computed. Must be symmetric.

  • n_eigenvalues (int) – number of eigenvalues to compute. (This parameter corresponds to n_components in scikit-learn’s PCA.)

  • n_oversamples (int, optional) – number of oversamples. The default is 10.

  • power_iter (int, optional) – number of power iterations. The default is 0. Choosing power_iter > 0 can improve the accuracy of the eigenvalue approximation in the case of slowly decaying eigenvalues, but increases the computational cost.

  • qr_procs_to_merge (int, optional) – number of processes to merge at each step of QR decomposition in the power iteration (if power_iter > 0). The default is 2. See the corresponding remarks for heat.linalg.qr() for more details.

Notes

Memory requirements: the symmetric eigenvalue decomposition of a matrix of size (n_eigenvalues + n_oversamples) x (n_eigenvalues + n_oversamples) must fit into the memory of a single process. The implementation follows Algorithm 4.4 (randomized range finder) and Algorithm 5.3 (eigenvalue decomposition from an SVD) in [1].

References

[1] Halko, N., Martinsson, P. G., & Tropp, J. A. (2011). Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2), 217-288.