AlgoVerse

ضرب ماتریس‌ها

ماتریس n×m را در m×p ضرب می‌کند: هر خانه‌ی حاصل، ضرب داخلی یک سطر از A و یک ستون از B است.

اگر A ماتریس n×m و B ماتریس m×p باشد، حاصل‌ضرب C = A·B ماتریس n×p است و

ادامه‌ی توضیح ↓
ورودی:
A 2×3 · B 3×2خروجی PDF

A دو در سه و B سه در دو؛ حاصل دو در دو است و هر خانه جمع سه ضرب.

  1. def matrix_multiply(A, B):
  2. n, m, p = len(A), len(B), len(B[0])
  3. if len(A[0]) != m:
  4. return None
  5. C = [[0] * p for _ in range(n)]
  6. for i in range(n):
  7. for j in range(p):
  8. total = 0
  9. for k in range(m):
  10. total = total + A[i][k] * B[k][j]
  11. C[i][j] = total
  12. return C

ناوردا: خانه‌های C که تا اینجا پر شده‌اند همه درست‌اند و هر خانه فقط به یک سطر A و یک ستون B بستگی دارد.

شروع اجرا

i—
j—
total—

A

123
456

B

78
910
1112

C

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

متغیرهای محلی

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

A list

[1, 2, 3][4, 5, 6]

B list

[7, 8][9, 10][11, 12]

Call stack

  1. matrix_multiply()خط 1
گام ۱ از ۵۰
خط سیاه = cell · خط نارنجی = گام کلیدیadd: 0/12 · cell: 0/4
    توضیح

    ایده

    اگر A ماتریس n×m و B ماتریس m×p باشد، حاصل‌ضرب C = A·B ماتریس n×p است و

    C[i][j] = Σ A[i][k] · B[k][j]   برای k = 1 … m

    یعنی ضرب داخلی سطر i از A و ستون j از B. تعداد ستون‌های A باید با تعداد سطرهای B برابر باشد.

    هزینه

    برای هر خانه از n·p خانه، m ضرب: O(n·m·p)؛ برای ماتریس‌های مربعی O(n³). روش اشتراسن با ۷ ضرب به‌جای ۸ در هر تقسیم به O(n^2.81) می‌رسد.

    نکته‌ها

    • ضرب ماتریس جابه‌جایی‌پذیر نیست: معمولاً A·B ≠ B·A.
    • ترتیب ضرب چند ماتریس هزینه را عوض می‌کند (صفحه‌ی «ضرب زنجیره‌ای ماتریس‌ها»).

    در trace به چه چیزی نگاه کنی

    • سه جدول کنار هم‌اند؛ برای هر خانه‌ی C ببین کدام سطر A و ستون B خوانده می‌شود.