Search

The Strassen algorithm for multiplying 22 matrices requires seven multiplications and 18 additions. The recursive use of this algorithm for matrices of dimension n yields a total arithmetic complexity of (7n2.816n2) for n=2k. Winograd showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying 22 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 (6n2.815n2) for n=2k and (3.73n2.815n2) for n=82k, which is the best-known bound for Strassen-like multiplications. This paper proposes a method that reduces the complexity of Winograd's variant to (5n2.81+0.5n2.59+2n2.326.5n2) for n=2k. It is also shown that the total arithmetic complexity can be improved to (3.55n2.81+0.148n2.59+1.02n2.326.5n2) for n=82k, which, to the best of our knowledge, improves the best-known bound for a Strassen-like matrix multiplication algorithm.

In this work an efficient algorithm to perform a block decomposition for large dense rectangular matrices with entries in F"2 is presented. Matrices are stored as column blocks of row major matrices in order to facilitate rows operation and matrix multiplications with blocks of columns. One of the major bottlenecks of matrix decomposition is the pivoting involving both rows and column exchanges. Since row swaps are cheap and column swaps are order of magnitude slower, the number of column swaps should be reduced as much as possible. Here an algorithm that completely avoids the column permutations is presented. An asymptotically fast algorithm is obtained by combining the four Russian algorithm and the recursion with the Strassen algorithm for matrix-matrix multiplication. Moreover optimal parameters for the tuning of the algorithm are theoretically estimated and then experimentally verified. A comparison with the state of the art public domain software SAGE shows that the proposed algorithm is generally faster.

In this paper we show that nxn matrices with entries from a semiring R which is generated additively by q generators can be multiplied in time O(q^2n^@w), where n^@w is the complexity for matrix multiplication over a ring (Strassen: @w

The main purpose of this paper is to present a fast matrix multiplication algorithm taken from the paper of Laderman et al. (Linear Algebra Appl. 162-164 (1992) 557) in a refined compact "analytical" form and to demonstrate that it can be implemented as quite efficient computer code. Our improved presentation enables us to simplify substantially the analysis of the computational complexity and numerical stability of the algorithm as well as its computer implementation. The algorithm multiplies two N × N matrices using O(N2.7760) arithmetic operations. In the case where N = 18 ċ 48k, for a positive integer k, the total number of flops required by the algorithm is 4.894N2.7760 - 16.165N2, which may be compared to a similar estimate for the Winograd algorithm, 3.732N2.8074 - 5N2 flops, N = 8 ċ 2k, the latter being current record bound among all known practical algorithms. Moreover, we present a pseudo-code of the algorithm which demonstrates its very moderate working memory requirements, much smaller than that of the best available implementations of Strassen and Winograd algorithms. For matrices of medium-large size (say, 2000 ≤ N < 10,000) we consider one-level algorithms and compare them with the (multilevel) Strassen and Winograd algorithms. The results of numerical tests clearly indicate that our accelerated matrix multiplication routines implementing two or three disjoint product-based algorithm are comparable in computational time with an implementation of Winograd algorithm and clearly outperform it with respect to working space and (especially) numerical stability. The tests were performed for the matrices of the order of up to 7000, both in double and single precision.

Matrix-matrix multiplication is normally computed using one of the BLAS or a reinvention of part of the BLAS. Unfortunately, the BLAS were designed with small matrices in mind. When huge, well-conditioned matrices are multiplied together, the BLAS perform like the blahs, even on vector machines. For matrices where the coefficients are well conditioned. Winograd's variant of Strassen's algorithm offers some relief, but is rarely available in a quality form on most computers. We reconsider this method and offer a highly portable solution based on the Level 3 BLAS interface.

IT IS shown that Karatsubi's algorithm, applied to the problem of calculating the product of matrices, is transformed into Strassen's algorithm.