Problem
I research electron behavior in organic solar cells and have found a way to recast this problem in terms of a large (n=~60 million) Absorbing Markov Chain that I represent as a sparse matrix. The matrix has high dimension but only 12 nonzero entries per row (at most). From the Markov Chain, I want to build its fundamental matrix:
$\mathbf{Q} = (\mathbf{I} - \mathbf{V})^{-1}$
and use that matrix to find the first passage time from a specific initial state i to any absorbing state. I know that $Q_{ij}$ is the mean number of times that the system starting in state i visits state j before being absorbed. So, if I could calculate a single row of $\mathbf{Q}$, i.e. calculate a single row of the inverse of a given sparse matrix, then I would be done.
My question is, is it possible to calculate a single row of the inverse of a matrix without having to calculate the rest of the inverse?
Complications
The matrix is extremely large (dimension > 60 million) and the only way I can store it in memory is because it is so sparse. The inverse is known to be dense so I cannot calculate it all explicitly. It's no problem to store a few vectors of length 60 million though. I have access to a nice computer with many GB of RAM.
I have tried just solving the system using restarted GMRES(m), however even with ILU(2) preconditioning and as long a restart as my computer has RAM for (m = 50), GMRES has uselessly slow convergence and basically stagnates. The matrix is nonsymmetric but diagonally dominant by construction. It has real entries.
Edit More Info
V comes from a random walk problem in 3 dimensions with 2 particles on a cubic lattice, so each row in V is a particular combination of a location for particle 1 and a location for particle 2 in 3-space. I restrict their position to a box of side s to limit the size of the matrix. The problem requires that s be large enough such that $s^6$ is on the order of 60 million, hence the matrix size. V has unity on the diagonal and strictly negative off diagonal elements with magnitude < 1. There are at most 12 off diagonal elements for row, corresponding to two directions of hopping along each of the 3 cardinal axes for each of the 2 particles.
I have not yet tried solving the system with GMRES for a right-hand-side that is just a basis vector but have tried for a rhs that is all 1s, which would also solve the problem and that does not converge. I will try to solve for a basis vector rhs tomorrow. Would you expect that to have better convergence properties?
Well, generally, for a matrix $A$ and a vector $b,$ it is much easier to compute $A^{-1}b$ than computing $A^{-1}$ (conjugate gradient is one way, there are others). So, to compute the first row, just compute $A^{-1} e_i$ for every basis vector $e_i,$ and then take the list of the first coordinates. This requires no extra memory, so while it will not be fast (you will have to run $60000000$ conjugate gradients, or whatever, but it will return.