الگوریتم ضرب دو ماتریس — به زبان ساده همراه با کد پایتون

در این مقاله درمورد الگوریتم ضرب دو ماتریس و مقایسه انواع الگوریتم‌های آن با یکدیگر صحبت خواهیم کرد. الگوریتم‌های مختلفی برای ضرب ماتریس‌ها وجود دارد که معروف‌ترین و پرکاربردترین الگوریتم ضرب ماتریس را می‌توان پس از الگوریتم کلاسیک (پیمایشی)، بدون شک الگوریتم استراسن (Strassen’s Algorithm) دانست. در ادامه این الگوریتم و دیگر الگوریتم‌ها را توضیح خواهیم داد پس با ما همراه باشید.

مقدمه

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

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

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

تعریف ضرب دو ماتریس

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

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

به‌عبارت دیگر، هر درایه در سطر i و ستون j از ماتریس حاصل، از مجموع حاصل‌ضرب عناصر متناظر سطر i از ماتریس اول و ستون j از ماتریس دوم به دست می‌آید.

شرایط امکان‌پذیری ضرب

برای اینکه ضرب دو ماتریس A و B (به‌ترتیب AB) تعریف‌شده و قابل محاسبه باشد، باید:

تعداد ستون‌های ماتریس اول (A)، برابر با تعداد سطرهای ماتریس دوم (B) باشد.

پس اگر داشته باشیم:

• A با ابعاد m×n
• B با ابعاد n×p

آنگاه ضرب AB امکان‌پذیر و نتیجه‌ی آن ماتریسی با ابعاد m×p خواهد بود.

مثال قابل ضرب:

A_۲*۳ و B_۳*۴ ⇒ AB_۲*۴

چون ۳=۳ (ستون‌های A = سطرهای B) → ضرب ممکن است.

مثال غیر قابل ضرب:

A_۲*۳ و B_۲*۲ ⇒ ضرب تعریف نمی‌شود

چون ۳ ≠ ۲ → شرط برقرار نیست → ضرب ناممکن است.

الگوریتم ضرب دو ماتریس

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

۱- الگوریتم پیمایشی (Iterative Algorithm)

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

اگرچه این روش از نظر مفهومی بسیار ساده و قابل فهم است، اما از نظر کارایی، به‌ویژه در پردازش‌های عددی با ماتریس‌های بزرگ، چندان بهینه نیست. پیچیدگی زمانی آن O(n^۳) است (در حالت ضرب دو ماتریس مربعی)، که برای بسیاری از مسائل با مقیاس بالا ناکارآمد محسوب می‌شود. با این حال، این الگوریتم هنوز به عنوان مبنای بسیاری از روش‌های آموزشی و حتی بعضی از کتابخانه‌های پایه‌ی ریاضی مورد استفاده قرار می‌گیرد. فرمول این الگوریتم به صورت زیر می‌باشد:

مراحل اجرای الگوریتم

1. یک ماتریس صفر با ابعاد مناسب (تعداد سطرهای ماتریس اول و تعداد ستون‌های ماتریس دوم) به‌عنوان ماتریس نتیجه تعریف می‌شود.
2. با استفاده از یک حلقه بیرونی، هر سطر از ماتریس اول انتخاب می‌شود.
3. برای هر سطر، یک حلقه‌ی میانی اجرا شده و در آن، هر ستون از ماتریس دوم بررسی می‌گردد.
4. در داخل این حلقه، با کمک یک حلقه‌ی داخلی سوم، درایه‌های متناظر از سطر و ستون انتخاب‌شده ضرب و جمع می‌شوند تا درایه‌ی مربوطه از ماتریس نهایی به‌دست آید.
5. این روند برای تمام سطرها و ستون‌ها تکرار شده و در نهایت ماتریس ضرب کامل می‌شود.

– فرض کنیم:

• A ماتریسی با ابعاد m×n
• B ماتریسی با ابعاد n×p
• ماتریس حاصل C با ابعاد m×p

الگوریتم به‌صورت زیر عمل می‌کند:

1. برای هر سطر i از A
2. برای هر ستون j از B
3. مقدار cij را با جمع حاصل‌ضرب a_ik​ ⋅ b_kj​ برای k=1 تا n محاسبه می‌کند.

مثال برای الگوریتم

فرض می‌کنیم دو ماتریس داریم:

• ماتریس A[2×۳]:

