Is there any online implementation for the coppersmith matrix multiplication I have searched alot but can not find any? and if there is not any why is that Isn't this algotithm much faster than strassen in very large square matrices in the range of 100000 to millions, from what I understand the only downside of it is that the constants of running time is high

  • 2
    $\begingroup$ See here: en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm. The Copper-Smith algorithm is a galactic algorithm: en.wikipedia.org/wiki/Galactic_algorithm, which means it doesn't worth to implement it. $\endgroup$ Oct 13 '19 at 15:47
  • $\begingroup$ @AloneProgrammer thanks very much is there any chance that you may know Virginia Vassilevska Williams algorithm and if it is implemented and used or not? thanks for your time and help $\endgroup$
    – bedo dan
    Oct 13 '19 at 19:17
  • $\begingroup$ I don't think so... Even for Strassen and Winograd which are more popular ones, there are few implementations available online. Is this related to your research or you just simply looking for an efficient way to multiply large matrices? I mean you want to develop a new algorithm to beat for example Strassen or Winograd or you just looking for a better performance to multiply large matrices? $\endgroup$ Oct 13 '19 at 21:58
  • $\begingroup$ Have you thought about what it even just takes to store a dense matrix of size 100,000 to a million? You'll end up with $10^{10}$ to $10^{12}$ entries, each of which takes at least 4 bytes. Where do you get this much memory from? $\endgroup$ Oct 14 '19 at 1:56
  • $\begingroup$ @WolfgangBangerth We have some nodes in our supercomputer that have ~ 4TB RAM but I agree it is unreasonably large that just probably storing one matrix of this size would inflate the memory... $\endgroup$ Oct 14 '19 at 2:12

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.