As I know, the time complexity for usual inversion algorithm of general matrix is $O(n^3)$. In recent years, there is a improvement from $O(n^3)$ to $O(n^{2.8....})$. However, does there exists a faster inversion algorithm for symmetric positive-definite matrices? I have tried to search the answer but the best answer I have seen is to inverse the symmetric positive-definite matrix by using Cholesky decomposition. However, its complexity is also $O(n^3)$.

Could you provide me the fastest algorithm (even only the name) for inversion of symmetric positive-definite matrices?

  • 1
    $\begingroup$ I think you mean $O(n^{2.38...})$. inversion of general matrix takes the same amount of time as matrix multiplication. $\endgroup$ – Chao Xu May 28 '14 at 15:17
  • $\begingroup$ Have you looked in the Knuth book for references? $\endgroup$ – Zsbán Ambrus May 28 '14 at 20:23

Your Answer

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

Browse other questions tagged or ask your own question.