3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 6
    $\begingroup$ 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. $\endgroup$
    – Juho
    Commented May 30, 2013 at 20:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – rajaditya_m
    Commented May 30, 2013 at 21:27
  • 1
    $\begingroup$ I would not consider Coppersmith-Winograd "basic". $\endgroup$
    – Tyson Williams
    Commented May 30, 2013 at 21:29
  • 3
    $\begingroup$ I would not consider Coppersmith-Winograd. $\endgroup$
    – Jeffε
    Commented May 30, 2013 at 23:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – Thomas Steinke
    Commented Jun 4, 2013 at 23:08

2 Answers 2

Reset to default
10
$\begingroup$

The fastest way to multiply dense matrices on a modern computer is to call BLAS.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Commented Jun 2, 2013 at 16:59
9
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.