Question

Hi, there

I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special matrix ${(E-a \cdot X)}^{-1}$,

where $E$ is an $n \times n$ identity matrix, $ a \in (0,1)$ is a scalar, and $X$ is a sparse stochastic matrix (the sum of each row is 1, and all its entries are between 0 and 1),

do you have some ideas to compute ${(E-a \cdot X)}^{-1}$ as fast as you can? (to reduce its $O(n^3)$ complexity is preferable, or approximate solution is also acceptable) ? Thanks in advance!

Answer 1

As others have already indicated, there's a good chance that you don't actually need $(E-aX)^{-1}$, but rather $(E-aX)^{-1}v$ for some vector $v$. In that case, you might be better off using an iterative method to solve $(E-aX)y=v$.

Another option to consider is the power series:

$ (E-aX)^{-1}=E+aX+a^2X^2+a^3X^3+... $

which is convergent for $|a|<1$, and can converge quite quickly if $a$ is small. If $a$ is small enough, then perhaps using a few terms of this power series will be sufficient. Computing powers of $X$ also takes $O(n^3)$ time in the worst case, but if $X$ is extremely sparse it might be much faster in practice than computing the inverse of $(E-aX)$.

In computing a partial sum of this series, you can use Horner's rule and get successive partial sums:

$ M^{1}=E+aX $

$ M^{2}=E+aX(M^{1})=E+aX+a^2X^2 $

$ M^{3}=E+aX(M^{2})=E+aX+a^2X^2+a^3X^3 $

$ \ldots $

Note that $(E-aX)^{-1}$ will typically be fully dense, but the sum of the first few terms of this series could be relatively sparse.

Answer 2

${(E-a \cdot X)}^{-1}=E+a \cdot X+\cdots+(a \cdot X)^k + O(a^{k+1}).$ General matrix multiplication can be $O(n^{\log_2 7})$ (I'm not sure how bad the constant is though) and since you say that $X$ is sparse there may be faster methods.