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

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

ضرب ماتریس ها چیست؟

در سال ۱۸۵۸، آرتور کیلی، ریاضی‌دان انگلیسی، اولین بار مفهوم ماتریس‌ها و عملیات روی آن‌ها، از جمله ضرب ماتریس‌ها، را در مقاله‌ای ارائه کرد. او از این ابزار برای مطالعه تبدیلات خطی و معادلات دیفرانسیل استفاده کرد. جیمز جوزف سیلوستر، یکی دیگر از ریاضی‌دانان بزرگ قرن نوزدهم، به‌طور گسترده‌ای روی ماتریس‌ها و خصوصیات آن‌ها کار کرد و کاربردهای عملی ضرب ماتریس‌ها را در فیزیک و جبر خطی بررسی کرد.

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

به عبارت دیگر، اگر ماتریس A ابعاد m*n داشته باشد و ماتریس B ابعاد n*p داشته باشد، آنگاه حاصل ضرب این دو ماتریس C=A*B یک ماتریس C با ابعاد m*p خواهد بود.

به طور ساده‌تر، می‌توان ضرب ماتریس‌ها را به صورت یک عملیات ترکیب خطی در نظر گرفت که وزن‌های (ضریب‌های) هر عنصر در ماتریس اول توسط مقادیر ماتریس دوم تعیین می‌شود. این عملیات کاربردهای گسترده‌ای در علوم مختلف دارد، از جمله در گرافیک کامپیوتری، یادگیری ماشینی، و حل معادلات خطی. ضرب ماتریس‌ها با جمع و ضرب معمولی تفاوت دارد و ترتیب آن‌ها مهم است؛ یعنی A*B معمولاً با B*A برابر نیست.

مثال ساده برای ضرب ماتریس

اگر ۲ ماتریس A و B به صورت زیر داشته باشیم:

حال ابتدا باید بررسی کنیم که تعداد سطرهای ماتریس اول و تعداد ستون‌های آن برابر با تعداد ستون‌های ماتریس دوم باشد. حال می‌بینیم که این ماتریس یک ماتریس ۲ * ۲ است. هر عنصر از ماتریس C (ماتریس پاسخ نهایی) را به ترتیب زیر محاسبه می‌کنیم.

ماتریس بالا سمت چپ : حاصل ضرب سطر اول A و ستون اول B خواهد بود.

(۱*۵) + (۲*۷) = 5+۱۴ = 19

ماتریس بالا سمت راست: حاصل ضرب سطر اول A و ستون دوم B خواهد بود.

(۱*۶) + (۲*۸) = 6+۱۶ = 22

ماتریس پایین سمت چپ: حاصل ضرب سطر دوم A و ستون اول B خواهد بود.

(۳*۵) + (۴*۷) = 15+۲۸ = 43

ماتریس پایین سمت راست: حاصل ضرب سطر دوم A و ستون دوم B خواهد بود.

(۳*۶) + (۴*۸) = 18+۳۲ = 50

حاصل ماتریس C به صورت زیر خواهد بود.

اشکال ضرب ماتریس ها

روش سنتی یا کلاسیک ضرب ماتریس‌ها، بر اساس جمع ضرب‌های اسکالر میان سطرهای ماتریس اول و ستون‌های ماتریس دوم است. اما این روش اشکال‌هایی دارد مانند:

پیچیدگی محاسباتی

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

نیاز به حافظه و ذخیره‌سازی

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

عدم بهره‌وری از پردازش موازی

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

الگوریتم ضرب استراسن چیست؟

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

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

در سال ۱۹۶۹، ولکر استراسن، ریاضی‌دان آلمانی، الگوریتمی را ارائه کرد که تعداد عملیات مورد نیاز برای ضرب دو ماتریس را به طور چشمگیری کاهش داد. او با استفاده از روش تقسیم و غلبه، نشان داد که می‌توان پیچیدگی زمانی ضرب ماتریس‌ها را از O(n^۳) به O(n^log_۲۷) کاهش داد، که تقریباً برابر با O(n^۲.۸۱) است. این بهبود با استفاده از شکستن بازگشتی مسئله ضرب ماتریس به زیرمسائل کوچکتر و ترکیب نتایج آنها به دست می‌آید. این پیشرفت نقطه عطفی در تاریخ ضرب ماتریس‌ها بود و الهام‌بخش الگوریتم‌های سریع‌تر بعدی شد.

نحوه عملکرد الگوریتم ضرب استراسن

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

گام اول: تقسیم ماتریس‌ها به زیرماتریس‌ها

