1
$\begingroup$

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

$\endgroup$
  • 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$ – Alone Programmer Oct 13 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 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$ – Alone Programmer Oct 13 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$ – Wolfgang Bangerth Oct 14 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$ – Alone Programmer Oct 14 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.