MATRIX MULTIPLICATION VIA ARITHMETIC PROGRESSIONS

被引：1298

作者：

COPPERSMITH, D

WINOGRAD, S

机构：

[1] Department of Mathematical Sciences, IBM Research Division, Thomas J. Watson Research Center, Yorktown Heights, New York, 10598

来源：

JOURNAL OF SYMBOLIC COMPUTATION | 1990年 / 9卷 / 03期

关键词：

D O I：

10.1016/S0747-7171(08)80013-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a new method for accelerating matrix multiplication asymptotically. Thiswork builds on recent ideas of Volker Strassen, by using a basic trilinear form which is not a matrix product. We make novel use of the Salem-Spencer Theorem, which gives a fairly dense set of integers with no three-term arithmetic progression. Our resulting matrix exponent is 2.376. © 1990, Academic Press Limited. All rights reserved.

引用

页码：251 / 280

页数：30

共 9 条

[1] BAHREND FA, 1946, P NATL ACAD SCI USA, V32, P331
[2] ON THE ASYMPTOTIC COMPLEXITY OF MATRIX MULTIPLICATION
COPPERSMITH, D
WINOGRAD, S
[J]. SIAM JOURNAL ON COMPUTING, 1982, 11 (03) : 472 - 492
[3] COPPERSMITH D, 1986, RC12104 IBM TJ WATS
[4] Pan V. Ya., 1978, 19th Annual Symposium on Foundations of Computer Science, P166, DOI 10.1109/SFCS.1978.34
[5] PAN VY, 1984, SPRINGER LECTURE NOT, V179
[6] On sets of integers which contain no three terms in arithmetical progression
Salem, R
Spencer, DC
[J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1942, 28 : 561 - 563
[7] PARTIAL AND TOTAL MATRIX MULTIPLICATION
SCHONHAGE, A
[J]. SIAM JOURNAL ON COMPUTING, 1981, 10 (03) : 434 - 455
[8] Strassen V., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P49, DOI 10.1109/SFCS.1986.52
[9] [No title captured]

← 1 →