Jianyu Huang, Tyler Smith, Greg Henry et al. · 2016
We dispel with “street wisdom” regarding the practical implementation of Strassen's algorithm for matrix-matrix multiplication (DGEMM). Conventional wisdom: it is only practical for very large matrices. Our implementation is practical for small matrices. Conventional wisdom: the matrices being multiplied should be relatively square. Our implementation is practical for rank-k updates, where k is relatively small (a shape of importance for libraries like LAPACK). Conventional wisdom: it inherently requires substantial workspace. Our implementation requires no workspace beyond buffers already incorporated into conventional high-performance DGEMM implementations. Conventional wisdom: a Strassen DGEMM interface must pass in workspace. Our implementation requires no such workspace and can be plug-compatible with the standard DGEMM interface. Conventional wisdom: it is hard to demonstrate speedup on multi-core architectures. Our implementation demonstrates speedup over conventional DGEMM even on an Intel <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">®</sup> Xeon Phi™ coprocessor1 utilizing 240 threads. We show how a distributed memory matrix-matrix multiplication also benefits from these advances.
Cited by 25
Jianyu Huang, Devin A. Matthews, Robert A. Geijn · SIAM Journal on Scientific Computing · 2018
Tensor contraction (TC) is an important computational kernel widely used in numerous applications. It is a multidimensional generalization of matrix multiplication (GEMM). While Strassen's algorithm for GEMM is well studied in theory and practice, extending it to accelerate TC has not been previously pursued. Thus, we believe this to be the first paper to demonstrate how one can in practice speed up TC with Strassen's algorithm. By adopting a block-scatter-matrix format, a novel matrix-centric tensor layout, we can conceptually view TC as GEMM for a general stride storage, with an implicit tensor-to-matrix transformation. This insight enables us to tailor a recent state-of-the-art implementation of Strassen's algorithm to a recent state-of-the-art TC, avoiding explicit transpositions (permutations) and extra workspace, and reducing the overhead of memory movement that is incurred. Performance benefits are demonstrated with a performance model as well as in practice on modern single core, multicore, and distributed memory parallel architectures, achieving up to $1.3 \times$ speedup. The resulting implementations can serve as a drop-in replacement for various applications with significant speedup.
Cited by 12
Jean‐Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic · arXiv (Cornell University) · 2024
We propose a non-commutative algorithm for multiplying 2x2 matrices using 7 coefficient products. This algorithm reaches simultaneously a better accuracy in practice compared to previously known such fast algorithms, and a time complexity bound with the best currently known leading term (obtained via alternate basis sparsification). To build this algorithm, we consider matrix and tensor norms bounds governing the stability and accuracy of numerical matrix multiplication. First, we reduce those bounds by minimizing a growth factor along the unique orbit of Strassen's 2x2-matrix multiplication tensor decomposition. Second, we develop heuristics for minimizing the number of operations required to realize a given bilinear formula, while further improving its accuracy. Third, we perform an alternate basis sparsification that improves on the time complexity constant and mostly preserves the overall accuracy.
Cited by 3Open access
Ikenmeyer, Christian, Moosbauer, Jakob · ArXiv.org · 2025
We give a short proof for Strassen's result that the rank of the 2 by 2 matrix multiplication tensor is at most 7. The proof requires no calculations and also no pattern matching or other type of nontrivial verification, and is based solely on properties of a specific order 6 group action. Our proof is based on the recent combination of flip graph algorithms and symmetries.
Cited by 0Open access
Juby Mathew, R Vijaya Kumar · 2012
The main focus of this paper is to compare the execution time complexity and space complexity between Strassen’s algorithm and the conventional algorithm for matrix multiplication. The aim is to design a program, which generates two matrices with various dimensions, and multiplies the two matrices using both the Strassen’s algorithm and the conventional algorithm. The execution time of each algorithm is recorded to evaluate the performance of each algorithm. The programming language used this project is Java. Some of the main achievements in this project are, successfully divide matrices into blocks, the Strassen’s algorithm was applied to each blocks recursively, and the level of recursion was controlled. The overall finding is that the Strassen’s algorithm is more efficient than conventional algorithm on large size of matrices. However, in scientific computing, memory has to be considered. The results show that Strassen’s algorithm needs more memory allocations than the conventional algorithm, due to the fact in design that more arrays need to be created.
Cited by 5
M.M. Shul'ts · USSR Computational Mathematics and Mathematical Physics · 1977
Cited by 0
Grey Ballard, James Demmel, Olga Holtz et al. · arXiv (Cornell University) · 2012
Parallel matrix multiplication is one of the most studied fundamental problems in distributed and high performance computing. We obtain a new parallel algorithm that is based on Strassen's fast matrix multiplication and minimizes communication. The algorithm outperforms all known parallel matrix multiplication algorithms, classical and Strassen-based, both asymptotically and in practice. A critical bottleneck in parallelizing Strassen's algorithm is the communication between the processors. Ballard, Demmel, Holtz, and Schwartz (SPAA'11) prove lower bounds on these communication costs, using expansion properties of the underlying computation graph. Our algorithm matches these lower bounds, and so is communication-optimal. It exhibits perfect strong scaling within the maximum possible range. Benchmarking our implementation on a Cray XT4, we obtain speedups over classical and Strassen-based algorithms ranging from 24% to 184% for a fixed matrix dimension n=94080, where the number of nodes ranges from 49 to 7203. Our parallelization approach generalizes to other fast matrix multiplication algorithms.
Cited by 9Open access
Grey Ballard, James Demmel, Olga Holtz et al. · arXiv (Cornell University) · 2012
Parallel matrix multiplication is one of the most studied fundamental\nproblems in distributed and high performance computing. We obtain a new\nparallel algorithm that is based on Strassen's fast matrix multiplication and\nminimizes communication. The algorithm outperforms all known parallel matrix\nmultiplication algorithms, classical and Strassen-based, both asymptotically\nand in practice.\n A critical bottleneck in parallelizing Strassen's algorithm is the\ncommunication between the processors. Ballard, Demmel, Holtz, and Schwartz\n(SPAA'11) prove lower bounds on these communication costs, using expansion\nproperties of the underlying computation graph. Our algorithm matches these\nlower bounds, and so is communication-optimal. It exhibits perfect strong\nscaling within the maximum possible range.\n Benchmarking our implementation on a Cray XT4, we obtain speedups over\nclassical and Strassen-based algorithms ranging from 24% to 184% for a fixed\nmatrix dimension n=94080, where the number of nodes ranges from 49 to 7203.\n Our parallelization approach generalizes to other fast matrix multiplication\nalgorithms.\n
Cited by 0Open access
Ivo Hedtke · arXiv (Cornell University) · 2010
The well known algorithm of Volker Strassen for matrix multiplication can only be used for $(m2^k \times m2^k)$ matrices. For arbitrary $(n \times n)$ matrices one has to add zero rows and columns to the given matrices to use Strassen's algorithm. Strassen gave a strategy of how to set $m$ and $k$ for arbitrary $n$ to ensure $n\leq m2^k$. In this paper we study the number $d$ of additional zero rows and columns and the influence on the number of flops used by the algorithm in the worst case ($d=n/16$), best case ($d=1$) and in the average case ($d\approx n/48$). The aim of this work is to give a detailed analysis of the number of additional zero rows and columns and the additional work caused by Strassen's bad parameters. Strassen used the parameters $m$ and $k$ to show that his matrix multiplication algorithm needs less than $4.7n^{\log_2 7}$ flops. We can show in this paper, that these parameters cause an additional work of approx. 20 % in the worst case in comparison to the optimal strategy for the worst case. This is the main reason for the search for better parameters.
Cited by 7Open access
Jianyu Huang, Chenhan D. Yu, Robert A. Geijn · arXiv (Cornell University) · 2018
Conventional GPU implementations of Strassen's algorithm (Strassen) typically rely on the existing high-performance matrix multiplication (GEMM), trading space for time. As a result, such approaches can only achieve practical speedup for relatively large, "squarish" matrices due to the extra memory overhead, and their usages are limited due to the considerable workspace. We present novel Strassen primitives for GPUs that can be composed to generate a family of Strassen algorithms. Our algorithms utilize both the memory and thread hierarchies on GPUs, reusing shared memory and register files inherited from GEMM, fusing additional operations, and avoiding extra workspace. We further exploit intra- and inter-kernel parallelism by batching, streaming, and employing atomic operations. We also develop a performance model for NVIDIA Volta GPUs to select the appropriate blocking parameters and predict the performance for GEMM and Strassen. Overall, our 1-level Strassen can achieve up to 1.11x speedup with a crossover point as small as 1,536 compared to cublasSgemm on a NVIDIA Tesla V100 GPU. With additional workspace, our 2-level Strassen can achieve 1.19x speedup with a crossover point at 7,680.
Cited by 9Open access
Chien‐Hung Huang, Jeremy Johnson, R. W. Johnson · Applied Mathematics Letters · 1990
Cited by 30
David A. Bailey, King Lee, Horst D. Simon · The Journal of Supercomputing · 1991
Cited by 69
K. Deepthi, B. Mounika, Y. Chalapathi Rao · 2025
This paper presents a hardware implementation of 32-bit matrix multiplication using Strassen's algorithm, targeting improvements in speed, power efficiency, and chip area. Strassen's method reduces the number of required multiplications by dividing matrices recursively into smaller blocks, achieving a computational complexity of approximately <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{O}\left(\mathrm{n}^{2}. 81\right)$</tex> compared to the conventional <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{O}\left(\mathrm{n}^{3}\right)$</tex> method. The design is implemented in Verilog and synthesized using 90 nm SAED technology. Comparative evaluation shows a 30 % reduction in area, 20 % savings in power, and 42 % improvement in timing over traditional matrix multiplication. These improvements construct the design fit for super-computing applications including steganography, artificial intelligence, and display adapter, where large-scale matrix operations are general. The work shows that a recursive, hardware-aware approach can critically accelerate matrix computation while remaining are agreeable with 32-bit architectures.
Cited by 0
Kouya, Tomonori · arXiv (Cornell University) · 2014
The Strassen algorithm and Winograd's variant accelerate matrix multiplication by using fewer arithmetic operations than standard matrix multiplication. Although many papers have been published to accelerate single- as well as double-precision matrix multiplication by using these algorithms, no research to date has been undertaken to accelerate multiple precision matrix multiplication. In this paper, we propose a multiple precision matrix multiplication program for matrices of any size and test its performance. We also reveal special properties of our program through its application to LU decomposition.
Cited by 0Open access
Pierrick Gaudry, Alexander I. Kruppa, Paul Zimmermann · SPIRE - Sciences Po Institutional REpository · 2007
Schönhage-Strassen's algorithm is one of the best known algorithms for multiplying large integers. Implementing it ef?ciently is of utmost importance, since many other algorithms rely on it as a subroutine. We present here an improved implementation, based on the one distributed within the GMP library. The following ideas and techniques were used or tried: faster arithmetic modulo 2n + 1, improved cache locality, Mersenne transforms, Chinese Remainder Reconstruction, the √2 trick, Harley's and Granlund's tricks, improved tuning.
Cited by 36Open access
Chien‐Hung Huang, Jeremy Johnson, R. W. Johnson · Applied Mathematics Letters · 1991
Cited by 4
B. Raghu Kumar, Chien‐Hung Huang, R. W. Johnson et al. · 2002
A programming methodology based on tensor products has been used for designing and implementing block recursive algorithms for parallel and vector multiprocessors. A previous tensor product formulation of Strassen's matrix multiplication algorithm requires working arrays of size O(7/sup n/) for multiplying 2/sup n/*2/sup n/ matrices. The authors present a modified tensor product formulation of Strassen's algorithm in which the size of working arrays can be reduced to O(4/sup n/). The modified formulation exhibits sufficient parallel and vector operations for efficient implementation. Performance results on the Cray Y-MP are presented.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 26
Ahmad Jibir Kawu, Aishatu Yahaya Umar, Saminu I. Bala · 2017 IEEE 3rd International Conference on Electro-Technology for National Development (NIGERCON) · 2017
Matrix multiplication is presumably one of the most important techniques in many scientific applications. Efficient implementation of this technique on the ubiquitous multi-cores is therefore critical to the performance of this broad range of applications. The execution time of sequential and parallel implementation of the algorithms were measured, analyzed and interpreted. The main aim of this research work is to compare the speedup obtainable from executing one-level recursion parallel Strassen's matrix multiplication algorithm on multi-core processors. The programs were written in C++/OpenMP. The result of the research work showed significant performance of the parallel programs of the Strassen's algorithm for large matrix size. It was also observed that Strassen's algorithm performs better for large matrix size while having the same performance as the Traditional algorithm for small matrices. The result suggested that with one step recursion, for both small and large matrix sizes Strassen's algorithm is the best choice.
Cited by 3
Niall Emmart, Charles Weems · Parallel Processing Letters · 2011
We have improved our prior implementation of Strassens algorithm for high performance multiplication of very large integers on a general purpose graphics processor (GPU). A combination of algorithmic and implementation optimizations result in a factor of up to 13.9 speed improvement over our previous work, running on an NVIDIA 295. We have also reoptimized the implementation for an NVIDIA 480, from which we obtain a factor of up to 19 speedup in comparison with a Core i7 processor core of the same technology generation. To provide a fairer chip to chip comparison, we also determined total GPU throughput on a set of multiplications relative to all of the cores on a multicore chip running in parallel. We find that the GTX 480 provides a factor of six higher throughput than all four cores/eight threads of the Core i7. This paper discusses how we adapted the algorithm to operate within the limitations of the GPU and how we dealt with other issues encountered in the implementation process, including details of the memory layout of our FFTs. Compared with our earlier work, which used Karatsuba's algorithm to guide multiplication of different operand sizes built on top of Strassen's algorithm being applied to fixed-size segments of the operands, we are now able to apply Strassen's algorithm directly to operands ranging in size from 255K bits to 16,320K bits.
Cited by 48
Henry M. D. Ip, Jade Low, Peter Y. K. Cheung et al. · 2003
Strassen's algorithm is an efficient method for multiplying large matrices. We explore various ways of mapping Strassen's algorithm into reconfigurable hardware that contains one or more customisable instruction processors. Our approach has been implemented using Nios processors with custom instructions and with custom-designed coprocessors, taking advantage of the additional logic and memory blocks available on a reconfigurable platform.
Cited by 4