0
$\begingroup$

Hi,

All iterative solvers I've been able to find are for a system Ax = b where b is a vector. Does anyone know of general iterative solvers for AX = B where X, B are matrices, or more specifically finding the inverse A^-1? (Assuming A is large and sparse.)

Thanks!

Improve this question
$\endgroup$
1
  • $\begingroup$ If $B$ has $r$ columns, you can solve $AX=B$ by calling your $Ax=b$ solver $r$ times. As Federico points out, it's almost invariably a mistake to compute $A^{-1}$. finally this question is not appropriate for this site. $\endgroup$
    – Chris Godsil
    May 30, 2012 at 22:00

2 Answers 2

Reset to default
2
$\begingroup$

Unless your matrices have a special structure, both $A^{-1}$ and $A^{-1}B$ are dense (full), general matrices without any special properties. Even storing them in memory will be prohibitive.

The short answer is: don't do it. :)

The long answer is: look for structure in your matrices, and exploit it. If there is no structure and you really need to perform this computation, then your best bet is using an exact solver, not an iterative one. It will be extremely slow ($O(N^3)$ time and $O(N^2)$ storage), but there are no shortcuts.

Improve this answer
$\endgroup$
3
  • $\begingroup$ In my case the entries of A^-1 have a probabilistic interpretation, so I need to at least approximate the inverse. A is sparse because I'm making some approximations (it would otherwise be dense). I was hoping the approximations would lead to a block diagonal structure where the largest block was tractable for exact solvers, but this was not the case. However, I believe the structure may be almost block diagonal, leading to a sparse inverse. $\endgroup$
    – Nicholas Andrews
    May 30, 2012 at 22:04
  • $\begingroup$ Have you actually tried any canned software to see if your conjecture is correct? $\endgroup$
    – Igor Rivin
    May 30, 2012 at 23:54
  • $\begingroup$ What is the probabilistic interpretation of the entries of $A^{-1}$? Are you looking for the entries of a covariance matrix of the form $(X^{T}X)^{-1}$ for example? "Almost Block Diagonal" really isn't gonig to be enough to help here- as soon as you've got one entry linking two blocks, you can get fill in of the linking block in the inverse matrix. $\endgroup$
    – Brian Borchers
    May 31, 2012 at 3:26
0
$\begingroup$

You can find $A^{-1}$ from $Ax=b$ where A is a symmetric matrix and $x$, $b$ are vectors using efficient iterative solvers. I outline the algorithm I came up with here.

  1. First solve $x$
  2. Solve a new problem $\bar{A}\bar{x} = \bar{b}$:
    • $\bar{b}$ = [x; eye(k)]
    • $\bar{x}$ = values of $A^{-1}$ that fully characterize the matrix
    • $\bar{A}$ = matrix that has both of these restrictions:
      • $A^{-1}\bar{b} = b$
      • $A^{-1} A = I$
  3. Use $\bar{x}$ to for $A^{-1}$

A recommended iterative solver for this kind of problems is lsmr.

Improve this answer
$\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.