0

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

John
  • 109
  • 2
  • 5
    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. – Brian Borchers Jan 20 '14 at 19:37
  • The answer to that would require too much explanation :) but the short answer that if I can approximate the inverse of such a matrix, I can use it in an optimization problem directly and maintain linearity (it's a high dimensional problem). – John Jan 20 '14 at 20:02
  • 1
    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. – Brian Borchers Jan 20 '14 at 20:28
  • it is unlikely and actually impossible. I do not want to get into details of the optimization problem but believe me that I need an explicit approximation of the inverse. There is a paper here: http://www.sciencedirect.com/science/article/pii/0024379582902385 that is close to what I need but this requires off-diagonal elements to be strictly negative and I'm not sure if the proof would work for nonpositive – John Jan 20 '14 at 23:05
  • Since you won't tell us what your optimization problem is, it's impossible to discuss how you might approach that problem without explicitly constructing this inverse matrix. – Brian Borchers Jan 20 '14 at 23:13
  • I do need the explicit inverse. If I had to do this once for a specific matrix, I wouldn't need to post this as a question but I need a general approach for a class of matrices with the above properties. What I do with the resulting inverse is irrelevant. – John Jan 21 '14 at 00:14
  • 4
    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". – Wolfgang Bangerth Jan 21 '14 at 05:10
  • @John: Please provide more background for your problem. The volunteers on this site who answer questions are asking for more information because we want to help you, and what we're saying is that the answer you're going to get is "No, there's no good way to approximate the inverse," and that doesn't help you solve your problem. If you provide us with more information, it is more likely that we can give you a more helpful answer. – Geoff Oxberry Jan 21 '14 at 09:47
  • 1
    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 – John Jan 21 '14 at 15:16
  • 1
    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. – Nick Alger Jan 22 '14 at 04:03

2 Answers2

2

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.

Anton Menshov
  • 8,672
  • 7
  • 38
  • 94
1

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.

Federico Poloni
  • 11,344
  • 1
  • 31
  • 59