On the arithmetic complexity of Strassen-like matrix multiplications

Creative Commons License

CENK M., Hasan M. A.

JOURNAL OF SYMBOLIC COMPUTATION, cilt.80, ss.484-501, 2017 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 80
  • Basım Tarihi: 2017
  • Doi Numarası: 10.1016/j.jsc.2016.07.004
  • Dergi Adı: JOURNAL OF SYMBOLIC COMPUTATION
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.484-501
  • Anahtar Kelimeler: Fast matrix multiplication, Strassen-like matrix multiplication, Computational complexity, Cryptographic computations, Computer algebra, ALGORITHMS
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

The Strassen algorithm for multiplying 2 x 2 matrices requires seven multiplications and 18 additions. The recursive use of this algorithm for matrices of dimension n yields a total arithmetic complexity of (7n(2.81) - 6n(2)) for n = 2(k). Winograd showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying 2 x 2 matrices with seven multiplications is called a Strassen-like algorithm. Winograd also discovered an additively optimal Strassen-like algorithm with 15 additions. This algorithm is called the Winograd's variant, whose arithmetic complexity is (6n(2.81) - 5n(2)) for n = 2(k) and (3.73n(2.81) - 5n(2)) for n = 8 . 2(k), which is the best-known bound for Strassen-like multiplications. This paper proposes a method that reduces the complexity of Winograd's variant to (5n(2.81) + 0.5n(2.59) + 2n(2.32) - 6.5n(2)) for n = 2(k). It is also shown that the total arithmetic complexity can be improved to (3.55n(2.81) + 0.148n(2.59) + 1.02n(2.32) - 6.5n(2)) for n = 8 . 2(k), which, to the best of our knowledge, improves the best-known bound for a Strassen-like matrix multiplication algorithm. (C) 2016 Elsevier Ltd. All rights reserved.