فرض کنید دو ماتریس داریم به اسم‌های A و B که اندازه آن‌ها n*n است. حالا این ماتریس‌ها رو به چهار بخش مساوی تقسیم می‌کنیم. برای این کار، ماتریس A را به چهار زیرماتریس تقسیم می‌کنیم که به این صورت می‌شود:

در اینجا، A_۱۱ و A_۱۲ و A_۲۱ و A_۲۲ هرکدام یک ماتریس \({n \over 2} \times {n \over 2}\) هستند. همین کار را برای ماتریس B نیز انجام می‌دهیم.

گام دوم: محاسبه ۷ ضرب اصلی

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

P_۱ = A_۱۱ * (B_۱۲ – B_۲۲)

P_۲ = (A_۱۱ + A_۱۲) * B_۲۲

P_۳ = (A_۲۱ + A_۲۲) * B_۱۱

P_۴ = A_۲۲ * (B_۲۱ – B_۱۱)

P_۵ = (A_۱۱ + A_۲۲) * (B_۱۱ + B_۲۲)

P_۶ = (A_۱۲ – A_۲۲) * (B_۲۱ + B_۲۲)

P_۷ = (A_۱۱ – A_۲۱) * (B_۱۱ + B_۱۲)

گام سوم: ترکیب نتایج برای ساخت ماتریس نهایی

پس از محاسبه ۷ ضرب، باید نتایج رو ترکیب کنیم تا به ماتریس نهایی برسیم. ماتریس نهایی C=A*B به صورت زیر خواهد بود:

هر بخش از ماتریس C را به صورت زیر محاسبه می‌کنیم:

C_۱۱ = P_۵ + P_۴ – P_۲ + P_۶

C_۱۲ = P_۱ + P_۲

C_۲۱ = P_۳ + P_۴

C_۲۲ = P_۵ + P_۱ – P_۳ – P_۷

با این روش می‌توان هر ماتریسی را به روش استراسن محاسبه کرد. چه ماتریس‌های بزرگ چه کوچک همگی از این فرمول استفاده می‌کنند.

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

همانطور که دانستیم، الگوریتم ضرب استراسن به جای استفاده از روش کلاسیک ضرب ماتریس، از تکنیک تقسیم و غلبه (Divide and Conquer) استفاده می‌کند. در این الگوریتم، ماتریس‌ها به زیرماتریس‌های کوچکتری تقسیم می‌شوند و سپس ضرب‌ها بر روی این زیرماتریس‌ها انجام می‌شود.

این تقسیم و غلبه به‌طور بازگشتی ادامه می‌یابد تا به ماتریس‌های ۱*۱ برسیم. بنابراین، پیچیدگی زمانی الگوریتم استراسن به‌طور بازگشتی محاسبه می‌شود. فرض کنید پیچیدگی زمان برای ضرب دو ماتریس از اندازه n×n را T(n) بنامیم. در این صورت:

T(n) = 7 T(n/2) + O(n^۲)

در این معادله:

• 7T(n/2) مربوط به ۷ ضربی است که در هر مرحله انجام می‌شود.
• O(n^۲) مربوط به عملیات جمع و تفریق ماتریس‌ها است که در هر مرحله انجام می‌شود.

برای حل این معادله از روش‌های تحلیل معادلات بازگشتی (مثل روش استفاده از قاعده تبدیل) می‌توان استفاده کرد. در نهایت، پیچیدگی زمانی الگوریتم استراسن به‌صورت زیر به دست می‌آید:

T(n) = O(n^log_۲۷) ≈ O(n^۲.۸۱)

این به این معناست که پیچیدگی زمانی الگوریتم استراسن به‌طور اساسی از O(n^۳) در روش کلاسیک به O(n^۲.۸۱) کاهش می‌یابد و سرعت عملیات افزایش می‌یابد.

مثال برای الگوریتم ضرب استراسن ۲*۲

برای فهم بهتر الگوریتم ضرب استراسن، یک مثال عددی ساده می‌زنیم. می‌توانید روش حل این الگوریتم و نتیجه آن را با ضرب ماتریس ساده که در بالا توضیح دادیم مقایسه کنید. اگر ۲ ماتریس A و B به صورت زیر داشته باشیم:

گام اول: تقسیم ماتریس‌ها به زیرماتریس‌ها

