Fastest algorithm for computing the determinant of a matrix?

algorithm matrix complexity-theory linear-algebra determinants
John-Luke Laue picture John-Luke Laue · Nov 18, 2014 · Viewed 20.8k times · Source

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

Sopel picture Sopel · Nov 18, 2014

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.

Related questions

How do you rotate a two dimensional array?

Inspired by Raymond Chen's post, say you have a 4x4 two dimensional array, write a function that rotates it 90 degrees. Raymond links to a solution in pseudo code, but I'd like to see some real world stuff. [1][2][3][4] [5][6][7][8] [9][0][1][2] [3][4][5][6] Becomes: [3][9][5][1] [4][0][6][2] [5][1][7][3] [6][2][8][4] Update: Nick's …

Read More
Python Inverse of a Matrix

How do I get the inverse of a matrix in python? I've implemented it myself, but it's pure python, and I suspect there are faster modules out there to do it.

Read More
What is the fastest way to transpose a matrix in C++?

I have a matrix (relatively big) that I need to transpose. For example assume that my matrix is a b c d e f g h i j k l m n o p q r I want the result …

Read More