Lower bounds for the multiplicative complexity of matrix multiplication

Authors
Blaser, M
Citation
M. Blaser, Lower bounds for the multiplicative complexity of matrix multiplication, COMP COMPLE, 8(3), 1999, pp. 203-226
Citations number
12
Categorie Soggetti
Engineering Mathematics
Journal title
COMPUTATIONAL COMPLEXITY
ISSN journal
10163328 → ACNP
Volume
8
Issue
3
Year of publication
1999
Pages
203 - 226
Database
ISI
SICI code
1016-3328(1999)8:3<203:LBFTMC>2.0.ZU;2-Z
Abstract
We prove a lower bound of km + mn + k - m + n - 3 for the multiplicative co mplexity of the multiplication of k x m-matrices with m x n-matrices using the substitution method.