هر دو ماتریس را به چهار زیرماتریس تقسیم می‌کنیم. از آنجایی که هر دو ماتریس ۲*۲ هستند، هر کدام به‌طور مستقیم به زیرماتریس‌های ۱*۱ تقسیم می‌شوند. در این مثال، برای ماتریس‌ها، زیرماتریس‌ها به این صورت خواهند بود:

که در اینجا چون ماتریس خود ۲*۲ است نیازی به تقسیم کردن به زیرماتریس نداریم. همچنین ماتریس B را داریم:

گام دوم: محاسبه ۷ ضرب اصلی

در این مرحله، طبق فرمول بالا باید ۷ ضرب اصلی را محاسبه کنیم که به صورت زیر خواهد بود:

P_۱ = A_۱۱ * (B_۱۲ – B_۲۲) = 1 * (۶ – ۸) = 1 * (-۲) = -۲

P_۲ = (A_۱۱ + A_۱۲) * B_۲۲ = (۱ + ۲) * ۸ = 3 * ۸ = 24

P_۳ = (A_۲۱ + A_۲۲) * B_۱۱ = (۳ + ۴) * ۵ = 7 * ۵ = 35

P_۴ = A_۲۲ * (B_۲۱ – B_۱۱) = 4 * (۷ – ۵) = 4 * ۲ = 8

P_۵ = (A_۱۱ + A_۲۲) * (B_۱۱ + B_۲۲) = (۱ + ۴) * (۵ + ۸) = 5 * ۱۳ = 65

P_۶ = (A_۱۲ – A_۲۲) * (B_۲۱ + B_۲۲) = (۲ – ۴) * (۷ + ۸) = (-۲) * ۱۵ = -۳۰

P_۷ = (A_۱۱ – A_۲۱) * (B_۱۱ + B_۱۲) = (۱ – ۳) * (۵ + ۶) = (-۲) * ۱۱ = -۲۲

گام سوم: ترکیب نتایج برای ساخت ماتریس نهایی

حالا که نتایج ۷ ضرب اصلی را به دست آورده‌ایم، طبق فرمول بالا نتایج را ترکیب می‌کنیم تا ماتریس نهایی به دست آید؛ که به صورت زیر خواهد بود:

C_۱۱ = P_۵ + P_۴ – P_۲ + P_۶ = 65 + ۸ – ۲۴ + (-۳۰) = 19

C_۱۲ = P_۱ + P_۲ = -۲ + ۲۴ = 22

C_۲۱ = P_۳ + P_۴ = 35 + ۸ = 43

C_۲۲ = P_۵ + P_۱ – P_۳ – P_۷ = 65 + (-۲) – ۳۵ – (-۲۲) = 50

حاصل ماتریس C به صورت زیر خواهد بود.

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

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

در زیر کد الگوریتم به زبان پایتون قرار داده شده است؛ می‌توانید کد را برای هر ماتریسی ویرایش کنید. در این کد یک ماتریس ۴*۴ به عنوان مثال آورده شده است.

import numpy as np

def add_matrices(A, B):
    #Add two matrices.
    return A + B

def subtract_matrices(A, B):
    #Subtract matrix B from matrix A.
    return A - B

def strassen(A, B):
    
    #Perform Strassen matrix multiplication on two matrices A and B.
    #A and B must be square matrices with dimensions that are powers of 2.
    #Base case: 1x1 matrix
    if A.shape[0] == 1:
        return A * B

    #Divide matrices into quadrants
    n = A.shape[0] // 2

    A11, A12, A21, A22 = A[:n, :n], A[:n, n:], A[n:, :n], A[n:, n:]
    B11, B12, B21, B22 = B[:n, :n], B[:n, n:], B[n:, :n], B[n:, n:]

    #Calculate the 7 products (P1 to P7)
    P1 = strassen(add_matrices(A11, A22), add_matrices(B11, B22))
    P2 = strassen(add_matrices(A21, A22), B11)
    P3 = strassen(A11, subtract_matrices(B12, B22))
    P4 = strassen(A22, subtract_matrices(B21, B11))
    P5 = strassen(add_matrices(A11, A12), B22)
    P6 = strassen(subtract_matrices(A21, A11), add_matrices(B11, B12))
    P7 = strassen(subtract_matrices(A12, A22), add_matrices(B21, B22))

    #Combine results into the resulting matrix
    C11 = P1 + P4 - P5 + P7
    C12 = P3 + P5
    C21 = P2 + P4
    C22 = P1 - P2 + P3 + P6

    #Combine quadrants into one matrix
    C = np.vstack([
        np.hstack([C11, C12]),
        np.hstack([C21, C22])
    ])

    return C

