ضرب ماتریس اشتراسن

ضرب ماتریس‌های n×n با تقسیم و حل: به‌جای ۸ ضرب نیم‌اندازه، ۷ تا با چند جمع و تفریق اضافه؛ زمان O(n^2.81).

با تقسیم هر ماتریس به چهار قطعه‌ی n/2 × n/2، ضرب معمولی ۸ ضرب نیم‌اندازه لازم دارد: T(n) = 8T(n/2) + O(n²) = O(n³).

ورودی:

A 2×2 · B 2×2خروجی PDF

دو ماتریس ۲×۲: هفت ضرب عدد به‌جای هشت.

def strassen(A, B):
n = len(A)
if n != len(B) or n & (n - 1) != 0:
return None
if n == 1:
return [[A[0][0] * B[0][0]]]
h = n // 2
a11, a12, a21, a22 = quarters(A, h)
b11, b12, b21, b22 = quarters(B, h)
p1 = strassen(a11, sub(b12, b22))
p2 = strassen(add(a11, a12), b22)
p3 = strassen(add(a21, a22), b11)
p4 = strassen(a22, sub(b21, b11))
p5 = strassen(add(a11, a22), add(b11, b22))
p6 = strassen(sub(a12, a22), add(b21, b22))
p7 = strassen(sub(a11, a21), add(b11, b12))
c11 = add(sub(add(p5, p4), p2), p6)
c12 = add(p1, p2)
c21 = add(p3, p4)
c22 = sub(sub(add(p5, p1), p3), p7)
C = [c11[i] + c12[i] for i in range(h)] + [c21[i] + c22[i] for i in range(h)]
return C
def quarters(M, h):
return ([r[:h] for r in M[:h]], [r[h:] for r in M[:h]], [r[:h] for r in M[h:]], [r[h:] for r in M[h:]])
def add(X, Y):
return [[x + y for x, y in zip(rx, ry)] for rx, ry in zip(X, Y)]
def sub(X, Y):
return [[x - y for x, y in zip(rx, ry)] for rx, ry in zip(X, Y)]

ناوردا: هر فراخوانی حاصل‌ضرب دقیق دو ماتریس ورودی‌اش را برمی‌گرداند؛ هفت ضرب کافی است چون هر خانه‌ی C ترکیب خطی آن‌هاست.

شروع اجرا

n—

1	3
7	5

6	8
4	2

جدول هنوز خالی است.

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

نارنجی = در همین گام عوض شد

[1, 3][7, 5]

[6, 8][4, 2]

گام ۱ از ۹۵

توضیح

با تقسیم هر ماتریس به چهار قطعه‌ی n/2 × n/2، ضرب معمولی ۸ ضرب نیم‌اندازه لازم دارد: T(n) = 8T(n/2) + O(n²) = O(n³).

اشتراسن (۱۹۶۹) با جمع و تفریق‌های زیرکانه فقط ۷ ضرب لازم دارد (P1 تا P7) و هر قطعه‌ی حاصل ترکیبی از آن‌هاست:

T(n) = 7T(n/2) + O(n²) = O(n^log₂7) ≈ O(n^2.81)

جمع و تفریق ارزان‌اند (O(n²)) و کم کردن یک ضرب از هشت در هر سطح، در عمق log n اثر بزرگی دارد.
برای ماتریس‌های کوچک، ضرب معمولی سریع‌تر است؛ در عمل زیر یک اندازه‌ی مشخص به روش معمولی برمی‌گردند.

درخت فراخوانی‌ها در هر سطح ۷ شاخه دارد؛ جدول‌های A و B همیشه قطعه‌های فراخوانی فعلی‌اند.