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?

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

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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