• ماتریس B[3×۲]:

ماتریس حاصل C[2×۲] خواهد بود.

• مرحله‌به‌مرحله محاسبه عناصر ماتریس C:

C[0] [0] = (1×۷)+(۲×۹)+(۳×۱۱) = 7+۱۸+۳۳ = 58

C[0] [1] = (1×۸)+(۲×۱۰)+(۳×۱۲) = 8+۲۰+۳۶ = 64

C[1] [0] = (4×۷)+(۵×۹)+(۶×۱۱) = 28+۴۵+۶۶ = 139

C[1] [1] = (4×۸)+(۵×۱۰)+(۶×۱۲) = 32+۵۰+۷۲ = 154

• ماتریس نهایی C:

پیاده سازی الگوریتم با زبان پایتون

def iterative_multiply(A, B):
    m = len(A)        # تعداد سطرهای A
    n = len(A[0])     # تعداد ستون‌های A (و سطرهای B)
    p = len(B[0])     # تعداد ستون‌های B

    # تعریف ماتریس حاصل C با مقداردهی اولیه صفر
    C = [[0 for _ in range(p)] for _ in range(m)]

    # سه حلقه‌ی تو در تو برای ضرب کلاسیک
    for i in range(m):
        for j in range(p):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]

    return C
A = [
    [۱, ۲, ۳],
    [۴, ۵, ۶]
]

B = [
    [۷, ۸],
    [۹, ۱۰],
    [۱۱, ۱۲]
]

result = iterative_multiply(A, B)
for row in result:
    print(row)

• خروجی:

[۵۸, ۶۴]
[۱۳۹, ۱۵۴]

۲- الگوریتم تقسیم و حل (Divide-and-Conquer Algorithm)

الگوریتم تقسیم و حل یکی از رویکردهای کلاسیک در طراحی الگوریتم‌هاست که در آن، یک مسئله به زیرمسئله‌های کوچک‌تر تقسیم می‌شود، سپس این زیرمسئله‌ها به‌طور جداگانه حل شده و نتایج آن‌ها با یکدیگر ترکیب می‌گردد تا پاسخ نهایی به دست آید. در زمینه‌ی ضرب ماتریس، این رویکرد به این صورت است که هر ماتریس به چهار زیرماتریس مساوی تقسیم می‌شود و سپس ضرب ماتریسی میان این زیرماتریس‌ها انجام می‌گیرد.

در این الگوریتم ضرب دو ماتریس در واقع، اگر دو ماتریس ورودی از مرتبه n×n باشند، آن‌ها به چهار قسمت \({n \over 2} \times {n \over 2}\) تقسیم می‌شوند و ضرب اصلی با انجام ۸ ضرب ماتریسی بر روی این زیرماتریس‌ها انجام می‌شود. این روش باعث می‌شود که ساختار بازگشتی و قابل تجزیه‌ای برای ضرب ماتریس ایجاد شود. پیچیدگی زمانی این الگوریتم همچنان O(n^۳) است، مشابه روش پیمایشی، اما زمینه‌ای برای طراحی الگوریتم‌های سریع‌تر (مانند الگوریتم استراسن) فراهم می‌سازد.

مراحل اجرای الگوریتم

فرض می‌شود دو ماتریس A و B از مرتبه‌ی n×n هستند. این دو ماتریس به چهار زیرماتریس مساوی تقسیم می‌شوند:

سپس ۸ ضرب ماتریسی بین این زیرماتریس‌ها انجام می‌گیرد و نتایج آن‌ها به‌شکل زیر ترکیب می‌شوند:

این فرآیند به‌صورت بازگشتی ادامه پیدا می‌کند تا به حالت پایه (ماتریس‌های ۱×۱) برسد، سپس ترکیب نهایی انجام می‌شود.

مثال برای الگوریتم

فرض می‌کنیم دو ماتریس داریم:

ماتریس A[2×۲]:

ماتریس B[2×۲]:

محاسبه مرحله به مرحله:

C_۱۱=(۱×۵)+(۲×۷)=۵+۱۴=۱۹

C_۱۲=(۱×۶)+(۲×۸)=۶+۱۶=۲۲

C_۲۱=(۳×۵)+(۴×۷)=۱۵+۲۸=۴۳

C_۲۲=(۳×۶)+(۴×۸)=۱۸+۳۲=۵۰

ماتریس نهایی C:

