ضرب ماتریس‌های خلوت

هر سطر را فقط با جمله‌های ناصفرش نگه می‌دارد و فقط ضرب‌های ناصفر را انجام می‌دهد؛ برای ماتریس‌های خلوت خیلی کمتر از n³ ضرب.

در ماتریس خلوت بیشتر ضرب‌های A[i][k]·B[k][j] صفرند و انجامشان بی‌فایده است. اگر هر سطر را فقط با جمله‌های ناصفرش نگه داریم:

ادامه‌ی توضیح ↓

زمان: O(rows + the number of non-zero products)
حافظه: O(non-zeros)
هوروویتز–ساهنی، فصل ۲

ورودی:

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

دو ماتریس ۴×۴ که بیشتر خانه‌هایشان صفر است؛ به‌جای ۶۴ ضرب فقط ۵ ضرب لازم است.

def sparse_multiply(A, B):
if len(A[0]) != len(B):
return None
# Row lists: for each row, only its non-zero (column, value) pairs.
a_rows = [[(j, v) for j, v in enumerate(row) if v != 0] for row in A]
b_rows = [[(j, v) for j, v in enumerate(row) if v != 0] for row in B]
C = []
products = 0
for i in range(len(A)):
acc = {}
for k, a in a_rows[i]:
for j, b in b_rows[k]:
acc[j] = acc.get(j, 0) + a * b
products = products + 1
C.append(sorted((j, v) for j, v in acc.items() if v != 0))
return products

ناوردا: هر ضرب انجام‌شده دو جمله‌ی ناصفر را ضرب می‌کند و A[i][k]·B[k][j] فقط به خانه‌ی (i, j) حاصل اضافه می‌شود.

شروع اجرا

products—

a_rows

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

b_rows

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

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

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

`A` list

[1, 0, 0, 2][0, 0, 3, 0][0, 0, 0, 0][4, 0, 0, 0]

`B` list

[0, 5, 0, 0][0, 0, 0, 0][6, 0, 0, 7][0, 0, 8, 0]

Call stack

sparse_multiply()خط 1

گام ۱ از ۴۷

توضیح

ایده

برای سطر i از A، هر جمله‌ی ناصفر A[i][k] را در جمله‌های ناصفر سطر k از B ضرب کن و در acc[j] جمع کن.
acc سطر i حاصل است؛ صفرها کنار گذاشته می‌شوند.

هزینه

تعداد ضرب‌ها دقیقاً تعداد جفت‌های ناصفر (A[i][k], B[k][j]) است، که برای ماتریس‌های خلوت خیلی کمتر از n³ است. کتاب هوروویتز همین کار را روی سه‌تایی‌ها و با ترانهاده‌ی B انجام می‌دهد؛ ایده یکی است.

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

جدول‌های a_rows و b_rows فهرست جمله‌های ناصفر هر سطرند و C حاصل به همان شکل. products تعداد ضرب‌های انجام‌شده است.