SVD¶

Given an \(m \times n\) matrix \(A\), a Singular Value Decomposition is a triplet \((U,\Sigma,V)\) such that

\[A = U \Sigma V^H,\]

where \(U^H U = I\), \(V^H V = I\), and \(\Sigma\) is diagonal with non-negative entries. The columns of \(U\) are called left singular vectors, the columns of \(V\) are called right singular vectors, and the first \(\text{min}(m,n)\) diagonal entries of \(\Sigma\) are called singular values.

The above constraints allow for a number of different configurations:

A full SVD requires a square, \(m \times m\) \(U\), a square, \(n \times n\), \(V\), and an \(m \times n\) \(\Sigma\).
A thin SVD only involves an \(m \times \text{min}(m,n)\) \(U\), an \(\text{min}(m,n) \times n\) \(V\), and a \(\min(m,n) \times \min(m,n)\) \(\Sigma\).
A compact SVD only keeps the singular triplets corresponding to nonzero singular values, and so its size is bounded by that of the thin SVD.
A thresholded SVD only keeps the singular triplets with singular values which are sufficiently large. Thus, compact SVDs are a special case of thresholded SVDs.

Elemental currently provides support for thin and thresholded SVDs as well as allowing for only the singular values to be computed.

Implementation

Subroutines

Computing singular values¶

The following routines form the singular values of \(A\) in s. Note that A is overwritten in order to compute the singular values.

C++ API¶

void SVD(Matrix<F> &A, Matrix<Base<F>> &s)¶

void SVD(AbstractDistMatrix<F> &A, AbstractDistMatrix<Base<F>> &s, const SVDCtrl<Base<F>> &ctrl = SVDCtrl<Base<F>>())¶

C API¶

ElSingularValues_s(ElMatrix_s A, ElMatrix_s s)¶

ElSingularValues_d(ElMatrix_d A, ElMatrix_d s)¶

ElSingularValues_c(ElMatrix_c A, ElMatrix_s s)¶

ElSingularValues_z(ElMatrix_z A, ElMatrix_d s)¶

ElSingularValuesDist_s(ElDistMatrix_s A, ElDistMatrix_s s)¶

ElSingularValuesDist_d(ElDistMatrix_d A, ElDistMatrix_d s)¶

ElSingularValuesDist_c(ElDistMatrix_c A, ElDistMatrix_s s)¶

ElSingularValuesDist_z(ElDistMatrix_z A, ElDistMatrix_d s)¶

TODO: Expert interfaces

Computing Singular Value Decompositions¶

The following routines overwrite A with \(U\), s with the diagonal entries of \(\Sigma\), and V with \(V\).

C++ API¶

void SVD(Matrix<F> &A, Matrix<Base<F>> &s, Matrix<F> &V, const SVDCtrl<Base<F>> &ctrl = SVDCtrl<Base<F>>())¶

void SVD(AbstractDistMatrix<F> &A, AbstractDistMatrix<Base<F>> &s, AbstractDistMatrix<F> &V, const SVDCtrl<Base<F>> &ctrl = SVDCtrl<Base<F>>())¶

C API¶

ElError ElSVD_s(ElMatrix_s A, ElMatrix_s s, ElMatrix_s V)¶

ElError ElSVD_d(ElMatrix_d A, ElMatrix_d s, ElMatrix_d V)¶

ElError ElSVD_c(ElMatrix_c A, ElMatrix_s s, ElMatrix_c V)¶

ElError ElSVD_z(ElMatrix_z A, ElMatrix_d s, ElMatrix_z V)¶

ElError ElSVDDist_s(ElDistMatrix_s A, ElDistMatrix_s s, ElDistMatrix_s V)¶

ElError ElSVDDist_d(ElDistMatrix_d A, ElDistMatrix_d s, ElDistMatrix_d V)¶

ElError ElSVDDist_c(ElDistMatrix_c A, ElDistMatrix_s s, ElDistMatrix_c V)¶

ElError ElSVDDist_z(ElDistMatrix_z A, ElDistMatrix_d s, ElDistMatrix_z V)¶

TODO: Expert interfaces

Control structures¶

C++ API¶

template<> type SVDCtrl<Real>¶

bool seqQR¶: Whether or not sequential implementations should use the QR algorithm instead of a Divide and Conquer when computing singular vectors. When only singular values are requested, a bidiagonal DQDS algorithms is always run.

double valChanRatio¶: The minimum height/width ratio before preprocessing with a QR decomposition when only computing singular values.

double fullChanRatio¶: The minimum height/width ratio before preprocessing with a QR decomposition when computing a full SVD.

bool thresholded¶: If the sufficiently small singular triplets should be thrown away. When thresholded, a cross-product algorithm is used. This is often advantageous since tridiagonal eigensolvers tend to have faster parallel implementations than bidiagonal SVD’s.

bool relative¶: If the tolerance should be relative to the largest singular value.

Real tol¶: The numerical tolerance for the thresholding. If this value is kept at zero, then a value is automatically chosen based upon the matrix.

SVDCtrl()¶: Sets seqQR=false, valChanRatio=1.2, fullChanRatio=1.5, thresholded=false, relative=true, and tol=0.

template<> type SVDCtrl<Base<F>>¶: A particular case where the datatype is the base of the potentially complex type F.

C API¶

ElSVDCtrl_s¶

bool seqQR¶

double valChanRatio¶

double fullChanRatio¶

bool thresholded¶

bool relative¶

float tol¶

ElSVDCtrl_d¶

bool seqQR¶

double valChanRatio¶

double fullChanRatio¶

bool thresholded¶

bool relative¶

double tol¶

ElError ElSVDCtrlDefault_s(ElSVDCtrl_s* ctrl)¶

ElError ElSVDCtrlDefault_d(ElSVDCtrl_d* ctrl)¶: Initialize the default values for the control structure (seqQR=false, valChanRatio=1.2, fullChanRatio=1.5, thresholded=false, relative=true, and tol=0)