# Matrix multiplication algorithms for research

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.

• 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
May 30, 2013 at 20:42
• 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. May 30, 2013 at 21:27
• I would not consider Coppersmith-Winograd "basic". May 30, 2013 at 21:29
• I would not consider Coppersmith-Winograd. May 30, 2013 at 23:34
• 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. Jun 4, 2013 at 23:08

• 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. Jun 2, 2013 at 16:59