Is there any method for multiplying matrices havin

Question

I want to multiply two matrices but the triple loop has O(n³) 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(n^2.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(n^2.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.

Answer 1

Matrices have O(n²) elements, and every element must be considered at least once for the result, so there is no possible way for a matrix multiplication algorithm to run in less than O(n²) operations.

Answer 2

If the matrices are known to be diagonal, you can multiply them in O(N) operations. But in general, you cannot.