# Eigenvalue problem and pseudoinverse of a product of sparse matrices

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?

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.
• @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$. Commented Feb 8 at 16:27