Strassen Algoritması: Matris Çarpımını Hızlandıran Zarif Fikir

Önce sezgiyle: çarpma "pahalı", toplama "ucuz"

Bilgisayar bilimlerinde küçük bir gerçek vardır: çarpma işlemleri genellikle toplamadan daha pahalıdır. Bu fark donanımda küçülse de büyük matrislerle (görüntü işleme, sinir ağları, fizik simülasyonları) uğraşırken çarpma sayısı toplam süreyi belirler.

İki $2 \times 2$ matrisi çarpalım:

$$\begin{pmatrix} a & b \\ c & d \end{pmatrix} \cdot \begin{pmatrix} e & f \\ g & h \end{pmatrix} = \begin{pmatrix} ae+bg & af+bh \\ ce+dg & cf+dh \end{pmatrix}$$

Sayalım: 8 çarpma, 4 toplama. Genel $n \times n$ matriste her hücre $n$ çarpma istediği için klasik algoritma $O(n^3)$ zaman alır. 1960'lara kadar herkes "bu zaten en iyisi" derdi.

Strassen'in patlatıcı fikri (1969)

Alman matematikçi Volker Strassen o yıl iki sayfalık bir makaleyle herkesi şaşırttı: $2 \times 2$ çarpımı 7 çarpma + 18 toplama ile yapılabilir. Bir çarpma az, ama 14 toplama fazla — küçük matrislerde anlamsız. Asıl güzellik şurada: bu hile özyinelemeli uygulanırsa kazanç katlanarak büyür.

Strassen'in yedi yardımcı çarpımı (kısaltılmış):

• $M_1 = (a+d)(e+h)$
• $M_2 = (c+d)e$
• $M_3 = a(f-h)$
• $M_4 = d(g-e)$
• $M_5 = (a+b)h$
• $M_6 = (c-a)(e+f)$
• $M_7 = (b-d)(g+h)$

Sonra sonuç matrisinin hücreleri bu $M_i$'lerin toplam/farkıyla yazılıyor (örnek: sol üst $= M_1+M_4-M_5+M_7$). Doğrulaması cebirseldir ama görmek için kâğıt-kalem yeter.

Karmaşıklık nasıl düşüyor?

Klasik böl-fethet algoritmasında $n \times n$ matrisi dört $\tfrac{n}{2} \times \tfrac{n}{2}$ bloğa bölersek 8 alt-çarpım yapılır:

$T(n) = 8 \cdot T(n/2) + O(n^2) \Rightarrow T(n) = O(n^3)$

Strassen ile sadece 7 alt-çarpım:

$T(n) = 7 \cdot T(n/2) + O(n^2) \Rightarrow T(n) = O(n^{\log_2 7}) \approx O(n^{2.807})$

Üs $3$'ten $2.807$'ye düştü. Küçük gibi mi görünüyor? Bir milyon elemanlı (1000×1000) matriste yaklaşık 4 kat hızlanma; 10000×10000'de 15 kattan fazla kazanım.

"Az çarpma" niye o kadar önemli?

Çünkü matris çarpımı, modern hesaplamanın atomudur. Bir görüntü filtresi, bir grafik dönüşümü, bir nöral ağ ileri yayılımı — hepsinin altında yatar. GPT gibi büyük modeller eğitilirken saniyede milyarlarca matris çarpımı yapılır. Strassen'in fikrini izleyen geliştirmeler (Coppersmith–Winograd, Le Gall) bugün üssü $2.371$'e kadar indirdi. Hâlâ açık soru: Acaba en alt sınır $n^2$ mı?

Niye herkes Strassen kullanmıyor?

Çünkü gerçek dünyada sabitler önemli. Strassen 18 toplama getiriyor; bellek erişim deseni karmaşıklaşıyor; sayısal kararlılık bir miktar bozuluyor (kayar nokta hataları biraz büyüyor). Bu yüzden BLAS gibi kütüphaneler küçük bloklarda klasik, büyük bloklarda Strassen (veya türevi) kullanır — hibrit yaklaşım.

Hayat dersi: "kanıtlanmış sınır" kanıtlanmadıysa şüphe duy

Strassen öncesi nesil $O(n^3)$'e doğal sınır gözüyle bakıyordu, çünkü 8 çarpım sezgisel olarak "gereklidir" görünüyordu. Strassen'in dersi: sezgisel zorunluluk, matematiksel zorunluluk değildir. Bir alt sınır kanıtlanana dek sezgiye fazla güvenme.

Bugün hâlâ kimse $n \times n$ matris çarpımının gerçek karmaşıklığını bilmiyor. Belki bir gün lise öğrencisi bir algoritma keşfeder ve üs $2.5$'e iner. Strassen 1969'da bunu yaptı; engel sadece zihinde duruyordu.