0
$\begingroup$

If I have some dense matrix that can be decomposed into a product of sparse matrices with known(but different) sparsity patterns. Can I somehow use this information to more efficiently compute its Eigenvalues and Eigenvectors and its Moore-Penrose Pseudoinverse? By efficiently I mostly mean with lower memory cost since I am memory bottlenecked. Also is there any way to leverage this information when using iterative algorithms, since I would like to avoid instantiating the matrix if possible?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

You can use an iterative routine such as Arnoldi or Lanczos for the eigendecomposition, by implementing the matrix-vector product with the dense matrix as two products with the sparse matrices. That is let $M= BA$ then you can implement the matrix-vector product as $Ax=y$ and $z=By \equiv BAx = Mx$.

You don't need the eigendecomposition if you just need to compute the application of the pseudoniverse, e.g. if you want to compute $x=M^{+}b$ you can just use the conjugate gradient solver for the normal equations (CGNR) with an initial guess of zero and it will give you the pseudoinverse solution. It goes without saying that you should implement $M$ as a product with the two sparse matrices here also. If you know that $b$ is in the range of $M$ and that $M$ is Hermitian positive semi-definite then you can directly use the conjugate gradient solver with initial guess zero instead of CGNR and it will also give you the pseudoinvetse solution if I remember correctly.

$\endgroup$
4
  • $\begingroup$ Thank you for your answer! I think my problem with using Lanczos is that I don't have the memory to store more than a handful of Lanczos vectors so I can do a very deep Lanczos. I need v -> f(A)v. I like your suggestion of a Conjugate Gradient(since I care mostly about the pseudoinverse vector product). Does this explicitly leverage the sparsity? And how important is preconditioning? In my experience, it was very hard to find good pre-conditioners to get my cg to work in the past on similar problems. $\endgroup$
    – HRI
    Commented Feb 8 at 14:39
  • $\begingroup$ @HRI If you just need the pseudoinverse application try CG or CGNR. There are various preconditioners for CG but ultimately what is best depends on your problem. So the best way is to just test. For general matrix functions evaluation with limited memory see: arxiv.org/abs/2002.01682 $\endgroup$
    – lightxbulb
    Commented Feb 8 at 14:52
  • $\begingroup$ But can I get the CG or CGNR to explicitly leverage the sparsity? $\endgroup$
    – HRI
    Commented Feb 8 at 15:16
  • $\begingroup$ @HRI As I explained you can implement the matrix vector product with $M=BA$ as $y = Ax$ and then $z=By$ which means $z\equiv BAx = Mx$. So yes you can exploit the sparsity. Conjugate gradient requires only a routine implementing the matrix-vector product. CGNR additionally requires a routine for the matrix-vector product with the transpose, but that's just $M^T=A^TB^T$ in your case, so $v=B^Tu$ and $w=A^Tv$, which means $w\equiv A^TB^Tu = M^Tu$. $\endgroup$
    – lightxbulb
    Commented Feb 8 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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