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?

$\begingroup$
$\endgroup$

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:

- 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.)

See: https://en.wikipedia.org/wiki/Schur_complement

- 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.

completelyunrelated 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)$. $\endgroup$ – Federico Poloni Apr 23 at 17:13