CODEWITHSUNDEEP
algorithmmatrix
Evan Sanderson
Evan Sanderson

Reputation: 105

What is the quickest method of matrix multiplication?

I've been working on a rather extensive program as of late, and i'm currently at a point where I have to utilize matrix multiplication. Thing is, for this particular program, speed is crucial. I'm familiar with a number of matrix setups, but I would like to know which method will run the fastest. I've done extensive research, but turned up very little results. Here is a list of the matrix multiplication algorithms I am familiar with:

If anyone needs clarification on the methods I listed, or on the question in general, feel free to ask.

Upvotes: 3

Views: 334

Answers (2)

igon
igon

Reputation: 3046

The Strassen algorithm and the naive (O(n^3)) one are the most used in practice.

More complex algorithms with tighter asymptotic bounds are not used because they benefits would be apparent only for extremely large matrices, due to their complexity, e.g. Coppersmith algorithm.

As others pointed out you might want to use a library like ATLAS which will automatically tune the algorithm depending on the characteristcs of the platform where you are executing, e.g. L1/L2 cache sizes.

Upvotes: 3

Mathieu Borderé
Mathieu Borderé

Reputation: 4367

Quickest way might be using an existing library that's already optimized, you don't have to reinvent the wheel every time.

Upvotes: 2

Related Questions