2
$\begingroup$

Let's say I have a somewhat large matrix $M$ and I need to find its inverse $M^{-1}$, but I only care about the first row in that inverse, what's the best algorithm to use to calculate just this row?

My matrix $M$ has the following properties:

  • All its entries describe probabilities, i.e. take on values between $0$ and $1$ (inclusive)
  • Many of the entries are $0$, but I don't know before hand which ones
  • All entries in the same row sum to $1$
  • $M$'s size is on the order of $10\times10$ to $100\times100$

I need to solve this problem literally a trillion times, though, so I need an algorithm that is as efficient as possible for matrices of this size.

$\endgroup$
  • $\begingroup$ As Omnomnomnom notices, it's equivlent to a linear system. If there is not much change between your trillion matrices, maybe an iteration method will work. As a starting point you will use the solution of the preceding run, and for the first, any direct method will do. $\endgroup$ – Jean-Claude Arbaut Apr 7 '15 at 22:24
2
$\begingroup$

You could row-reduce the augmented matrix $(M^T\mid (1,0,\dots,0)^T)$, where ${}^T$ here means transpose. This will row-reduce to $(I \mid v)$ where $v$ is the (transposed) first row of $M^{-1}$.

$\endgroup$
  • $\begingroup$ Basically Gauss-Jordan-Elimination, correct? That has a complexity of O(n³). Is that the best I can do for this? $\endgroup$ – Markus A. Sep 30 '14 at 18:50
  • $\begingroup$ If we don't know more about $M$, then I don't think you can exceed $O(n^3)$; Gauss-Jordan is fairly robust as a general approach. If $M$ has some additional structure (i.e. $M$ is diagonal, orthogonal, upper-triangular, sparse), then you may be able to find an algorithm tailored for that case, which provides an improvement. $\endgroup$ – Omnomnomnom Sep 30 '14 at 18:59
  • $\begingroup$ Also, I think that there are iterative methods of solution, if you're content with an approximation. $\endgroup$ – Omnomnomnom Sep 30 '14 at 19:00
  • $\begingroup$ An iterative method could indeed be a good way to go. The output if this calculation will be percentages and an accuracy of 1% would be sufficient. Do you have a suggestion of a specific algoritm? $\endgroup$ – Markus A. Sep 30 '14 at 19:03
  • 1
    $\begingroup$ @MarkusA. Since your matrix is sparse, you might consider a sparse direct solver such as KLU or SuperLU (AFAIK Matlab uses the first one). Efficiency of this approach, however, depends on how "many" entries are (non)zero. $\endgroup$ – Algebraic Pavel Oct 1 '14 at 13:17
1
$\begingroup$

Solve the linear system $$ M^T\boldsymbol{x}=\boldsymbol{e}_1, $$ where $$ {e}_1=(1,0,0,\ldots,0). $$

In general, the solution of the system $$ M^T\boldsymbol{x}=\boldsymbol{e}_k, $$ with $\boldsymbol{x}\in\mathbb R$, is the $k-$th row of $M^{-1}$, while $k-$th column of $M^{-1}$ is the solution of $$ M\boldsymbol{x}=\boldsymbol{e}_k. $$

$\endgroup$
  • $\begingroup$ Do you have a suggestion for which algorithm is best for solving this linear system? $\endgroup$ – Markus A. Sep 30 '14 at 18:56
  • 2
    $\begingroup$ Unfortunately, the fact that the right-hand side, i.e., $\boldsymbol{e}_1$, look simple and nice and with many zeroes, does not make our life easier. In other words, solving this system it is equally hard as solving it with arbitrary right-hand side. The algorithm to choose depends only on how nice the matrix $M$. Is it symmetric, is it sparse, does it have any other symmetries? $\endgroup$ – Yiorgos S. Smyrlis Sep 30 '14 at 19:03
  • 1
    $\begingroup$ It is sparse, but unfortunately I don't know anything about its shape before hand... Let me add a bit of information I do know about the matrix to the question, one sec... $\endgroup$ – Markus A. Sep 30 '14 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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