Complexity of calculating the determinant

1.6k Views Asked by At

For calculating the determinant, there are several algorithms available:

  • Laplace: $\mathcal{O}{(n!)}$
  • Bareiss: $\mathcal{O}{(n^3)}$
  • LU-decomposition: $\mathcal{O}{(n^3)}$
  • Strassen: $\mathcal{O}{(n^{2.807})}$
  • Coppersmith-Winograd: $\mathcal{O}{(n^{2.376})}$

Now my question is: What is the theoretical limit for calculating the determinant. It is $\mathcal{O}{(n^2)}$, isn't it? If yes, how is this possible?

Is this still an active research field, or is the Coppersmith-Winograd-Algorithm "the limit"?

1

There are 1 best solutions below

2
On BEST ANSWER

That algorithm's Wikipedia page mentions slight improvements for matrix multiplication, which has the same complexity as determinant calculation. The best is due to Le Gall 2014, reducing the exponent to $2.3728639$.