1
$\begingroup$

I have a sparse matrix $W$ which is almost-squared ($N+1 \times N$) and I would like to know the eigenvalues of $A = W^T W$. $A$ is Hermitian so the eigenvalues are real-positive valued.

The usual approach would be to do svd(W), but I found no GPU SVD sparse implementation. I'm working in python but I'm good with any language hoping I can found a C/ C++ code to wrap and call.

I've looked into cuSPARSE and cuSOLVE and I only found:

  • eigenvalue solver
  • LU
  • QR
  • Cholesky

$W$ is an $N+1 \times N$ complex sparse matrix with sparsity = $1 - 2^{-M}$ for $M$ in $[9,10,11]$

I've tried using CPU libraries (numpy and scipy), but they're very slow since the fraction of nonzero SVD is more than 20% for $M = 9$. I've looked into the randomized solver implemented by scikit-learn but I cannot use it since this method is not proven to work on complex matrices.

Any tip is more than welcome.

$\endgroup$
  • $\begingroup$ Try performing the GPU-accelerated QR decomposition on $W$, where $W = Q R$, and $W^* W = R^* R$, where $R$ is a triangular matrix. The singular values of $R$ are the same as $W$. Computing the SVD of a triangular matrix using your CPU code might be easier. I wouldn't be surprised if there was a specialized SVD algorithm for a triangular matrix. $\endgroup$ – Charlie S Jul 31 at 16:32
3
$\begingroup$

I'm no expert on software and certainly not on GPU software, but I can hopefully give some advice of a mathematical nature that might be helpful to you.

Given a matrix $W$, one can embed $W$ in the larger square and Hermitian matrix

$$ B = \begin{bmatrix} 0 & W \\ W^* & 0 \end{bmatrix}. $$

$B$ is a square matrix with twice the number of nonzeros as $W$. The nonzero eigenvalues of $B$ are $\pm$ the nonzero singular values of $W$. If $\sigma$ is a singular value of $W$ satisfying $Wv = \sigma u$ and $W^*u = \sigma v$, then

$$ B \begin{bmatrix} u \\ v \end{bmatrix} = \begin{bmatrix} 0 & W \\ W^* & 0 \end{bmatrix}\begin{bmatrix} u \\ v \end{bmatrix} = \begin{bmatrix} Wv \\ W^* u \end{bmatrix} = \sigma \begin{bmatrix} u \\ v \end{bmatrix}. $$

$\begin{bmatrix} u \\ v \end{bmatrix}$ is an eigenvector of $B$ with eigenvalue $\sigma$. Likewise, $\begin{bmatrix} u \\ -v \end{bmatrix}$ is an eigenvector of $B$ with eigenvector $-\sigma$. This should allow you to use any Hermitian eigenvalue code to get a (full or truncated) SVD. This embedding might not be as fast as a dedicated SVD code, but it will allow you to take advantage of existing highly optimized eigenvalue code to compute an SVD.

Also, regarding randomized methods, every method I'm aware of works for both real and complex matrices. Software support for complex values might be a different story.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.