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$
5
-
1$\begingroup$ related: mathoverflow.net/q/297567/11260 $\endgroup$– Carlo BeenakkerApr 23, 2020 at 17:02
-
2$\begingroup$ 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)$. $\endgroup$– Federico PoloniApr 23, 2020 at 17:13
-
2$\begingroup$ The complexity of matrix inversion is not $O(N^3)$. Using Coppersmith-Winograd it is $O(N^{2.376})$. $\endgroup$– Robert IsraelApr 23, 2020 at 17:34
-
$\begingroup$ @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()$). $\endgroup$– Federico PoloniApr 24, 2020 at 7:07
-
$\begingroup$ Good point. I should have said it is better than $O(N^3)$. $\endgroup$– Robert IsraelApr 24, 2020 at 15:04
Add a comment
|
1 Answer
$\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.