def pad_matrix(A, size):
    #Pad a matrix to the desired size with zeros.
    padded = np.zeros((size, size))
    padded[:A.shape[0], :A.shape[1]] = A
    return padded

def strassen_with_padding(A, B):

    #Perform Strassen matrix multiplication on matrices A and B of arbitrary size.
    #Pads matrices to the nearest power of 2.
    # Find the nearest power of 2
    max_dim = max(A.shape[0], A.shape[1], B.shape[0], B.shape[1])
    next_power_of_2 = 2 ** int(np.ceil(np.log2(max_dim)))

    # Pad matrices to the nearest power of 2
    A_padded = pad_matrix(A, next_power_of_2)
    B_padded = pad_matrix(B, next_power_of_2)

    # Perform Strassen multiplication
    C_padded = strassen(A_padded, B_padded)

    # Remove padding and return result
    return C_padded[:A.shape[0], :B.shape[1]]

# Example Usage
if __name__ == "__main__":
    A = np.array([[1, 2, 3, 4],
                  [۵, ۶, ۷, ۸],
                  [۹, ۱۰, ۱۱, ۱۲],
                  [۱۳, ۱۴, ۱۵, ۱۶]])

    B = np.array([[17, 18, 19, 20],
                  [۲۱, ۲۲, ۲۳, ۲۴],
                  [۲۵, ۲۶, ۲۷, ۲۸],
                  [۲۹, ۳۰, ۳۱, ۳۲]])

    result = strassen_with_padding(A, B)
    print("Result of Strassen Multiplication:")
    print(result)

نتیجه این کد به صورت زیر خواهد بود.

array([[ 250.,  260.,  270.,  280.],
       [ ۶۱۸.,  ۶۴۴.,  ۶۷۰.,  ۶۹۶.],
       [ ۹۸۶., ۱۰۲۸., ۱۰۷۰., ۱۱۱۲.],
       [۱۳۵۴., ۱۴۱۲., ۱۴۷۰., ۱۵۲۸.]])

• تعریف توابع پایه:

کد الگوریتم ضرب استراسن با تعریف توابع پایه برای عملیات ماتریسی شروع می‌کند. توابع add_matrices و subtract_matrices به ترتیب برای جمع و تفریق ماتریس‌ها استفاده می‌شوند. سپس، تابع اصلی strassen برای ضرب ماتریس‌ها با استفاده از الگوریتم Strassen تعریف شده است. این الگوریتم ماتریس‌ها را به زیرماتریس‌های کوچکتر تقسیم می‌کند و عملیات روی آن‌ها را در چند مرحله انجام می‌دهد. اگر ماتریس به اندازه ۱*۱ برسد (مورد پایه)، مقدار ضرب به صورت مستقیم محاسبه می‌شود.

• تقسیم ماتریس‌ها به چهار قسمت:

در تابع strassen، ماتریس‌ها به چهار زیرماتریس (ربع ماتریس‌ها) تقسیم می‌شوند:

• A_۱۱ , A_۱۲ , A_۲۱ , A_۲۲
• B_۱۱ , B_۱۲ , B_۲۱ , B_۲۲

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

• ترکیب نتایج برای ماتریس نهایی:

نتایج P_۱ تا P_۷ برای محاسبه چهار بخش ماتریس نتیجه C_۱۱ , C_۱۲ , C_۲۱ , C_۲۲ ترکیب می‌شوند. این بخش‌ها مجدداً به یک ماتریس C با استفاده از عملیات ترکیب (vstack و hstack) کنار هم قرار می‌گیرند. این روش ساختار بازگشتی الگوریتم Strassen را حفظ می‌کند و زمان محاسبه را نسبت به روش‌های استاندارد کاهش می‌دهد.

• پردازش ماتریس‌ها با اندازه دلخواه:

از آنجایی که الگوریتم Strassen تنها برای ماتریس‌هایی با ابعاد توان ۲ قابل استفاده است، تابع pad_matrix ماتریس‌ها را با افزودن صفرها به ابعاد مناسب گسترش می‌دهد. تابع strassen_with_padding این کار را انجام داده و سپس ضرب را انجام می‌دهد و در نهایت مقادیر اضافه‌شده (ناشی از padding) را حذف می‌کند تا نتیجه‌ای متناسب با ابعاد اصلی ماتریس‌ها برگرداند. در پایان، مثالی از استفاده از این الگوریتم نشان داده شده که دو ماتریس ۴*۴ را ضرب کرده و نتیجه را چاپ می‌کند.

نتیجه گیری

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