Algoritmo de Strassen

Em álgebra linear, o algoritmo de Strassen, em homenagem a Volker Strassen, é um algoritmo de multiplicação de matrizes. É mais rápido que o algoritmo de multiplicação de matrizes padrão para matrizes grandes, com melhor complexidade assintótica ( O ( n log 2 ⁡ 7 ) {\displaystyle O(n^{\log _{2}7})} versus O ( n 3 ) {\displaystyle O(n^{3})} ), embora o algoritmo ingênuo seja frequentemente melhor para matrizes menores. O algoritmo de Strassen é mais lento do que os algoritmos conhecidos mais rápidos para matrizes extremamente grandes, mas tais algoritmos galácticos não são úteis na prática, pois são muito mais lentos para matrizes de tamanho prático. Para matrizes pequenas, existem algoritmos ainda mais rápidos. O algoritmo de Strassen funciona para qualquer anel, como soma/multiplicação, mas não para todos os semianéis, como min-plus ou álgebra booliana, onde o algoritmo ingênuo ainda funciona, sendo a chamada multiplicação de matrizes combinatória.