0
$\begingroup$

I'm trying to find some theory to help me explicitly express the inverse of a matrix (or a close approximation of the inverse). My matrix has the following properties:

  1. invertible
  2. positive definite
  3. symmetric
  4. all diagonal entries $> 0$
  5. all off diagonal entries $\le 0$
  6. sum across any row or column is nonnegative and further for each row, $i$, the diagonal entry, $d_{ii} \ge \sum_{j\ne i}|d_{ij}|$

6) tells me that all eigenvalues are $\ge 0$ (Gershgorin theorem) but since I know the matrix is invertible, the eigenvalues must be positive.

Anyway, does anyone know if there's a way to approximate the inverse?

thanks

$\endgroup$
  • 5
    $\begingroup$ Why do you need the inverse of this matrix? For example, if you need to solve systems of equations involving the matrix, then its most likely the case that this can be done more easily without explicitly computing the inverse. $\endgroup$ – Brian Borchers Jan 20 '14 at 19:37
  • 1
    $\begingroup$ It's likely that the use of the inverse matrix in the optimization routine can be replaced by the solution of one or more systems of equations involving the matrix and that the inverse itself isn't needed. $\endgroup$ – Brian Borchers Jan 20 '14 at 20:28
  • 4
    $\begingroup$ But you don't hear what people are saying. It's not possible in general unless (i) you have additional information about the matrix, or (ii) you use what you will need the inverse for. The matrices you have appear frequently in the discretization of PDEs and if there was an even halfway decent approximation of the inverse, everyone would use it as a preconditioner. But there isn't. So that gets back to the two points above: you need to tell us more or you won't get a better answer than "It can't be done in general". $\endgroup$ – Wolfgang Bangerth Jan 21 '14 at 5:10
  • 1
    $\begingroup$ Geoff and Wolfgang, thanks for the replies but I don't have more information on the matrix type. The properties I provided are already based on analysis of the problem structure, if I could say anything more to help, I would. I found a couple of papers that provide bounds for the inverse of a symmetric, positive definite matrix but my matrix is an M-matrix and I thought maybe there are better bounds for this class. Wolfgang is saying that there aren't any, which answers my question, so I need to think about a different approach. Thank you for the help $\endgroup$ – John Jan 21 '14 at 15:16
  • 1
    $\begingroup$ Can you construct a typical matrix of reasonable size arising from your optimization problem and post an image of it here? Eg., using imagesc in matlab and saving to .png? I know you're saying there is no additional structure, but how do you know for sure? You might be surprised. $\endgroup$ – Nick Alger Jan 22 '14 at 4:03
2
$\begingroup$

Unfortunately, the listed set of matrix properties does not give any hope on a closed-form of the matrix inverse or its reasonable approximation (for this specific case). It is too general, and finding matrix inverse (or matrix factorization) is a non-trivial task. Otherwise, such fundamental problem as preconditioning would have been successfully solved.

You have the following options, as far as I can see:

  1. Perform exact factorization of the matrix and tolerate that it is memory consuming and slow.
  2. Find an accelerated method to speed up the factorization/inverse calculation. That would require domain (physics) knowledge from where this matrix is coming. Examples: Hierarchical matrices, FMM- or FFT-based methods. Different application areas might have many more specialized methods that offer certain advantages. There is also an active field in randomized methods.
  3. Stick to very coarse approximations: diagonal(+possible near zone) matrix inverse. Here, you manually select "most significant" parts of the matrix and choosing only them to form an approximation inverse. Commonly, it is the matrix main diagonal and possibly some near-zone around it (subject to row/col reordering).

NB: I would omit discussion of the question of why explicit calculation of the matrix inverse should be avoided in the first place.

$\endgroup$
1
$\begingroup$

Truncated Neumann series: let $D$ be the diagonal of your matrix, and $-N$ be the non-diagonal part. Then, $M=D-N=D(I-D^{-1}N)$, and $$M^{-1}=(I-D^{-1}N)D^{-1}=(I+D^{-1}N + D^{-1}ND^{-1}N + D^{-1}ND^{-1}ND^{-1}N + \dots)D^{-1}.$$

Truncate the infinite sum where you prefer. Note that $D$ and $N$ contain non-negative elements, so what you get is guaranteed to be an approximation from below.

$\endgroup$

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.