پیاده سازی الگوریتم با زبان پایتون

# جمع دو ماتریس
def add_matrix(X, Y):
    return [[X[i][j] + Y[i][j] for j in range(len(X))] for i in range(len(X))]

# تفریق دو ماتریس
def sub_matrix(X, Y):
    return [[X[i][j] - Y[i][j] for j in range(len(X))] for i in range(len(X))]

# تقسیم یک ماتریس n×n به چهار زیرماتریس n/2×n/2
def divide_matrix(A):
    n = len(A)
    mid = n // 2
    A11 = [row[:mid] for row in A[:mid]]     # زیرماتریس بالا-چپ
    A12 = [row[mid:] for row in A[:mid]]     # بالا-راست
    A21 = [row[:mid] for row in A[mid:]]     # پایین-چپ
    A22 = [row[mid:] for row in A[mid:]]     # پایین-راست
    return A11, A12, A21, A22

# ترکیب چهار زیرماتریس به یک ماتریس کامل
def combine_matrix(C11, C12, C21, C22):
    top = [a + b for a, b in zip(C11, C12)]        # ترکیب ردیف‌های بالا
    bottom = [a + b for a, b in zip(C21, C22)]     # ترکیب ردیف‌های پایین
    return top + bottom                            # ترکیب بالا و پایین

# الگوریتم تقسیم و حل برای ضرب دو ماتریس مربعی
def divide_and_conquer_multiply(A, B):
    n = len(A)

    # حالت پایه: اگر ماتریس فقط یک درایه داشت
    if n == 1:
        return [[A[0][0] * B[0][0]]]

    # تقسیم ماتریس‌ها به چهار بخش
    A11, A12, A21, A22 = divide_matrix(A)
    B11, B12, B21, B22 = divide_matrix(B)

    # محاسبه بلوک‌های ماتریس حاصل با استفاده از ضرب بازگشتی
    C11 = add_matrix(
        divide_and_conquer_multiply(A11, B11),
        divide_and_conquer_multiply(A12, B21)
    )

    C12 = add_matrix(
        divide_and_conquer_multiply(A11, B12),
        divide_and_conquer_multiply(A12, B22)
    )

    C21 = add_matrix(
        divide_and_conquer_multiply(A21, B11),
        divide_and_conquer_multiply(A22, B21)
    )

    C22 = add_matrix(
        divide_and_conquer_multiply(A21, B12),
        divide_and_conquer_multiply(A22, B22)
    )

    # ترکیب چهار بلوک برای ساختن ماتریس نهایی
    return combine_matrix(C11, C12, C21, C22)
# تعریف دو ماتریس ۲×۲
A = [
    [۱, ۲],
    [۳, ۴]
]

B = [
    [۵, ۶],
    [۷, ۸]
]

# اجرای ضرب با الگوریتم تقسیم و حل
C = divide_and_conquer_multiply(A, B)

# چاپ خروجی
for row in C:
    print(row)

• خروجی:

[۱۹, ۲۲]
[۴۳, ۵۰]

۳- الگوریتم استراسن (Strassen’s Algorithm)

الگوریتم استراسن یکی از سریع‌ترین الگوریتم‌ها در ضرب ماتریس است که در سال ۱۹۶۹ توسط ولکر استراسن ارائه شد. این الگوریتم با کاهش تعداد ضرب‌های مورد نیاز در الگوریتم بازگشتی (مشابه Divide-and-Conquer)، توانست پیچیدگی زمانی ضرب دو ماتریس را از O(n^۳) به حدود O(n^۲.۸۱) کاهش دهد. روش استراسن بر پایه‌ی ایده‌ی تقسیم ماتریس‌ها به چهار زیرماتریس مساوی و سپس انجام فقط ۷ ضرب ماتریسی (به‌جای ۸ عدد در روش تقسیم‌وحل معمولی) استوار است. این کاهش، علی‌رغم افزایش تعداد عملیات جمع و تفریق، در نهایت باعث صرفه‌جویی در زمان اجرای کلی می‌شود.

