Data Structures and Algorithms

   

The Curve of Matrix Multiplication Schemes

Authors: Warren D. Smith

Various methods have been devised to multiply N×N matrices using O(NE) arithmetic operations when N→∞, for various exponents E with 2<E≤3.However, in practice, the schemes with least known E are not the best, because they only start to win for infeasibly large N. Prior literature has unhealthily been fixated on E alone, i.e. on the asymptotic large-N performance alone. To address that, we propose investigating, for each method, not merely its E, but also its "breakeven N," meaning the least N causing that method to use fewer than the obvious algorithm's N3 bilinear multiplications [or fewer than Strassen'sO(N2.807355) scheme]. The set of (E,logN) datapoints then form a subset of the infinite rectangle (2,3]×[0,∞). Part of that rectangle is filled with datapoints, while another part contains none. What is of interest is the curve delineating the boundary between those two regions.

Comments: 17 Pages.

Download: PDF

Submission history

[v1] 2024-01-13 21:00:28

Unique-IP document downloads: 483 times

Vixra.org is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. Vixra.org will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus