Strassen algorithm

<p>In <a href="/facts/Linear_algebra/8VaB4VWk">linear algebra</a>, the Strassen algorithm, named after <a href="/facts/Volker_Strassen/YrULq6nE">Volker Strassen</a>, is an <a href="/facts/Matrix_multiplication_algorithm/VrYWxfDt">algorithm for matrix multiplication</a>. It is faster than the standard matrix multiplication algorithm for large matrices, with a better <a href="/facts/Asymptotic_complexity/etHuVF3U">asymptotic complexity</a>, although the naive algorithm is often better for smaller matrices. The Strassen algorithm is slower than <a href="/facts/Computational_complexity_of_matrix_multiplication/KCn5KUzd">the fastest known algorithms</a> for extremely large matrices, but such <a href="/facts/Galactic_algorithm/Q17Y5kP8">galactic algorithms</a> are not useful in practice, as they are much slower for matrices of practical size. For small matrices even faster algorithms exist.
</p><p>Strassen's algorithm works for any <a href="/facts/Ring_(mathematics)/JnCUXz63">ring</a>, such as plus/multiply, but not all <a href="/facts/Semirings/7cSvWXVQ">semirings</a>, such as <a href="/facts/Min-plus_matrix_multiplication/TK6rwgMz">min-plus</a> or <a href="/facts/Boolean_algebra/VkCToAmg">boolean algebra</a>, where the naive algorithm still works, and so called combinatorial matrix multiplication.
</p>

Strassen algorithm open-in-new

Strassen algorithm