Is there any method for multiplying matrices having O(n) complexity?

I want to开发者_C百科 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.

The best Matrix Multiplication Algorithm known so far is the "Coppersmith-Winograd algorithm" with O(n^2.38 ) complexity but it is not used for practical purposes.

However you can always use "Strassen's algorithm" which has O(n^2.81 ) complexity but there is no such known algorithm for matrix multiplication with O(n) complexity.

There is a theoretical lower bound for matrix multiplication at O(n^2) as you have to touch that many memory locations to do the multiplication. As others have said, there are algorithms that drop us below O(n^3), but are usually impractical in real use.

If you need to speed it up, you might want to look at Cache Oblivious Algorithms, such as this one (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5650) that accelerate performance by performing operations in a cache cohesive way, ensuring that data is in the cache when needed.

Short answer: No

Long answer: There are ways if you have special kinds of matricies (for instance a diagonal matrix). The better matrix multiplication algorithms out there can pare you down to something like O(n^2.4) (http://en.wikipedia.org/wiki/Coppersmith-Winograd_algorithm). The major one I am somewhat familiar with uses a divide and conquer algorithm to split up the workload (not the one I linked to).

I hope this helps!

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

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.

If

• your matrices are large
• they have a lot of zeroes
• you are willing to store them in strange formats

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).

No! I don't think so.

There is no way unless and until you are using a parallel processing machine. That too, it has its own dependencies and limitations.

Till now, its not yet achieved.

If you have n² processors and shared-read memory architecture, you could multiply two matrices in O(n) time... but this is only theory for now.