zbMATH — the first resource for mathematics

Rectangular matrix multiplication revisited. (English) Zbl 0872.68052
Summary: We give a constant $$\alpha> 0.294$$ and, for any $$\varepsilon >0$$, an algorithm for multiplying an $$N\times N$$ matrix by an $$N\times N^\alpha$$ matrix with complexity $$O(N^{2+ \varepsilon})$$.

MSC:
 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text:
References:
 [1] Bini, D.; Capovani, M.; Lotti, G.; Romani, F., On2.7799, Inform. process. lett., 8, 98-108, (1979) [2] Coppersmith, D., Rapid multiplication of rectangular matrices, SIAM J. comput., 11, 467-471, (Aug. 1982) [3] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. symbolic comput., 9, 251-280, (1990) · Zbl 0702.65046 [4] Pan, V.Ya., How to multiply matrices faster, Springer lecture notes in computer science, 179, (1984), Springer-Verlag New York/Berlin [5] R. Salem, D. C. Spencer, On sets of integers which contain no three terms in arithmetical progression, Proc. Natl. Acad. Sci. USA, 28, 561, 563 · Zbl 0060.10301 [6] Strassen, V., Gaussian elimination is not optimal, Numer. math., 13, 354-356, (1969) · Zbl 0185.40101 [7] V. Strassen, Relative bilinear complexity and matrix multiplication · Zbl 0621.68026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.