Fastest algorithm for computing the determinant of a matrix?

Question

For a research paper, I have been assigned to research the fastest algorithm for computing the determinant of a matrix.

I already know about LU decomposition and Bareiss algorithm which both run in O(n^3), but after doing some digging, it seems there are some algorithms that run somewhere between n^2 and n^3.

This source (see page 113-114) and this source (see page 198) say that an algorithm exists that runs in O(n^2.376) because it is based on the Coppersmith-Winograd's algorithm for multiplying matrices. However, I have not been able to find any details on such an algorithm.

My questions are:

1. What is the fastest created (non-theoretical) algorithm for computing the determinant of a matrix?
2. Where can I find information about this fastest algorithm?

Thanks so much.

Answer 1

I believe the fastest in practice (and commonly used) algorithm is the Strassen Algorithm. You can find explanation on Wikipedia along with sample C code.

Algorithms based on Coppersmith-Winograd's multiplication algorithms are too complex to be practical, though they have best asymptotic complexity as far.

Answer 2

I know this is not a direct answer for my question, but for the purposes of completing my research paper, it is enough. I just ended up asking my professor and I will summarize what he said:

Summary:

• The fastest matrix-multiplication algorithms (e.g., Coppersmith-Winograd and more recent improvements) can be used with O(n^~2.376) arithmetic operations, but use heavy mathematical tools and are often impractical.
• LU Decomposition and Bareiss do use O(n^3) operations, but are more practical

In short, even though LU Decomposition and Bareiss are not as fast as the most efficient algorithms, they are more practical and I should focus my research paper on these two.

Thanks for all who commented and helped!