Computational complexity of matrix multiplication

The naive approach to matrix multiplication requires n³ field operations for multiplying two n × n matrices, which is represented as Θ(n³) in big O notation. This straightforward method is often taught in schools but is not the most efficient for large matrices.

The discovery of Strassen's algorithm in 1969 marked a significant improvement over the naive method. Strassen's algorithm reduces the number of required field operations, demonstrating that faster algorithms can exist beyond the basic schoolbook approach.

As of January 2024, the best known asymptotic complexity for matrix multiplication algorithms is O(n².371339), surpassing Strassen's original algorithm. This improvement highlights the ongoing quest for more efficient algorithms in theoretical computer science.