closed form approximation of matrix inverse with special properties

Question

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

Answer 1

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.

Answer 2

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.