I'm trying find an optimization for an equation related to theorem 3.5.7 from "Finite Markov Chains" by Kemeny and Snell (1976). The theorem is:


Where $N_{dg}$ is a diagonal matrix with all 0 except for the diagonal portion of N and


And $Q$ is a $n \times n$ square sparse pairwise transition matrix that looks like: enter image description here

The matrix is symmetric structurally (shown by the colors), but not numerically. It is characterized by 3 tri-bands, with the distance between the bands related to $\sqrt{n}$. If there is a technical term for this matrix, I don't know what it is.

The modified version of the calculation I'm trying to solve simply involves pre-multiplying the theorem with a vector, like so:


I'm trying to apply this to extremely large matrices (n=1,000,000 is the low end of what we consider useful). I can solve the $v(N-I)$ part of the equation easily enough using the Ax=B approach. Inverting $N_{dg}$ is simple (simply invert the individual values, since the non-diagonal values are all 0). That only leaves finding $N_{dg}$ itself in a reasonably efficient manner (both in terms of time and memory requirements). I would also like to avoid estimation if possible.

Ideally, I wouldn't have to calculate $N$, which involves an inverse that results in a dense matrix, and instead solve the linear system. Unfortunately, the weird nature of $N_{dg}$ seems to preclude that option.

I can solve for individual rows and columns of $N$ by including a vector multiplication and solving the system. From this, I can extract individual elements of $N_{dg}$. However, to do so iteratively to calculate the entirety of $N_{dg}$ is impractically slow (months to years).

I did come across "The inverse of banded matrices" by Emrah Kılıç and Pantelimon Stanica (2013), and subsequently came across this Computer Science stackexchange post that also links to the same paper. Unfortunately, the answer provided assumes that the inverse will not be calculated directly, so my only option is to try and work through the paper myself. My hope is that because I don't need to calculate the entire inverse it will be practical. It looks promising, particularly the $i=j$ case in theorem 7, but it's also beyond my level of linear algebra, so it could take a while for me understand and just end up being a time-consuming dead-end.

Does anyone have any suggestions for a computationally reasonable approach for calculating $N_{dg}$? If the paper I found happens to be the best solution, just distilling it down would be helpful because I'm not a math major.



Your Answer

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