MATRIX MULTIPLICATION VIA ARITHMETIC PROGRESSIONS

被引：1316

作者：

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 [J].

COPPERSMITH, D ;

WINOGRAD, S .

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 [J].

Salem, R ;

Spencer, DC .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1942, 28 :561-563

[7] PARTIAL AND TOTAL MATRIX MULTIPLICATION [J].

SCHONHAGE, A .

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 →