vectorious icon indicating copy to clipboard operation
vectorious copied to clipboard

Published 20 hours ago • verified publisher icon mateogianolio

Matrix: multiplication performance

Open mateogianolio opened this issue 8 years ago • 3 comments

A switch to using the Strassen algorithm will reduce the algorithmic complexity from O(n3) to O(n2.81).

mateogianolio avatar Mar 25 '16 14:03 mateogianolio

If you're willing to go that path, maybe switching to Coppersmith-Winograd is even better. Strassen was the first to find an algorithm better than O(n^3), this led to more research finding even better algoritms. It's actually stated in the Wikipedia link you posted.

Note that I'm totally clueless about any of this.

bartvanandel avatar May 09 '18 11:05 bartvanandel

If I have time, I would contribute to it As I learnt it in uni and I am kind of interested in making an implementation, if you're not against

Beraliv avatar Sep 03 '18 21:09 Beraliv

I think the Strassen algorithm is the best choice for most applications.

From Wikipedia:

Algorithms with better asymptotic running time than the Strassen algorithm are rarely used in practice, because the large constant factors in their running times make them impractical.

mateogianolio avatar Sep 04 '18 07:09 mateogianolio