4
$\begingroup$

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!

$\endgroup$
7
  • 1
    $\begingroup$ What are you looking for? Good theoretical complexity or fast answer in practice? These are two different questions. $\endgroup$ Mar 21, 2011 at 6:21
  • $\begingroup$ I am just wondering whether there would be some effciient way to optimize the ${E-a \cdot X}^{-1}$ computation? $\endgroup$
    – Nancy
    Mar 21, 2011 at 6:47
  • 5
    $\begingroup$ There's also the question of whether you really want the inverse matrix. (For example, if you are trying to solve a system of linear equations, then computing the inverse is not the best approach.) The matrix $E-aX$ is diagonally dominant, which is an important hypothesis for analyzing iterative algorithms, such as the Jacobi method for solving systems of equations. $\endgroup$
    – Henry Cohn
    Mar 21, 2011 at 6:50
  • $\begingroup$ @Nancy, I think what Thierry is saying is that what's efficient in theory may not be efficient in practice, and vice versa. Also, what's efficient when $n=10$ may not be when $n=10,000$, and also the answer may depend on just how sparse is sparse. $\endgroup$ Mar 21, 2011 at 6:52
  • $\begingroup$ Yeah, you can alteratively think of this problem as solve a linear equation in terms of $Y$ such that $(E-aX)Y=E$. $\endgroup$
    – Nancy
    Mar 21, 2011 at 9:30

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Matrix multiplication can be done faster than $O(n^3)$ even for dense matrices; for example there are implementations of Strassen multiplication faster than naive one for $n>200$. On the other hand, you're multiplying (possibly) dense matrix by a sparse matrix. So there may be faster multiplication algorithm still. $\endgroup$ Mar 22, 2011 at 0:32
  • 2
    $\begingroup$ Strassen's algorithm (and other similar "faster than O(n^3)" algorithms simply haven't proven to be useful in practice, even for fairly large (e.g. 10000 by 10000 matrix times 10000 by 10000 matrix) matrix-matrix multiplies. This is mostly because memory bandwidth and access times rather than flops are the real driving factor in matrix multiplication times. In this case, you'd definitely want to take advantage of the sparsity of X in doing the matrix multiplications. $\endgroup$ Mar 22, 2011 at 2:24
1
$\begingroup$

${(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.

$\endgroup$
0
$\begingroup$

$(E-aX)^{-1}$ can be solved iteratively by representing $X$ in rank-1 decomposition. Since we are not using the special structure of X, absorb $a$ into $X$ for simplification. Assume $X$ has rank $m<n$. Let $u, v$ vectors of size n. Assuming you have access to rank-1 decomposition, $ X = \sum_{i=1}^{m} u_i v'_i $

Define $X_k=X_{k-1}+u_kv'_k,$ with $X_1 = u_1v'_1, $ and $X=X_m.$ Now let $ M_k = (E + X_k)^{-1},$ with $M_0=E$, also define $w'_k=v'_kM_{k-1}.$ We can write

\begin{eqnarray*} M_k = (E + X_k)^{-1} & = & (M_{k-1}^{-1} + u_kv'_k)^{-1} \\ & = & (M_{k-1}-\frac{M_{k-1}u_kw'_k}{1+w'_ku_k}) \end{eqnarray*} Note that $1+w'_ku_k$ is a scalar quantity and no matrix-matrix multiplication is required.

$\endgroup$
0
$\begingroup$

I have a similar issue with inverting sparse matrices (inverting Hessian for Newton-like optimization). As was pointed out to me in this blog, inverse of sparse symmetric matrices not only does not have to be sparse, it cannot be even approximated with sparse matrices: an inverse of a tridiagonal matrix may have dense entries that are far from zero. Therefore, by inverting your matrix you may be loosing the performance advantage of a sparse matrix.

Many operations on sparse matrices are O(n^2) even though they are O(n^3) (or O(n^2.8)-ish) for general matrices. Besides that, each of those O(n^2) operations would be much faster on a typical computer because less amount of data passed back and forth would lead to better cache performance.

Therefore, as pointed out in other answers, you'll be much better of if you don't inverse the matrix, but use other means to solve the end problem you are working on. Something like a decomposition that would preserve sparsity would serve your (supposed) end goals much better.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.