استراسن برخلاف الگوریتم ساده که فقط به دنبال محاسبه مستقیم است، از یک ترکیب هوشمندانه از جمع و تفریق زیرماتریس‌ها بهره می‌برد تا ضرب‌های کمتری انجام دهد. این الگوریتم ضرب دو ماتریس پایه‌گذار نسل جدیدی از روش‌های سریع‌تر شد که بعدها در الگوریتم‌هایی مانند Coppersmith–Winograd و نسخه‌های مدرن‌تر توسعه پیدا کردند. با اینکه در برخی کاربردهای عملی مانند پردازش ماتریس‌های بسیار بزرگ یا پردازش گرافیکی استفاده می‌شود، اما در ماتریس‌های کوچک یا سیستم‌هایی با منابع محدود ممکن است سربار اضافی تولید کند.

مراحل اجرای الگوریتم

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

۴- الگوریتم وینوگراد (Winograd’s Algorithm)

الگوریتم وینوگراد یکی از الگوریتم‌های کلاسیک در زمینه ضرب ماتریس‌هاست که هدف آن کاهش تعداد ضرب‌های لازم نسبت به روش معمول پیمایشی است. این الگوریتم با بهره‌گیری از روش‌های هوشمندانه‌ای برای پیش‌محاسبه (preprocessing) و استفاده مجدد از نتایج میانی، تعداد عملیات ضرب را کاهش داده و در عوض از جمع و تفریق بیشتری استفاده می‌کند. در نتیجه، اجرای آن روی سیستم‌هایی که عملیات ضرب در آن‌ها نسبت به جمع هزینه‌برتر است، می‌تواند عملکرد بهتری نسبت به الگوریتم پیمایشی ساده داشته باشد.

این الگوریتم ضرب دو ماتریس بیشتر برای ضرب ماتریس‌های مستطیلی مورد استفاده قرار می‌گیرد، و مناسب پردازش‌هایی است که منابع ضرب (مثل سخت‌افزار یا زمان) محدودتر هستند.

این الگوریتم می‌تواند دو ماتریس n×n را در زمان O(n^۲.۳۷۲۷) در هم ضرب کند. این الگوریتم در عمل، موجب کاهش محسوس در تعداد ضرب‌ها و باعث بهبود سرعت اجرا می‌شود، به‌ویژه در ماتریس‌هایی با ابعاد خاص یا داده‌های عدد صحیح. نسخه‌های بهینه‌شده‌ی الگوریتم وینوگراد در بسیاری از کتابخانه‌های ریاضیاتی و گرافیکی مدرن نیز استفاده شده‌اند.

مراحل اجرای الگوریتم

1. مرحله‌ی آماده‌سازی (پیش‌محاسبه): برای صرفه‌جویی در تعداد ضرب‌ها، ابتدا برای هر سطر از ماتریس اول (A) و هر ستون از ماتریس دوم (B) چند مقدار کمکی محاسبه می‌کنیم. این مرحله باعث می‌شود در ادامه، عملیات ضرب کمتری انجام دهیم.
2. محاسبه‌ی درایه‌های ماتریس حاصل (C): حالا به‌جای اینکه مستقیم هر درایه‌ی ماتریس خروجی رو با ضرب کل یک سطر در کل یک ستون به دست بیاریم، از اطلاعات مرحله‌ی قبل کمک می‌گیریم و تعداد زیادی از ضرب‌ها رو با جمع و تفریق جایگزین می‌کنیم.
3. رسیدگی به حالت خاص (اگر تعداد ستون‌های A فرد باشد): در صورتی که تعداد ستون‌های ماتریس اول (یا به‌عبارت دیگر، تعداد ردیف‌های ماتریس دوم) فرد باشد، یک ضرب کوچک اضافی در انتهای کار انجام می‌دهیم تا دقت نتیجه حفظ شود.

– فرض کنیم برای دو ماتریس A[m×n] و B[n×p]:

پیش‌محاسبه‌ی جمع‌های سطری و ستونی، برای هر سطر i از ماتریس A:

برای هر ستون j از ماتریس B:

محاسبه‌ی درایه‌های ماتریس حاصل C[m×p] با استفاده از فرمول:

اگر n فرد باشد، باید مؤلفه‌ی نهایی به صورت جداگانه محاسبه شود:

مثال برای الگوریتم

فرض می‌کنیم دو ماتریس داریم:

ماتریس A[2×۳]:

ماتریس B[3×۲]:

ماتریس حاصل C[2×۲] خواهد بود.

• مرحله ۱: پیش‌محاسبه برای سطرهای A

ما ستون‌ها را جفت‌جفت در نظر می‌گیریم: (ستون ۰ و ۱)، چون ۳ ستون داریم، فقط یک جفت داریم (ستون ۲ بدون جفت است):

