Algorytm Strassena – algorytm wykorzystywany do mnożenia macierzy. Został nazwany na cześć swego twórcy – Volkera Strassena. Jest on szybszy od standardowego mnożenia macierzy i jest użyteczny dla dużych macierzy, ale działa wolniej od najszybszej znanej obecnie metody mnożenia – algorytmu Coppersmitha-Winograda – dla bardzo dużych macierzy.
Algorytm został opublikowany w 1969 roku. Pomimo że był tylko trochę szybszy od metody klasycznej, jako pierwszy wykazał, że standardowe podejście nie jest optymalne. Dzięki niemu rozpoczęto poszukiwania jeszcze szybszych algorytmów, aż do algorytmu Coppersmitha-Winograda opublikowanego w 1987 roku.
Działanie algorytmu
Niech i będą dwiema macierzami kwadratowymi nad pierścieniem Chcemy obliczyć macierz taką, że
Jeżeli macierze i nie są rozmiaru , to brakujące kolumny i wiersze wypełniamy zerami. Następnie dzielimy macierze i na macierze klatkowe o równych rozmiarach.
gdzie:
czyli
W powyższym przypadku nie zredukowaliśmy liczby potrzebnych do wykonania mnożeń. Wciąż musimy wykonać 8 mnożeń, czyli tyle samo, jak w przypadku zwykłego mnożenia macierzy.
Definiujemy nowe macierze według poniższego wzoru:
Powyższe macierze zostaną użyte do wyrażenia macierzy w zależności od Mk.