# Low-complexity method for sub-matrix inversion

Assume that $$\mathbf{A}$$ be an $$N\times N$$ matrix. We know that the complexity of the computation of matrix inversion is $$\mathcal{O}(N^3)$$. Let define $$\mathbf{D}=\mathbf{A}^{-1}$$. Now, assume that $$\mathbf{D}_n$$ is any $$n\times n$$ sub-matrix of $$\mathbf{D}$$, where $$n\ll N$$. Is there any way to compute $$\mathbf{D}_n$$ exactly with complexity oreder related to $$n$$ (not $$N$$)? If not, is there any better approximation than $$\mathbf{D}_n\simeq\mathbf{A}_n^{-1}$$, where $$\mathbf{A}_n$$ is corresponding sub-matrix?

• related: mathoverflow.net/q/297567/11260 – Carlo Beenakker Apr 23 at 17:02
• Complexity completely unrelated to $N$ seems impossible, since $D_n$ depends nontrivially on all entries of $A$, so we have at least to read them all in $O(N^2)$. – Federico Poloni Apr 23 at 17:13
• The complexity of matrix inversion is not $O(N^3)$. Using Coppersmith-Winograd it is $O(N^{2.376})$. – Robert Israel Apr 23 at 17:34
• @RobertIsrael $\text{True complexity of matrix inversion (unknown)} \subset O(N^{2376}) \subset O(N^3)$, so technically OP is correct (or at least "as wrong as you", depending on how you interpret $O()$). – Federico Poloni Apr 24 at 7:07
• Good point. I should have said it is better than $O(N^3)$. – Robert Israel Apr 24 at 15:04

Unfortunately, the following solutions are not independent of $$N,$$ (they can't be, see comment to your question) but may still help reduce the computations:

1. By using Schur complement, you can compute the upper $$n\times n$$ matrix $$(\boldsymbol{D}_n)$$ by using an inverse of an $$(N-n)\times (N-n)$$ matrix and an $$n\times n$$ matrix. (You can also try a few interesting approximations based on your matrix structure which may turn out to be better than direct inversion of the $$n\times n$$ submatrix.)
1. You may use the method (in the link below) based on matrix inversion using Cholesky decomposition but stop during the second step (equation solving) at the required number of elements.