I have searched and what I understood was that they use the naive one with several memory and cache optimizations.

  1. However, I wanted to know whether they are using the Strassen or the Coppersmith-Winograd algorithms.

  2. If they don't use them, then why?

  3. Additionally, does NumPy use BLAS or ATLAS? What I did is that I looked up similar questions but did not find specific answer to why/why not NumPy is faster than most implementations.

  • 5
    $\begingroup$ Those algorithms are fancy algorithms for doing matrix multiplication in a smart way but you don't really get a good performance for extremely large matrices on a single core. The best way is to use naive algorithm but parallelized it with MPI or OpenMP. That's a reason why you don't see standard linear algebra libraries use Strassen, Winograd, or Copper-Smith algorithm for matrix multiplication. In other word: It doesn't worth to do it with these fancy algorithms. $\endgroup$ Oct 10 '19 at 19:36
  • $\begingroup$ @AloneProgrammer can you tell me what may be a sufficiently large input size matrices where the naive one will beat copper smith or strassen? and why cant i parallelize these 2 algorithms? thank you very much $\endgroup$
    – bedo dan
    Oct 10 '19 at 19:39
  • 3
    $\begingroup$ Note that my purpose is: correctly parallelized naive algorithm will beat Strassen and Winograd on a single core. For a matrix with 121203 x 121203 members: Strassen will be dumped up even if you have several TB RAM available and for Winograd you should wait at least billion of years to get the answer. But it would be done simply in PETSC for example cause PETSC uses naive algorithm parallelized with MPI. I have a code written in C++ that I could share it with you to test both Strassen and Winograd algorithms and see their performance. $\endgroup$ Oct 10 '19 at 19:44
  • 1
    $\begingroup$ Can you give us a bit more information? What kind of Matrices are you working with. Are they sparse? Are they symmetric? Are they dense? $\endgroup$
    – MPIchael
    Oct 11 '19 at 9:26
  • 1
    $\begingroup$ I presume they don't have to be square. Are they sparse? i.e. are there only a few nonzero entries near the diagonal, or are they "full"? $\endgroup$
    – MPIchael
    Oct 11 '19 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.