Premium
A practical algorithm for faster matrix multiplication
Author(s) -
Kaporin Igor
Publication year - 1999
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/(sici)1099-1506(199912)6:8<687::aid-nla177>3.0.co;2-i
Subject(s) - strassen algorithm , matrix multiplication , algorithm , multiplication algorithm , multiplication (music) , freivalds' algorithm , matrix (chemical analysis) , mathematics , stability (learning theory) , computer science , arithmetic , discrete mathematics , combinatorics , binary number , dijkstra's algorithm , graph , physics , materials science , quantum mechanics , shortest path problem , composite material , quantum , machine learning
The purpose of this paper is to present an algorithm for matrix multiplication based on a formula discovered by Pan [7]. For matrices of order up to 10 000, the nearly optimum tuning of the algorithm results in a rather clear non‐recursive one‐ or two‐level structure with the operation count comparable to that of the Strassen algorithm [9]. The algorithm takes less workspace and has better numerical stability as compared to the Strassen algorithm, especially in Winograd's modification [2]. Moreover, its clearer and more flexible structure is potentially more suitable for efficient implementation on modern supercomputers. Copyright © 1999 John Wiley & Sons, Ltd.