Algorytm Strassena

[tomek3232]

Mam za zadanie napisać program w pascalu który będzie obliczał mnożenie macierzy algorytmem strassena, tylko że nie wiem jak ten algorytm wygląda dla macierzy większych niż 2 stopnia

Algorytm dla macierzy o wymiarze 2 wygląda następująco
P=(A11+A22)*(B11+B22)
Q=(A21+A22)*B11
R=A11*(B12+B22)
S=A22*(B21+B11)
T=B22*(A11-A12)
U=(A21-A11)*(B11-B12)
V=(A12+A22)*(B21+B22)

na podstawie których oblicza się
C11=P+S-T+V
C12=R+T
C21=Q+S
C22=P+R-Q+U

Więc jak będzie wyglądał ten algorytm dla macierzy np.wymiary czwartego
Może tak?:
P=(A11+A22+A33+A44)*(B11+B22+B33+B44)
Q=(A21+A22+A23+A24)*B11
itd
Bardzo proszę o pomoc ponieważ muszę koniecznie to zrozumieć abym mógł zacząć pisać kod

[myky]

Dołączam się do pytania. Bardzo proszę o odpowiedź.

[Mariusz M]

Na wejściu masz macierze o wymiarach będących potęgą dwójki
Sam algorytm jest typu dziel i rządź (divide et impera)
Jak masz zdefiniowane mnożenie macierzy o wymiarach 2x2 to
macierze o większych wymiarach dzielisz rekurencyjnie na bloki
aż w końcu otrzymasz macierze 2x2 następnie wyniki łączysz ze sobą

Pamiętasz np sortowanie przez scalanie albo Quicksort
idea jest podobna

[myky]

o dziękuję bardzo.