Live briefing
Everything about Strassen algorithm
Recursive algorithm for matrix multiplication
In linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm for matrix multiplication. It is faster than the standard matrix multiplication algorithm for large matrices, with a better asymptotic complexity, although the naive algorithm is often better for smaller matrices. The Strassen algorithm is slower than the fastest known algorithms for extremely large matrices, but such galactic algorithms are not useful in practice, as they are much slower for matrices of practical size. For small matrices, highly optimized implementations of the conventional algorithm are generally faster because Strassen's additional additions and recursion overhead outweigh its reduction in multiplications. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: Strassen algorithmA 5-minute orientation
- Skim a recent paper: Minimizing Multiplication of Kernel Computation in Convolutional Neural Networks Using Strassen AlgorithmInfluential work since 2022
- Pick up a classic book: Computer algorithmsThe most-reprinted book on the subject
- Read the landmark paper: Quantum Circuit Design for Integer Multiplication Based on Schönhage–Strassen AlgorithmCited 16 times
- Go sideways: Matrix multiplication algorithmA closely related topic
- Go sideways: Computational complexity of matrix multiplicationA closely related topic
đź“– Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Quantum Circuit Design for Integer Multiplication Based on Schönhage–Strassen Algorithm
A Tensor Product Formulation of Strassen′s Matrix Multiplication Algorithm with Memory Reduction
Double Precession Floating Point Multiplier using Schonhage – Strassen Algorithm used for FPGA Accelerator
An Efficient DCT Compression Technique using Strassen's Matrix Multiplication Algorithm
The Better Accuracy of Strassen-Winograd Algorithms (FastMMW)
Floating Point Multiplication Based on Schonhage Strassen Algorithm
A Rigorous Extension of the Schönhage-Strassen Integer Multiplication Algorithm Using Complex Interval Arithmetic
Improved FIR Filter using Schonhage-Strassen Algorithm based Multipliers
🆕 Influential since 2022
Minimizing Multiplication of Kernel Computation in Convolutional Neural Networks Using Strassen Algorithm
Minimizing Multiplication of Kernel Computation in Convolutional Neural Networks Using Strassen Algorithm
Algoritme Kritpografi RSA Menggunakan Algoritme Schönhage-Strassen
AlphaEvolve-Based Rank-48 Algorithm for 4Ă—4 Real-Valued Matrix Multiplication: 28 nm Implementation and Comparison with Strassen
Compiling Strassen-like Matrix Multiplication Algorithms to Fast CUDA Kernels
đź“š Books worth reading
Computer algorithmsEllis Horowitz · 1997
Fundamentals of computer algorithmsEllis Horowitz · 1978
Handbook of Theoretical Computer ScienceJan van Leeuwen · 1990
Abstract machine models for parallel and distributed computingM. Kara · 1996
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- Matrix multiplication algorithm Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms…
- Computational complexity of matrix multiplication Unsolved problem in computer science What is the fastest algorithm for matrix multiplication? More unsolved problems in computer science In theoretical…
- Matrix multiplication In mathematics, specifically in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication…
- Schönhage–Strassen algorithm The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers, published by Arnold Schönhage and Volker Strassen…
- Volker Strassen Volker Strassen (born April 29, 1936) is a German mathematician, a professor emeritus in the department of mathematics and statistics at the University…
- Multiplication algorithm A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient…
- Bareiss algorithm In mathematics, the Bareiss algorithm, named after Erwin Bareiss, is an algorithm to calculate the determinant or the echelon form of a matrix with integer…
- Toom–Cook multiplication Toom–Cook, sometimes known as Toom-3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned…