<p>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 <strong>symmetric positive-definite matrices</strong>? 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)$.</p>

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

CC BY-SA 3.0
2014-05-28T15:17:12.540Z
I think you mean $O(n^{2.38...}）$. inversion of general matrix takes the same amount of time as matrix multiplication.
Chao Xu
CC BY-SA 3.0
2014-05-28T20:23:55.723Z
Have you looked in the Knuth book for references?
Zsbán Ambrus
<cc.complexity-theory><ds.algorithms><matrices>
Best algorithm for inversion of symmetric positive-definite matrices
Timespace
# Best algorithm for inversion of symmetric positive-definite matrices

(Asked by: username_0 on 2014-05-28)

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?

**Tags:** cc.complexity-theory, ds.algorithms, matrices

> **Comments:**
> **username_1**: I think you mean $O(n^{2.38...}）$. inversion of general matrix takes the same amount of time as matrix multiplication.  
> **username_2**: Have you looked in the Knuth book for references?  

---

## 0 answers

