1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ related: mathoverflow.net/q/297567/11260 $\endgroup$ – Carlo Beenakker Apr 23 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 Poloni Apr 23 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 Israel Apr 23 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 Poloni Apr 24 at 7:07
  • $\begingroup$ Good point. I should have said it is better than $O(N^3)$. $\endgroup$ – Robert Israel Apr 24 at 15:04
2
$\begingroup$

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

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

  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.

See: https://de.mathworks.com/matlabcentral/fileexchange/41957-matrix-inversion-using-cholesky-decomposition

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.