I am trying to attain the Moore-Penrose pseudoinverse of a very large, very sparse, rank-degenerate, singular, and square matrix. ($75000 \times 75000$, near rank). The matrix is a graph Laplacian and I need to find the resistance distance between a large number of nodes (LU determinates are too slow). I realize the inverse will be very dense, but I would like to persist it so I can query out distance metrics ad-hoc . I have been trying some brute approaches by converting it to a dense matrix (~25GB) on a large memory machine (124GB).
scipy.linalg.pinv) and some SVD approaches (
numpy.linalg.pinv) quickly exhaust the memory. The only approach that has worked is a slow but memory efficient SVD (
I am exploring what other techniques are out there that can balance memory efficiency and speed, although I have yet to try
scipy.sparse.svds for a thorough comparison. I don't think any iterative approaches will work well because I can't provide a decent starting point. I think this leaves QR as a prime candidate. I have been exploring some of the methods listed in this paper. I have the following questions:
- I want to sample selected entries of the MPI to calculate the distance between a large number of graph nodes in a ad-hoc fashion. Is there a better way to sample select elements of the MPI than persisting the whole matrix?
- Are there any algorithms particularly well suited to my matrix type?
- Is QR factorization my best bet? Is there some other approaches I should be considering?
- If QR, what memory efficient QR implementations exist? Or will I need to hand roll one from a paper?