• مرحله ۲: پیش‌محاسبه برای ستون‌های B

در اینجا ردیف‌ها را جفت‌جفت می‌گیریم: (ردیف ۰ و ۱)، ردیف ۲ بدون جفت باقی می‌ماند.

• مرحله ۳: محاسبه درایه‌های ماتریس C

الگوریتم وینوگراد برای کاهش ضرب‌ها، از پیش‌محاسبه‌هایی استفاده می‌کند. برای هر عنصر C[i] [j]، از فرمول زیر استفاده می‌کنیم:

برای i=0, j=0:

C[0] [0] = −۲−۶۳+(۱+۹)(۲+۷)+۳×۱۱ = −۶۵+(۱۰×۹)+۳۳ = −۶۵+۹۰+۳۳ = 58

برای i=0, j=1:

C[0] [1] = −۲−۸۰+(۱+۱۰)(۲+۸)+۳×۱۲ = −۸۲+(۱۱×۱۰)+۳۶ = −۸۲+۱۱۰+۳۶ = 64

برای i=1, j=0:

C[1] [0] = −۲۰−۶۳+(۴+۹)(۵+۷)+۶×۱۱ = −۸۳+(۱۳×۱۲)+۶۶ = −۸۳+۱۵۶+۶۶ = 139

برای i=1, j=1:

C[1] [1] = −۲۰−۸۰+(۴+۱۰)(۵+۸)+۶×۱۲ = −۱۰۰+(۱۴×۱۳)+۷۲ = −۱۰۰+۱۸۲+۷۲ = 154

• ماتریس نهایی C:

پیاده سازی الگوریتم با زبان پایتون

def winograd_multiply(A, B):
    m = len(A)          # تعداد سطرهای A
    n = len(A[0])       # تعداد ستون‌های A (و سطرهای B)
    p = len(B[0])       # تعداد ستون‌های B

    # مرحله ۱: محاسبه rowFactors برای هر سطر A
    row_factor = [0] * m
    for i in range(m):
        for k in range(0, n // 2):
            row_factor[i] += A[i][2 * k] * A[i][2 * k + 1]

    # مرحله ۲: محاسبه colFactors برای هر ستون B
    col_factor = [0] * p
    for j in range(p):
        for k in range(0, n // 2):
            col_factor[j] += B[2 * k][j] * B[2 * k + 1][j]

    # مرحله ۳: محاسبه درایه‌های ماتریس حاصل
    C = [[0 for _ in range(p)] for _ in range(m)]
    for i in range(m):
        for j in range(p):
            C[i][j] = -row_factor[i] - col_factor[j]
            for k in range(0, n // 2):
                C[i][j] += (A[i][2 * k] + B[2 * k + 1][j]) * (A[i][2 * k + 1] + B[2 * k][j])

    # مرحله ۴: اگر n فرد باشد، درایه آخر را جداگانه محاسبه کن
    if n % 2 == 1:
        for i in range(m):
            for j in range(p):
                C[i][j] += A[i][n - 1] * B[n - 1][j]

    return C
A = [
    [۱, ۲, ۳],
    [۴, ۵, ۶]
]

B = [
    [۷, ۸],
    [۹, ۱۰],
    [۱۱, ۱۲]
]

C = winograd_multiply(A, B)

for row in C:
    print(row)

• خروجی:

[۵۸, ۶۴]
[۱۳۹, ۱۵۴]

مقایسه ۴ الگوریتم ضرب دو ماتریس

1. الگوریتم پیمایشی ساده‌ترین روش است، ولی برای ماتریس‌های بزرگ کند عمل می‌کند.
2. الگوریتم تقسیم‌وحل با بازگشت و تقسیم به زیرمسئله‌ها، ساختار الگوریتم را بهینه‌تر می‌کند، ولی پیچیدگی زمانی را کاهش نمی‌دهد.
3. الگوریتم استراسن با حذف یک ضرب ماتریسی در هر سطح بازگشت، پیچیدگی زمانی را کاهش داده و برای ماتریس‌های بزرگ بسیار مناسب است.
4. الگوریتم وینوگراد با پیش‌محاسبه و استفاده از جمع و تفریق، تعداد ضرب‌ها را کاهش می‌دهد و برای برخی کاربردها سریع‌تر از روش کلاسیک است.

نتیجه گیری

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

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