Menu
I want to multiply two matrices but the triple loop has O(n3) complexity. Is there any algorithm in dynamic programming to multiply two matrices with O(n) complexity?
ok fine we can't get best than O(n2.81 )
edit: but is there any solution that can even approximate the result upto some specific no. of columns and rows of matrix
i mean we get the best of O(n2.81 ) with a complex solution but perfect results but if there is any solution for even an approximation of multiplication of matrices as we have formulas for factorial approximation etc.
if there is any you know it will help me
regards.
527
As of December 2020, the matrix multiplication algorithm with best asymptotic complexity runs in O(n2.3728596) time, given by Josh Alman and Virginia Vassilevska Williams. However, this algorithm is a galactic algorithm because of the large constants and cannot be realized practically.
As of October 2022, the best announced bound on the asymptotic complexity of a matrix multiplication algorithm is O(n2.37188) time, given by Duan, Wu and Zhou announced in a preprint. This improves on the bound of O(n2.3728596) time, given by Josh Alman and Virginia Vassilevska Williams.
I understand that when you multiply two time complexities, you just multiply them as usual, for example a time complexity of n log n multiplied by the time complexity of n will give you a time complexity of (n^2) log n .
Hence, we know that multiplication has a time complexity of O(N logN) while usual algorithms in practice have a time complexity of O(N^2).
If
you can devise algorithms whose complexities depend only on the number of non-zero elements. This can be mandatory for some problems (eg. finite element methods).
177
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
