<p>As others have said, there's no point in reinventing the wheel.</p>

<p>If you <em>must</em> implement it yourself for whatever reason, then you should either go for the naïve or Strassen algorithm. Naïve is faster for smaller matrices, but as matrix size increases to ~100 you will find that the Strassen algorithm starts to perform better as the impact of the larger constant factors starts to become less significant.</p>

<p>The exact crossover point will vary depending on machine (e.g. the memory and how it is allocated etc.) which is why using a library would be beneficial because it will do the job of determining which one to use (a task no doubt more tricky than implementing the algorithm itself).</p>

<p>Do not bother with Coppersmith Winograd and their derivatives; the constant factors are just too large to make them of any practical use.</p>

CC BY-SA 3.0
2013-05-31T14:03:19.137Z
2013-06-04T00:10:55.890Z
2013-06-04T00:10:55.890Z
Will Sewell
<p>The fastest way to multiply dense matrices on a modern computer is to call <a href="http://en.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms">BLAS</a>.</p>

CC BY-SA 3.0
2013-06-02T16:59:22.717Z
Even the naive $O(n^3)$-time algorithm can be dramatically improved in practice by carefully reordering instructions to reduce cache/page faults.  BLAS already does this.  If you write your own code, you won't.
Jeffε
CC BY-SA 3.0
2013-05-30T21:19:34.610Z
2013-05-30T21:19:34.610Z
Max Hutchinson
<p>I am implementing a matrix library for use in my research. This should support 2D matrices of size 100x100 (or more perhaps later on). I am a little confused about the algorithm I should be using for matrix multiplication. </p>

<p>I am extremely curious to know what kind of algorithms my peers use? 
The following are the possible choices: </p>

<ol>
<li><p>Naive $O(n^3)$</p></li>
<li><p>Strassens Algorithm $O(n^{2.807})$</p></li>
<li><p>Coppersmith Winograd Algorithm $O(n^{2.375})$</p></li>
</ol>

<p>Obviously (3) is quite complicated and may take quite a few tries to get right. Is it worth the effort ? I must mention here that speed is paramount for my usage as I will have a number of multiplication calls. </p>

CC BY-SA 3.0
2013-05-30T20:42:59.667Z
Why on earth would you like to implement these yourself? There are tons of programs and libraries that already have highly-optimized matrix multiplication methods. If you want to implement them for fun or learning purposes, maybe this is not the right forum for the question. Especially if you care about performance, *don't* waste your time.
Juho
CC BY-SA 3.0
2013-05-30T21:27:08.300Z
No I am not implementing them for fun. These are all to be used for OpenGL rendering codes and I am trying to minimize the number of external library dependence. That is why I am writing these basic classes myself.
rajaditya_m
CC BY-SA 3.0
2013-05-30T21:29:25.917Z
I would not consider Coppersmith-Winograd "basic".
Tyson Williams
CC BY-SA 3.0
2013-05-30T21:33:22.980Z
Absolutely agree with you Mr. Williams. Hence I asked the question. BUt just to clarify I meant basic classes as in Matrix and Vector classes. CW (and to some extent) is anything but basic.
rajaditya_m
CC BY-SA 3.0
2013-05-30T23:34:13.950Z
I would not consider Coppersmith-Winograd.
Jeffε
CC BY-SA 3.0
2013-06-04T23:08:00.577Z
If you don't want to use an existing library directly, you can still look at their documentation/code to see what algorithms and optimisations they use. Just google for matrix multiplication library.
Thomas Steinke
<linear-algebra><matrix-product>
Matrix multiplication algorithms for research
rajaditya_m
# Matrix multiplication algorithms for research

(Asked by: username_0 on 2013-05-30)

I am implementing a matrix library for use in my research. This should support 2D matrices of size 100x100 (or more perhaps later on). I am a little confused about the algorithm I should be using for matrix multiplication.

I am extremely curious to know what kind of algorithms my peers use?
The following are the possible choices:

1. Naive $O(n^3)$
2. Strassens Algorithm $O(n^{2.807})$
3. Coppersmith Winograd Algorithm $O(n^{2.375})$

Obviously (3) is quite complicated and may take quite a few tries to get right. Is it worth the effort ? I must mention here that speed is paramount for my usage as I will have a number of multiplication calls.

**Tags:** linear-algebra, matrix-product
> **Comments:**
> **username_1**: Why on earth would you like to implement these yourself? There are tons of programs and libraries that already have highly-optimized matrix multiplication methods. If you want to implement them for fun or learning purposes, maybe this is not the right forum for the question. Especially if you care about performance, *don't* waste your time.  
> **username_0**: No I am not implementing them for fun. These are all to be used for OpenGL rendering codes and I am trying to minimize the number of external library dependence. That is why I am writing these basic classes myself.  
> **username_2**: I would not consider Coppersmith-Winograd "basic".  
> **username_0**: Absolutely agree with you Mr. Williams. Hence I asked the question. BUt just to clarify I meant basic classes as in Matrix and Vector classes. CW (and to some extent) is anything but basic.  
> **username_3**: I would not consider Coppersmith-Winograd.  
> **username_4**: If you don't want to use an existing library directly, you can still look at their documentation/code to see what algorithms and optimisations they use. Just google for matrix multiplication library.  

---

## 2 answers

### Answer by username_6 on 2013-05-30. Score: 10 | Accepted answer

The fastest way to multiply dense matrices on a modern computer is to call [BLAS](http://en.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms).

> **Comments:**
> **username_3**: Even the naive $O(n^3)$-time algorithm can be dramatically improved in practice by carefully reordering instructions to reduce cache/page faults.  BLAS already does this.  If you write your own code, you won't.  

---

### Answer by username_5 on 2013-05-31. Score: 9

As others have said, there's no point in reinventing the wheel.

If you *must* implement it yourself for whatever reason, then you should either go for the naïve or Strassen algorithm. Naïve is faster for smaller matrices, but as matrix size increases to ~100 you will find that the Strassen algorithm starts to perform better as the impact of the larger constant factors starts to become less significant.

The exact crossover point will vary depending on machine (e.g. the memory and how it is allocated etc.) which is why using a library would be beneficial because it will do the job of determining which one to use (a task no doubt more tricky than implementing the algorithm itself).

Do not bother with Coppersmith Winograd and their derivatives; the constant factors are just too large to make them of any practical use.


---

