تقسیم‌و‌غلبه برای ضرب ماتریس: از رویکرد ساده تا الگوریتم اشتراسن

مسئله ضرب ماتریس

با داشتن دو ماتریس n × n به نام A و B، هدف محاسبه حاصل‌ضرب آن‌ها C = A × B است، که هر عنصرش این‌طور تعریف می‌شود:

C[i][j] = Σ (برای k = 1 تا n) A[i][k] × B[k][j]

این عملیات در سراسر علوم کامپیوتر و ریاضیات کاربردی ظاهر می‌شود، از تبدیلات گرافیک کامپیوتری تا حل سیستم‌های معادلات خطی تا محاسبات شبکه عصبی که یادگیری ماشین امروزی زیربنای آن‌هاست.

الگوریتم ساده

رویکرد ساده مستقیماً تعریف ریاضی را با استفاده از سه حلقه تودرتو پیاده‌سازی می‌کند.

SQUARE-MATRIX-MULTIPLY(A, B, n):
  یک ماتریس جدید n × n به نام C بساز
  برای i = 1 تا n:
      برای j = 1 تا n:
          C[i][j] = 0
          برای k = 1 تا n:
              C[i][j] = C[i][j] + A[i][k] · B[k][j]
  C را برگردان

هر عنصر از ماتریس خروجی نیازمند n ضرب و جمع است، و n² عنصر برای محاسبه وجود دارد، که زمان اجرای کلی Θ(n³) می‌دهد. برای دهه‌ها، این زمان اجرای مکعبی اساساً اجتناب‌ناپذیر برای ضرب ماتریس فرض می‌شد.

یک تلاش اول: تقسیم‌و‌غلبه ساده

با به‌کارگیری الگوی تقسیم‌و‌غلبه، یک ماتریس n × n می‌تواند به چهار زیرماتریس n/2 × n/2 افراز شود، و ضرب ماتریس می‌تواند به‌صورت بازگشتی برحسب این زیرماتریس‌ها بیان شود.

افراز A و B به ربع‌ها:
A = [A11  A12]      B = [B11  B12]
    [A21  A22]          [B21  B22]

حاصل‌ضرب C = A × B سپس این‌طور است:
C11 = A11·B11 + A12·B21
C12 = A11·B12 + A12·B22
C21 = A21·B11 + A22·B21
C22 = A21·B12 + A22·B22

این نیازمند ۸ ضرب بازگشتی از زیرماتریس‌های n/2 × n/2 است، به‌علاوه ۴ جمع از ماتریس‌های n/2 × n/2، که هرکدام زمان Θ(n²) می‌گیرند. رابطه بازگشتی حاصل این است:

T(n) = 8T(n/2) + Θ(n²)

حل این رابطه بازگشتی، با استفاده از روش استاد که در مقاله بعدی این مجموعه پوشش داده می‌شود، T(n) = Θ(n³) می‌دهد — دقیقاً همان زمان اجرای مجانبی الگوریتم سه‌حلقه ساده. صرفاً بازنویسی بازگشتی مسئله هیچ بهبودی فراهم نکرد.

بینش پیشگامانه اشتراسن

در سال ۱۹۶۹، فولکر اشتراسن راهی برای محاسبه حاصل‌ضرب دو ماتریس ۲×۲ با استفاده از فقط ۷ ضرب به‌جای ۸ کشف کرد، به قیمت جمع و تفریق‌های اضافی ماتریسی. از آنجا که ضرب‌ها عملیات گران‌تری هستند از نظر مجانبی وقتی به‌طور بازگشتی اعمال شوند، این کاهش کوچک تأثیر نامتناسب بزرگی روی زمان اجرای کلی دارد.

الگوریتم اشتراسن ابتدا ۷ حاصل‌ضرب میانی را با استفاده از ترکیب‌های خاصی از مجموع‌ها و تفاضل‌های زیرماتریس محاسبه می‌کند:

