On the arithmetic complexity of Strassen-like matrix multiplications

Download

index.pdf

Date

2017-05-01

Author

Cenk, Murat

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

213
views

117
downloads

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.

Subject Keywords

Fast matrix multiplication, Strassen-like matrix multiplication, Computational complexity, Cryptographic computations, Computer algebra

URI

https://hdl.handle.net/11511/31534

Journal

JOURNAL OF SYMBOLIC COMPUTATION

DOI

https://doi.org/10.1016/j.jsc.2016.07.004

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

On the computation of generalized division polynomials Küçüksakallı, Ömer (2015-01-01) We give an algorithm to compute the generalized division polynomials for elliptic curves with complex multiplication. These polynomials can be used to generate the ray class fields of imaginary quadratic fields over the Hilbert class field with no restriction on the conductor.
On the Polynomial Multiplication in Chebyshev Form Akleylek, Sedat; Cenk, Murat; Özbudak, Ferruh (2012-04-01) We give an efficient multiplication method for polynomials in Chebyshev form. This multiplication method is different from the previous ones. Theoretically, we show that the number of multiplications is at least as good as Karatsuba-based algorithm. Moreover, using the proposed method, we improve the number of additions slightly. We remark that our method works efficiently for any N and it is easy to implement. To the best of our knowledge, the proposed method has the best multiplication and addition comple...
On the arithmetic operations over finite fields of characteristic three with low complexity AKLEYLEK, SEDAT; Özbudak, Ferruh; Özel, Claire Susanna (2014-03-15) In this paper, the Hermite polynomial representation is adapted as a new way to represent certain finite fields of characteristic three. We give the multiplication method to multiply two elements of F-3n in the Hermite polynomial representation with subquadratic computational complexity by using a divide-and-conquer idea. We show that in some cases there is a set of irreducible binomials in the Hermite polynomial representation to obtain modular reduction with a lower addition complexity than the standard p...
On m-th roots of nilpotent matrices Öztürk, Semra (2021-11-01) A new necessary and sufficient condition for the existence of an m-th root of a nilpotent matrix in terms of the multiplicities of Jordan blocks is obtained and expressed as a system of linear equations with nonnegative integer entries which is suitable for computer programming. Thus, computation of the Jordan form of the m-th power of a nilpotent matrix is reduced to a single matrix multiplication; conversely, the existence of an m-th root of a nilpotent matrix is reduced to the existence of a nonnegative ...
An improved algorithm for iterative matrix-vector multiplications over finite fields Mangır, Ceyda; Cenk, Murat; Manguoğlu, Murat (2018-11-09) Cryptographic computations such as factoring integers and computing discrete logarithms over finite fields require solving a large system of linear equations. When dealing with such systems iterative approaches such as Wiedemann or Lanczos are used. Both methods are based on the computation of a Krylov subspace in which the computational cost is often dominated by successive matrix-vector products. We introduce a new algorithm for computing iterative matrix-vector multiplications over finite fields. The pro...

Citation Formats

M. Cenk, “On the arithmetic complexity of Strassen-like matrix multiplications,” JOURNAL OF SYMBOLIC COMPUTATION, pp. 484–501, 2017, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31534.