:mod:`heat.linalg.randomized`
==================================
.. py:module:: heat.core.linalg.randomized

.. autoapi-nested-parse::

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



Module Contents
---------------


.. function:: rsvd(A: heat.core.dndarray.DNDarray, svd_rank: int, n_oversamples: int = 10, power_iter: int = 0, qr_procs_to_merge: int = 2) -> Union[Tuple[heat.core.dndarray.DNDarray, heat.core.dndarray.DNDarray, heat.core.dndarray.DNDarray], Tuple[heat.core.dndarray.DNDarray, heat.core.dndarray.DNDarray]]

   Randomized SVD (rSVD) with prescribed truncation rank `svd_rank`.
   If :math:`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.

   :param A: 2D-array (float32/64) of which the rSVD has to be computed.
   :type A: DNDarray
   :param svd_rank: truncation rank of the SVD. (This parameter corresponds to `n_components` in scikit-learn's TruncatedSVD.)
   :type svd_rank: int
   :param n_oversamples: number of oversamples. The default is 10.
   :type n_oversamples: int, optional
   :param power_iter: 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.
   :type power_iter: int, optional
   :param qr_procs_to_merge: 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 :func:`heat.linalg.qr() <heat.core.linalg.qr.qr()>` for more details.
   :type qr_procs_to_merge: int, optional

   .. rubric:: 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.

   .. rubric:: 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.


.. function:: 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]

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

   :param A: 2D-array (float32/64) of which the rEIGH has to be computed. Must be symmetric.
   :type A: DNDarray
   :param n_eigenvalues: number of eigenvalues to compute. (This parameter corresponds to `n_components` in scikit-learn's PCA.)
   :type n_eigenvalues: int
   :param n_oversamples: number of oversamples. The default is 10.
   :type n_oversamples: int, optional
   :param power_iter: 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.
   :type power_iter: int, optional
   :param qr_procs_to_merge: 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 :func:`heat.linalg.qr() <heat.core.linalg.qr.qr()>` for more details.
   :type qr_procs_to_merge: int, optional

   .. rubric:: 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].

   .. rubric:: 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.