P1 = A11 · (B12 - B22)
P2 = (A11 + A12) · B22
P3 = (A21 + A22) · B11
P4 = A22 · (B21 - B11)
P5 = (A11 + A22) · (B11 + B22)
P6 = (A12 - A22) · (B21 + B22)
P7 = (A11 - A21) · (B11 + B12)

چهار ربع خروجی سپس صرفاً از این ۷ حاصل‌ضرب، با استفاده فقط از جمع و تفریق، بازسازی می‌شوند:

C11 = P5 + P4 - P2 + P6
C12 = P1 + P2
C21 = P3 + P4
C22 = P5 + P1 - P3 - P7

تأیید این فرمول‌ها از نظر جبری تأیید می‌کند دقیقاً همان نتیجه فرمول‌های ضرب ماتریس استاندارد را تولید می‌کنند، اما با یک ضرب کمتر در هر سطح بازگشت.

تحلیل زمان اجرای اشتراسن

از آنجا که هر سطح بازگشت اکنون فقط نیازمند ۷ ضرب بازگشتی از زیرماتریس‌های نصف‌اندازه است، به‌علاوه تعداد ثابتی جمع و تفریق Θ(n²)، رابطه بازگشتی این‌طور می‌شود:

T(n) = 7T(n/2) + Θ(n²)

حل این رابطه بازگشتی با استفاده از روش استاد T(n) = Θ(n^log₂7) ≈ Θ(n^2.807) می‌دهد، یک بهبود مجانبی واقعی نسبت به الگوریتم ساده Θ(n³). در حالی که بهبود از توان ۳ به تقریباً ۲.۸۰۷ ممکن است متوسط به‌نظر برسد، برای ماتریس‌های بسیار بزرگ معنادار می‌شود، و چیزی عمیقاً مهم را اثبات کرد: زمان مکعبی اساساً برای ضرب ماتریس مورد نیاز نیست، که در را برای دهه‌ها پژوهش بیشتر روی الگوریتم‌های حتی سریع‌تر باز کرد.

ملاحظات عملی

با وجود پیچیدگی مجانبی بهتر، الگوریتم اشتراسن به‌ندرت در عمل برای اندازه‌های معمول ماتریس استفاده می‌شود، به چند دلیل عملی. الگوریتم یک فاکتور ثابت بزرگ‌تری دارد که درون نمادگذاری مجانبی پنهان است، به این معنا که فقط وقتی ماتریس‌ها به‌اندازه کافی بزرگ شوند از الگوریتم ساده پیشی می‌گیرد. همچنین از نظر عددی کمتر پایدار از رویکرد ساده است، چون جمع و تفریق‌های اضافی می‌توانند خطاهای گرد کردن ممیز شناور را تشدید کنند. کتابخانه‌های عددی دنیای واقعی معمولاً از یک رویکرد ترکیبی استفاده می‌کنند: به‌کارگیری بازگشتی الگوریتم اشتراسن تا یک اندازه آستانه، سپس تغییر به الگوریتم ساده برای حالت پایه، تا بهره مجانبی را با کمینه کردن سربار و بی‌ثباتی عددی به دست آورد.

چرا این نتیجه فراتر از ضرب ماتریس اهمیت دارد

الگوریتم اشتراسن از نظر تاریخی بسیار فراتر از کاربرد عملی فوری‌اش اهمیت دارد. این یکی از اولین نتایجی بود که نشان داد الگوریتم ساده یک مسئله، هرچند شهودی، لزوماً از نظر مجانبی بهینه نیست، و کل یک زیرشاخه پژوهشی درباره ضرب ماتریس سریع را الهام بخشید که تا امروز ادامه دارد، با بهترین الگوریتم‌های شناخته‌شده فعلی که به توان‌هایی حتی کمتر از کران اصلی اشتراسن دست می‌یابند، هرچند با فاکتورهای ثابت به‌اندازه‌ای بزرگ که صرفاً از نظر تئوری جالب باقی می‌مانند.