We need to carry out $2(n^3)-(n^2)$ number of basic operations (like addition and multiplication) to multiply two $n×n$ matrices. Is there any other efficient way so that we could use less no. of operations to multiply them?
Asked
Active
Viewed 68 times
1
-
There have been a lot of progress on this starting with the algorithm of Volker Strassen: https://en.wikipedia.org/wiki/Strassen_algorithm – Angina Seng Aug 18 '17 at 18:05
-
https://en.wikipedia.org/wiki/Coppersmith–Winograd_algorithm – Xander Henderson Aug 18 '17 at 18:05
-
But Strassen method is for 2×2 right? – Vishnu Mohan Aug 18 '17 at 18:09
1 Answers
2
The method you described is $O(n^3)$, using big O notation.
Algorithms do exist that have sub-cubic runtimes.
This Wikipedia section summarizes the history and current state of those algorithms quite nicely.
The current $O(n^k)$ algorithm with the lowest known exponent $k$ is a generalization of the Coppersmith–Winograd algorithm that has an asymptotic complexity of $O(n^{2.3728639})$, by François Le Gall.
Zubin Mukerjee
- 17,832