خوارزمية ضرب المصفوفات

نظرًا لأن ضرب المصفوفات عملية أساسية في العديد من الخوارزميات العددية ، فقد بُذلت جهود كبيرة لتحسين كفاءة خوارزميات ضرب المصفوفات . تُستخدم هذه العملية في العديد من المجالات، بما في ذلك الحوسبة العلمية والتعرف على الأنماط ، وحتى في مسائل تبدو غير ذات صلة ، مثل حساب المسارات عبر رسم بياني . ^{[ 1 ]} وقد صُممت العديد من الخوارزميات المختلفة لضرب المصفوفات على أنواع مختلفة من الأجهزة، بما في ذلك الأنظمة المتوازية والموزعة ، حيث يتم توزيع العمل الحسابي على معالجات متعددة (ربما عبر شبكة).

يُعطي تطبيق التعريف الرياضي المباشر لضرب المصفوفات خوارزمية تستغرق وقتًا من رتبة $n³$ عملية حقلية لضرب مصفوفتين $من الرتبة$ $n \times n$ على ذلك الحقل ( $Θ(n³)$ في ترميز Big O ). وقد عُرفت حدود تقاربية أفضل للوقت اللازم لضرب المصفوفات منذ خوارزمية ستراسن في ستينيات القرن الماضي $،$ لكن الوقت الأمثل (أي التعقيد الحسابي لضرب المصفوفات ) لا يزال مجهولًا. اعتبارًا من سبتمبر 2025 أفضل حدٍّ للتعقيد التقاربي لخوارزمية ضرب المصفوفات هو $O(n² 2.371339)$ ، كما ورد في بحث ألمان، دوان، ويليامز ، شو، شو، وتشو. ^{[ 2 ]} مع ذلك، تُعدّ هذه الخوارزمية خوارزميةً معقدةً للغاية نظرًا لكبر الثوابت، ولا يُمكن تطبيقها عمليًا.

خوارزمية تكرارية

تعريف ضرب المصفوفات هو أنه إذا كانت $C = AB$ $لمصفوفة A$ من الرتبة $n \times m$ ومصفوفة $B$ من الرتبة $m$ $\times$ $p$ ، فإن $C$ هي مصفوفة من الرتبة $n$ $\times$ $p$ عناصرها

c_{ij}=\sum _{k=1}^{m}a_{ik}b_{kj}.

انطلاقاً من هذا، يمكن إنشاء خوارزمية بسيطة تقوم بالتكرار على المؤشرات $i$ من 1 إلى $n$ و $j$ من 1 إلى $p$ ، وحساب ما سبق باستخدام حلقة متداخلة:

المدخلات: المصفوفات $A$ و $B$
لتكن $C$ مصفوفة جديدة بالحجم المناسب
لكل i من 1 إلى n :
- لكل j من 1 إلى p :
  - لنفترض $أن المجموع = 0$
  - بالنسبة لـ k من 1 إلى m :
    - مجموعة $المجموع \leftarrow المجموع + أ ik \times ب kj$
  - Set $C ij \leftarrow sum$
إرجاع $C$

تستغرق هذه الخوارزمية زمنًا مقداره $Θ(nmp)$ ( بالترميز التقاربي ). ^{[ 1 ]} من التبسيطات الشائعة لأغراض تحليل الخوارزمية افتراض أن المدخلات جميعها مصفوفات مربعة من الحجم ⁿ $\times n ،$ وفي هذه الحالة يكون زمن التشغيل $Θ(n³)$ ، أي مكعبًا بالنسبة لحجم البُعد. ^[ $3$ ^]

سلوك ذاكرة التخزين المؤقت

يمكن تبديل الحلقات الثلاث في عملية ضرب المصفوفات التكرارية بشكل عشوائي دون التأثير على صحة العملية أو زمن التشغيل التقاربي. مع ذلك، قد يؤثر ترتيب الحلقات بشكل كبير على الأداء العملي نظرًا لأنماط الوصول إلى الذاكرة واستخدام ذاكرة التخزين المؤقت للخوارزمية؛ ^{[ 1 ]} كما يعتمد الترتيب الأمثل على ما إذا كانت المصفوفات مخزنة بترتيب الصفوف، أو ترتيب الأعمدة ، أو مزيج من الاثنين.

على وجه الخصوص، في الحالة المثالية لذاكرة تخزين مؤقتة ترابطية بالكامل تتكون من $M$ بايت و $b$ بايت لكل سطر (أي M / b سطر ) ، تكون الخوارزمية المذكورة أعلاه دون المستوى الأمثل للمصفوفتين $A$ و $B$ المخزنتين بترتيب الصفوف. عندما يكون $n > M / b ،$ فإن كل تكرار للحلقة الداخلية (مسح متزامن لصف من $A$ وعمود من $B ) يتسبب في خطأ في ذاكرة التخزين$ $المؤقتة$ عند الوصول إلى عنصر من $B.$ هذا يعني أن الخوارزمية تتسبب في $Θ(n³) من أخطاء ذاكرة التخزين المؤقتة$ في أسوأ الحالات. اعتبارًا من عام 2010^[⁴^] إن سرعة الذاكرة مقارنة بسرعة المعالجات تجعل أخطاء ذاكرة التخزين المؤقت، بدلاً من العمليات الحسابية الفعلية، هي التي تهيمن على وقت التشغيل للمصفوفات الكبيرة.

$إن النسخة المثلى من$ الخوارزمية التكرارية لـ $A$ و $B$ في تخطيط الصفوف الرئيسية هي نسخة مقسمة $إلى$ مربعات ، حيث يتم تقسيم المصفوفة ضمنيًا إلى مربعات بحجم $\sqrtM$ بواسطة $\sqrtM$ : ^[⁴^]^[⁵^]

المدخلات: المصفوفات $A$ و $B$
لتكن $C$ مصفوفة جديدة بالحجم المناسب
اختر حجم البلاطة $T = Θ(\sqrt M)$
بالنسبة لـ I من 1 إلى n بخطوات مقدارها T :
- بالنسبة لـ J من 1 إلى p بخطوات مقدارها T :
  - بالنسبة لـ K من 1 إلى m بخطوات T :
    - اضرب $A I : I + T, K : K + T$ و $B K : K + T, J : J + T$ في $C I : I + T, J : J + T$ ، أي:
    - لكل i من I إلى min( I + T , n ) :
      - لكل $j$ من $J$ إلى $min(J + T, p)$ :
        لنفترض $أن المجموع = 0$
        لكل $k$ من $K$ إلى $min(K + T, m)$ :
        مجموعة $المجموع \leftarrow المجموع + أ ik \times ب kj$
        المجموعة $C ij \leftarrow C ij + المجموع$
إرجاع $C$

في نموذج الذاكرة المؤقتة المثالي، لا تتسبب هذه الخوارزمية إلا في $Θ(⁠ n 3 / b \sqrt M ⁠)$ من حالات عدم الوصول إلى الذاكرة المؤقتة؛ ويبلغ المقسوم عليه $b \sqrt M$ عدة مراتب من حيث الحجم على الأجهزة الحديثة، بحيث تهيمن العمليات الحسابية الفعلية على وقت التشغيل، بدلاً من حالات عدم الوصول إلى الذاكرة المؤقتة. ^{[ 4 ]}

خوارزمية فرق تسد

يُعدّ خوارزمية فرق تسد بديلاً للخوارزمية التكرارية في ضرب المصفوفات. وتعتمد هذه الخوارزمية على تقسيم المصفوفة إلى كتل .

C={\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}},\,A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}},\,B={\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}},

وهذا ينطبق على جميع المصفوفات المربعة التي أبعادها قوى العدد اثنين، أي أن أشكالها هي $2^n \times 2^n$ لبعض قيم $n$ . ويكون حاصل ضرب المصفوفات الآن

{\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}}{\begin{pmatrix}B_{11}&B_{12}\\B_{21}& B_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}

تتألف هذه العملية من ثماني عمليات ضرب لأزواج من المصفوفات الفرعية، تليها عملية جمع. وتقوم خوارزمية فرق تسد بحساب عمليات الضرب الأصغر بشكل متكرر ، باستخدام الضرب القياسي $c 11 = a 11 b 11$ كحالة أساسية.

يتم تحديد تعقيد هذه الخوارزمية كدالة لـ $n من خلال العلاقة التكرارية$ ^{[ 3 ]}

T(1)=\Theta (1);

T(n)=8T(n/2)+\Theta (n^{2}),

مع الأخذ في الاعتبار الاستدعاءات الثمانية المتكررة على مصفوفات بحجم $n /2$ و $Θ(n²)$ لجمع أزواج المصفوفات الناتجة الأربعة عنصرًا بعنصر. يُظهر تطبيق نظرية ماستر للتكرارات القائمة على أسلوب فرق تسد أن حل هذا التكرار هو ^Θ $(n³)$ $،$ وهو نفس حل الخوارزمية التكرارية. ^[ $3$ ^]

المصفوفات غير المربعة

هناك نسخة معدلة من هذه الخوارزمية تعمل مع المصفوفات ذات الأشكال العشوائية وهي أسرع عمليًا ^{[ 4 ]،} حيث تقسم المصفوفات إلى مصفوفتين فرعيتين بدلًا من أربع، كما يلي. ^{[ 6 ]} يعني تقسيم المصفوفة الآن تقسيمها إلى جزأين متساويين في الحجم، أو أقرب ما يكون إلى التساوي في الحجم في حالة الأبعاد الفردية.

المدخلات: مصفوفات $A$ بحجم $n \times m$ ، $وB$ بحجم $m \times p$ .
الحالة الأساسية: إذا كانت $قيمة max(n, m, p)$ أقل من عتبة معينة، فاستخدم نسخة غير ملفوفة من الخوارزمية التكرارية.
الحالات المتكررة:

إذا كانت $قيمة max(n, m, p) تساوي n$ ، فقم بتقسيم $A$ أفقيًا:

C={\begin{pmatrix}A_{1}\\A_{2}\end{pmatrix}}{B}={\begin{pmatrix}A_{1}B\\A_{2}B\end{pmatrix}}

وإلا، إذا كانت $قيمة max(n, m, p) = p$ ، فقم بتقسيم $B$ عموديًا:

C=A{\begin{pmatrix}B_{1}&B_{2}\end{pmatrix}}={\begin{pmatrix}AB_{1}&AB_{2}\end{pmatrix}}

وإلا، فإن $max(n, m, p) = m$ . قسّم $A$ عموديًا و $B$ أفقيًا:

C={\begin{pmatrix}A_{1}&A_{2}\end{pmatrix}}{\begin{pmatrix}B_{1}\\B_{2}\end{pmatrix}}=A_{1}B_{1}+A_{2}B_{2}

سلوك ذاكرة التخزين المؤقت

معدل فقدان البيانات في ذاكرة التخزين المؤقت لعملية ضرب المصفوفات التكرارية مماثل لمعدل فقدانها في النسخة التكرارية المُجزأة ، ولكن على عكس تلك الخوارزمية، فإن الخوارزمية التكرارية لا تعتمد على ذاكرة التخزين المؤقت : ^{[ 6 ]} فلا حاجة إلى أي معلمات ضبط للحصول على أداء مثالي لذاكرة التخزين المؤقت، كما أنها تعمل بكفاءة في بيئة تعدد البرامج حيث تكون أحجام ذاكرة التخزين المؤقت ديناميكية فعليًا بسبب استخدام العمليات الأخرى لمساحة ذاكرة التخزين المؤقت. ^{[ 4 ]} (الخوارزمية التكرارية البسيطة لا تعتمد على ذاكرة التخزين المؤقت أيضًا، ولكنها أبطأ بكثير عمليًا إذا لم يتم تكييف تخطيط المصفوفة مع الخوارزمية).

عدد حالات عدم العثور على البيانات في ذاكرة التخزين المؤقت التي يتسبب بها هذا الخوارزمية، على جهاز يحتوي على $M$ سطرًا من ذاكرة التخزين المؤقت المثالية، كل منها بحجم $b$ بايت، محدود بالمعادلة ^{[ 6 ]}^{: 13}

\Theta \left(m+n+p+{\frac {mn+np+mp}{b}}+{\frac {mnp}{b{\sqrt {M}}}}\right)

خوارزميات شبه مكعبة

{\displaystyle O(n^{\أوميغا })} — تحسين تقديرات الأس $ω$ بمرور الوقت للتعقيد الحسابي لضرب المصفوفات $O(n^{\أوميغا })$ .

توجد خوارزميات توفر أوقات تشغيل أفضل من الخوارزميات المباشرة. أول هذه الخوارزميات تم اكتشافها هي خوارزمية ستراسن ، التي ابتكرها فولكر ستراسن عام 1969، والتي يُشار إليها غالبًا باسم "ضرب المصفوفات السريع". تعتمد هذه الخوارزمية على طريقة لضرب مصفوفتين من الرتبة 2×2 تتطلب 7 عمليات ضرب فقط (بدلاً من 8 عمليات كما هو معتاد)، على حساب عدة عمليات جمع وطرح إضافية . بتطبيق هذه الطريقة بشكل متكرر، نحصل على خوارزمية بتكلفة ضربية قدرها $O(n^{\log _{2}7})\approx O(n^{2.807})$ خوارزمية ستراسن أكثر تعقيدًا، واستقرارها العددي أقل مقارنةً بالخوارزمية البسيطة، ^{[ 7 ]} لكنها أسرع في الحالات التي يكون فيها $n أكبر من 100$ تقريبًا ^{[ 1 ]} ، وتظهر في العديد من المكتبات، مثل BLAS . ^{[ 8 ]} وهي مفيدة جدًا للمصفوفات الكبيرة على مجالات دقيقة مثل الحقول المنتهية ، حيث لا يمثل الاستقرار العددي مشكلة.

بما أن خوارزمية ستراسن تُستخدم فعليًا في برامج المحاكاة العددية وأنظمة الجبر الحاسوبي ، فإن تحسين الثوابت المُضمنة في ترميز Big-O له مزاياه. فيما يلي جدول يُقارن الجوانب الرئيسية للنسخة المُحسّنة القائمة على الضرب التكراري لمصفوفات كتلية 2×2 عبر 7 عمليات ضرب مصفوفات كتلية. وكالعادة، $n$ يُعطي أبعاد المصفوفة و $M$ يحدد حجم الذاكرة.

التقدم المحرز في ضرب المصفوفات المتكررة من نوع ستراسن 2x2
سنة	مرجع	#عمليات ضرب المصفوفات لكل خطوة	#عمليات جمع المصفوفات لكل خطوة	إجمالي العمليات الحسابية	إجمالي تعقيد الإدخال/الإخراج
1969	Strassen^[9]	7	18	$7n^{\log _{2}7}-6n^{2}$	$6\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-18n^{2}+3M$
1971	Winograd^[10]	7	15	$6n^{\log _{2}7}-5n^{2}$	$5\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-15n^{2}+3M$
2017	Karstadt, Schwartz^[11]	7	12	$5n^{\log _{2}7}-4n^{2}+3n^{2}\log _{2}n$	$4\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-12n^{2}+3n^{2}\cdot \log _{2}\left({\frac {{\sqrt {2}}n}{\sqrt {M}}}\right)+5M$
2023	Schwartz, Vaknin^[12]	7	12	$5n^{\log _{2}7}-4n^{2}+1.5n^{2}\log _{2}n$	$4\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-12n^{2}+1.5n^{2}\cdot \log _{2}\left({\frac {{\sqrt {2}}n}{\sqrt {M}}}\right)+5M$

It is known that a Strassen-like algorithm with a 2×2-block matrix step requires at least 7 block matrix multiplications. In 1976 Probert^[13] showed that such an algorithm requires at least 15 additions (including subtractions); however, a hidden assumption was that the blocks and the 2×2-block matrix are represented in the same basis. Karstadt and Schwartz computed in different bases and traded 3 additions for less expensive basis transformations. They also proved that one cannot go below 12 additions per step using different bases. In subsequent work Beniamini et el.^[14] applied this base-change trick to more general decompositions than 2×2-block matrices and improved the leading constant for their run times.

It is an open question in theoretical computer science how well Strassen's algorithm can be improved in terms of asymptotic complexity. The matrix multiplication exponent, usually denoted $\omega$ , is the smallest real number for which any $n\times n$ matrix over a field can be multiplied together using $n^{\أوميغا +o(1)}$ field operations. The current best bound on $\omega$ is $\أوميغا <2.371339$ , by Alman, Duan, Williams, Xu, Xu, and Zhou.^[2] This algorithm, like all other recent algorithms in this line of research, is a generalization of the Coppersmith–Winograd algorithm, which was given by Don Coppersmith and Shmuel Winograd in 1990.^[15] The conceptual idea of these algorithms is similar to Strassen's algorithm: a way is devised for multiplying two $k \times k$ -matrices with fewer than $k 3$ multiplications, and this technique is applied recursively. However, the constant coefficient hidden by the big-O notation is so large that these algorithms are only worthwhile for matrices that are too large to handle on present-day computers.^[16]^[17]Victor Pan proposed so-called feasible sub-cubic matrix multiplication algorithms with an exponent slightly above 2.77, but in return with a much smaller hidden constant coefficient.^[18]

خوارزمية فريفالدز هي خوارزمية مونت كارلو بسيطة تقوم، عند إعطاء المصفوفات $A$ و $B$ و $C$ ، بالتحقق في وقت $Θ(n 2)$ إذا كان $AB = C.$

ألفا تينسور

في عام 2022، قدمت شركة ديب مايند شبكة ألفا تنسور العصبية ، التي استخدمت تشبيهًا بلعبة فردية لابتكار آلاف خوارزميات ضرب المصفوفات، بما في ذلك بعض الخوارزميات التي اكتشفها البشر سابقًا وبعضها الآخر لم يكتشفها أحد. ^{[ 19 ]} واقتصرت العمليات على الحقل الأساسي غير التبادلي (الحساب العادي) والحقل المنتهي. $\mathbb {Z} /2\mathbb {Z}$ (حساب modulo 2). أفضل خوارزمية "عملية" (تحليل صريح منخفض الرتبة لموتر ضرب المصفوفات) تم العثور عليها استغرقت وقتًا قدره O(n ^2.778 ). ^{[ 20 ]} يُعدّ إيجاد تحليلات منخفضة الرتبة لمثل هذه الموترات (وما بعدها) مسألة صعبة حسابيًا (NP-hard)؛ ولا يزال الضرب الأمثل حتى للمصفوفات 3×3 غير معروف ، حتى في الحقول التبادلية. ^{[ 20 ]} على المصفوفات 4×4، اكتشف AlphaTensor بشكل غير متوقع حلاً بـ 47 خطوة ضرب، وهو تحسن عن الـ 49 خطوة المطلوبة مع خوارزمية ستراسن لعام 1969، على الرغم من أنها تقتصر على حساب modulo 2. وبالمثل، حلّ AlphaTensor المصفوفات 5×5 بـ 96 خطوة بدلاً من 98 خطوة في خوارزمية ستراسن. استنادًا إلى الاكتشاف المثير للدهشة بوجود مثل هذه التحسينات، تمكن باحثون آخرون بسرعة من إيجاد خوارزمية مستقلة مماثلة بحجم 4×4، وقاموا بشكل منفصل بتعديل خوارزمية Deepmind ذات الـ 96 خطوة بحجم 5×5 إلى 95 خطوة في حساب modulo 2 وإلى 97 خطوة ^{[ 21 ]} في الحساب العادي. ^{[ 22 ]} بعض الخوارزميات كانت جديدة تمامًا: على سبيل المثال، تم تحسين (4، 5، 5) إلى 76 خطوة من أصل 80 خطوة في كل من الحساب العادي وحساب modulo 2.

الخوارزميات المتوازية والموزعة

التوازي في الذاكرة المشتركة

يمكن موازاة خوارزمية فرق تسد التي تم شرحها سابقًا بطريقتين للمعالجات المتعددة ذات الذاكرة المشتركة . وتعتمد هاتان الطريقتان على حقيقة أن عمليات ضرب المصفوفات الثمانية المتكررة في

{\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}

يمكن تنفيذ كل عملية على حدة، وكذلك عمليات الجمع الأربع (مع أن الخوارزمية تحتاج إلى "دمج" عمليات الضرب قبل إجراء عمليات الجمع). وباستغلال التوازي الكامل للمسألة، نحصل على خوارزمية يمكن التعبير عنها بلغة شبه رمزية على غرار fork–join : ^[²³^]

إجراء $الضرب (ج ، أ ، ب)$ :

الحالة الأساسية: إذا كان $n = 1$ ، فقم بتعيين $c 11 \leftarrow a 11 \times b 11$ (أو اضرب مصفوفة كتلة صغيرة).
وإلا، فقم بتخصيص مساحة لمصفوفة جديدة T ذات شكل n × n ، ثم:
- قسّم المجموعة $A$ إلى $A 11$ و $A 12$ و $A 21$ و $A 22$ .
- قسّم المجموعة $B$ إلى $B 11$ و $B 12$ و $B 21$ و $B 22$ .
- قسّم المجموعة $C$ إلى $C 11$ و $C 12$ و $C 21$ و $C 22$ .
- قسّم $T$ إلى $T 11$ و $T 12$ و $T 21$ و $T 22$ .
- التنفيذ المتوازي:
  - Fork $multiply(C 11, A 11, B 11)$ .
  - Fork $multiply(C 12, A 11, B 12)$ .
  - Fork $multiply(C 21, A 21, B 11)$ .
  - Fork $multiply(C 22, A 21, B 12)$ .
  - Fork $multiply(T 11, A 12, B 21)$ .
  - Fork $multiply(T 12, A 12, B 22)$ .
  - Fork $multiply(T 21, A 22, B 21)$ .
  - Fork $multiply(T 22, A 22, B 22)$ .
- انضم (انتظر حتى تكتمل التفرعات المتوازية).
- $أضف (ج ، ت)$ .
- إلغاء تخصيص $T.$

الإجراء $add(C, T)$ يضيف $T$ إلى $C$ ، عنصرًا تلو الآخر:

الحالة الأساسية: إذا كان $n = 1$ ، فقم بتعيين $c 11 \leftarrow c 11 + t 11$ (أو قم بعمل حلقة قصيرة، ربما غير ملفوفة).
خلاف ذلك:
- قسّم المجموعة $C$ إلى $C 11$ و $C 12$ و $C 21$ و $C 22$ .
- قسّم $T$ إلى $T 11$ و $T 12$ و $T 21$ و $T 22$ .
- بالتوازي مع ذلك:
  - Fork $add(C 11, T 11)$ .
  - Fork $add(C 12, T 12)$ .
  - Fork $add(C 21, T 21)$ .
  - Fork $add(C 22, T 22)$ .
- ينضم .

هنا، تُعدّ كلمة fork كلمة مفتاحية تُشير إلى إمكانية تشغيل عملية حسابية بالتوازي مع بقية استدعاء الدالة، بينما تنتظر join اكتمال جميع العمليات الحسابية "المتفرعة" سابقًا. $أما partition،$ فتُحقق هدفها من خلال معالجة المؤشرات فقط.

يبلغ طول المسار الحرج لهذه الخوارزمية $Θ(log₂n) خطوة ،$ ما يعني أنها تستغرق هذا القدر من الوقت على جهاز مثالي ذي عدد لا نهائي من المعالجات؛ وبالتالي، فإن أقصى تسريع ممكن لها هو $Θ(n³ /log₂n) على أي حاسوب حقيقي. لا$ تُعد هذه الخوارزمية عملية بسبب تكلفة الاتصال المتأصلة في نقل البيانات من وإلى المصفوفة المؤقتة $T ، ولكن$ $هناك$ صيغة أكثر عملية تحقق تسريعًا $قدره$ $Θ(n²)$ دون استخدام مصفوفة مؤقتة. ^{[ 23 ]}

خوارزميات تجنب الاتصال والخوارزميات الموزعة

في البنى الحديثة ذات الذاكرة الهرمية، تميل تكلفة تحميل وتخزين عناصر مصفوفة الإدخال إلى أن تفوق تكلفة العمليات الحسابية. على جهاز واحد، تمثل هذه التكلفة كمية البيانات المنقولة بين ذاكرة الوصول العشوائي (RAM) وذاكرة التخزين المؤقت (Cache)، بينما على جهاز متعدد العقد ذي ذاكرة موزعة ، تمثل كمية البيانات المنقولة بين العقد؛ وفي كلتا الحالتين، تُسمى هذه التكلفة عرض نطاق الاتصال . تستخدم الخوارزمية البسيطة التي تعتمد على ثلاث حلقات متداخلة عرض نطاق اتصال $مقداره$ $Ω(n³) .$

خوارزمية كانون ، المعروفة أيضًا بالخوارزمية ثنائية الأبعاد ، هي خوارزمية تتجنب استخدام الاتصال $، حيث تقسم كل مصفوفة$ $إدخال$ إلى مصفوفة كتلية عناصرها عبارة عن مصفوفات فرعية بحجم $\sqrtM /3$ × $\sqrtM /3$ ، حيث $M$ هو حجم الذاكرة السريعة. ^{[ 24 ]} ثم تُستخدم الخوارزمية البسيطة على المصفوفات الكتلية، لحساب نواتج المصفوفات الفرعية بالكامل في الذاكرة السريعة. هذا يقلل عرض نطاق الاتصال إلى $O (n³ / \sqrtM) ،$ وهو الأمثل تقاربًا (للخوارزميات التي تُجري ^Ω $(n³) عملية حسابية )$ . ^[ $25$ ^]^{[ 26 ]}

في بيئة موزعة تضم $p$ معالجًا مرتبة في شبكة ثنائية $الأبعاد$ بحجم $\sqrtp \times$ $\sqrtp$ $، يمكن تخصيص مصفوفة$ فرعية واحدة من الناتج لكل معالج، ويمكن حساب الناتج مع إرسال كل معالج $O (n² / \sqrtp)$ كلمة، وهو ما يُعدّ الأمثل تقاربًا بافتراض أن كل عقدة تخزن الحد الأدنى من $O$ $(n² / p) عنصرًا$ . ^{[ 26 ]} يمكن تحسين ذلك باستخدام خوارزمية ثلاثية الأبعاد، والتي ترتب المعالجات في شبكة مكعبة ثلاثية الأبعاد، وتُخصص كل ناتج $ضرب$ لمصفوفتين فرعيتين مدخلتين لمعالج واحد. ثم تُولّد المصفوفات الفرعية الناتجة عن طريق إجراء عملية اختزال على كل صف. ^{[ 27 ]} تُرسل هذه الخوارزمية $O (n² / p² /3)$ كلمة لكل معالج، وهو ما يُعدّ الأمثل تقاربًا. ^{[ 26 ]} $مع ذلك، يتطلب هذا تكرار كل عنصر من$ عناصر مصفوفة الإدخال $p¹ /³$ مرة، وبالتالي يتطلب ذاكرة أكبر بمقدار $p¹ /³$ من الذاكرة اللازمة لتخزين المدخلات. يمكن دمج هذه الخوارزمية مع خوارزمية ستراسن لتقليل وقت التشغيل بشكل أكبر. ^{[ 27 ]} توفر خوارزميات "2.5D" توازناً مستمراً بين استخدام الذاكرة وعرض نطاق الاتصال. ^{[ 28 ]} في بيئات الحوسبة الموزعة الحديثة مثل MapReduce ، تم تطوير خوارزميات ضرب متخصصة. ^{[ 29 ]}

خوارزميات الشبكات

توجد خوارزميات متنوعة لضرب المصفوفات على الشبكات . عند ضرب مصفوفتين من الرتبة n × n على شبكة ثنائية الأبعاد قياسية باستخدام خوارزمية كانون ثنائية الأبعاد ، يمكن إتمام عملية الضرب في 3n - 2 خطوة، مع العلم أن هذا العدد ينخفض إلى النصف عند تكرار العمليات الحسابية. ^{[ 30 ]} المصفوفة القياسية غير فعالة لأن بيانات المصفوفتين لا تصل في وقت واحد، ويجب إضافة أصفار إليها.

تكون النتيجة أسرع على شبكة متقاطعة الأسلاك ثنائية الطبقات، حيث لا تتطلب سوى 2n-1 خطوة. [ ^{31 ] ويتحسن} الأداء أكثر مع تكرار العمليات الحسابية، ليصل إلى كفاءة 100%. ^{[ 32 ]} ويمكن اعتبار مصفوفة الشبكة المتقاطعة الأسلاك حالة خاصة من بنية معالجة غير مستوية (أي متعددة الطبقات). ^{[ 33 ]}

في شبكة ثلاثية الأبعاد تحتوي على n ³ عناصر معالجة، يمكن ضرب مصفوفتين في ${\mathcal {O}}(\log n)$ باستخدام خوارزمية نظام أسماء النطاقات (DNS). ^{[ 34 ]}

انظر أيضاً

مراجع

1 2 3 4 سكينا، ستيفن (2012). "الفرز والبحث". دليل تصميم الخوارزميات . سبرينغر. الصفحات 45-46 ، 401-403 . doi : 10.1007/978-1-84800-070-4_4 . ISBN 978-1-84800-069-8.
1 2 ألمان، جوش؛ دوان، ران؛ ويليامز، فيرجينيا فاسيليفسكا؛ شو، ينزان؛ شو، زيكسوان؛ تشو، رينفي (2025). "زيادة عدم التناظر تؤدي إلى ضرب المصفوفات بشكل أسرع" . وقائع ندوة ACM-SIAM السنوية لعام 2025 حول الخوارزميات المنفصلة (SODA) . SIAM. الصفحات 2005-2039 . doi : 10.1137/1.9781611978322.63 .
1 2 3 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009) [1990]. مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ص 75 – 79. ISBN 0-262-03384-4.
1 2 3 4 5 أماراسينغ، سامان؛ ليسرسون، تشارلز (2010). "6.172 هندسة أداء أنظمة البرمجيات، المحاضرة 8" . MIT OpenCourseWare . معهد ماساتشوستس للتكنولوجيا. مؤرشف من الأصل في 7 أكتوبر 2019. تم الاسترجاع في 27 يناير 2015 .
↑ لام، مونيكا س .؛ روثبرغ، إدوارد إي.؛ وولف، مايكل إي. (1991). أداء ذاكرة التخزين المؤقت وتحسينات الخوارزميات المحظورة . ASPLOS91: المؤتمر الدولي الرابع حول دعم بنية لغات البرمجة وأنظمة التشغيل. doi : 10.1145/106972.106981 . ISBN 978-0-89791-380-5.
١ ٢ ٣ بروكوب، هارالد (١٩٩٩). خوارزميات غير مدركة لذاكرة التخزين المؤقت (ملف PDF) (رسالة ماجستير). معهد ماساتشوستس للتكنولوجيا. hdl : 1721.1/80568 . مؤرشف من الأصل (ملف PDF) بتاريخ ٢٠٢٣-١١-٢٢ . تم الاطلاع عليه بتاريخ ٢٠١٥-٠١-٢٨ .
↑ ميلر، ويب (1975)، "التعقيد الحسابي والاستقرار العددي"، أخبار SIAM ، 4 (2): 97-107 ، CiteSeerX 10.1.1.148.9947 ، doi : 10.1137/0204009
↑ بريس، ويليام هـ.؛ فلاني، برايان ب.؛ تيوكولسكي، شاول أ .؛ فيترلينغ، ويليام ت. (2007). وصفات عددية: فن الحوسبة العلمية ( الطبعة الثالثة). مطبعة جامعة كامبريدج . ص 108. ISBN 978-0-521-88068-8.
↑ ستراسن، فولكر (1969). "الحذف الغاوسي ليس الأمثل". الرياضيات العددية 13 (4): 354-356 . doi : 10.1007/BF02165411 . S2CID 121656251 .
↑ مراسلة خاصة مع بروبرت، روبرت ل. (1976). "حول التعقيد الجمعي لضرب المصفوفات" . مجلة SIAM للحوسبة . 5 (2): 187-203 . doi : 10.1137/0205016 .
↑ كارشتات، إيلاي؛ شوارتز، أوديد (يوليو 2017). "ضرب المصفوفات، أسرع قليلاً" . وقائع الندوة التاسعة والعشرين لجمعية الحوسبة الآلية حول التوازي في الخوارزميات والهياكل . SPAA '17. الصفحات 101-110 . doi : 10.1145/3087556.3087579 .
↑ شوارتز، عوديد؛ فاكنين، نوا (2023). "لعبة الحصى وأساس بديل لضرب المصفوفات عالي الأداء" . مجلة SIAM للحوسبة العلمية . الصفحات C277– C303. doi : 10.1137/22M1502719 .
↑ بروبرت، روبرت ل. (1976). "حول التعقيد الجمعي لضرب المصفوفات". مجلة SIAM للحوسبة 5 ( 2): 187-203 . doi : 10.1137/0205016 .
↑ بنياميني، غال؛ تشينغ، ناثان؛ هولتز، أولغا ؛ كارشتات، إيلاي؛ شوارتز، أوديد (2020). "تبسيط عوامل خوارزميات ضرب المصفوفات السريعة". arXiv : 2008.03759 [ cs.DS ].
↑ كوبرسميث، دون ؛ وينوغراد، شموئيل (1990)، "ضرب المصفوفات باستخدام المتتابعات الحسابية" (ملف PDF) ، مجلة الحساب الرمزي ، 9 (3): 251، doi : 10.1016/S0747-7171(08)80013-2
↑ إيليوبولوس، كوستاس س. (1989)، "حدود تعقيد الحالة الأسوأ لخوارزميات حساب البنية الأساسية للمجموعات الأبيلية المنتهية والأشكال الطبيعية لهيرميت وسميث لمصفوفة عددية" (PDF) ، مجلة SIAM للحوسبة ، 18 (4): 658-669 ، CiteSeerX 10.1.1.531.9309 ، doi : 10.1137/0218045 ، MR 1004789 ، مؤرشف من الأصل (PDF) في 2014-03-05 ، تم استرجاعه في 2015-01-16 ، خوارزمية كوبرسميث-وينوغراد غير عملية، بسبب الثابت الخفي الكبير جدًا في الحد الأعلى لعدد عمليات الضرب المطلوبة.
↑ روبنسون، سارة (نوفمبر 2005)، "نحو خوارزمية مثلى لضرب المصفوفات" (ملف PDF) ، أخبار SIAM ، 38 (9). حتى لو تمكن أحدهم من إثبات إحدى الفرضيات - وبالتالي إثبات أن $ω$ $= 2$ - فمن غير المرجح أن يكون أسلوب الضرب الإكليلي قابلاً للتطبيق على مسائل المصفوفات الكبيرة التي تظهر في الممارسة العملية. [...] يجب أن تكون مصفوفات الإدخال كبيرة للغاية حتى يكون الفرق في الوقت واضحًا.
↑ لادرمان، جوليان؛ بان، فيكتور؛ شا، شوان-هي (1992)، "حول الخوارزميات العملية لضرب المصفوفات المُسرّع"، الجبر الخطي وتطبيقاته ، 162-164 : 557-588 ، doi : 10.1016/0024-3795(92)90393-O
↑ "اكتشاف خوارزميات جديدة باستخدام AlphaTensor" . www.deepmind.com . 5 أكتوبر 2022. تاريخ الاسترجاع: 1 نوفمبر 2022 .
1 2 فوزي، الحسين؛ بالوج ماتيج. هوانغ، أجا؛ هيوبرت، توماس. روميرا باريديس، برناردينو؛ بركاتين، محمد أمين؛ نوفيكوف، الكسندر. ر. رويز، فرانسيسكو ج.؛ شريتويزر، جوليان؛ سويرزكز، جرزيجورز؛ الفضة، ديفيد؛ هاسابيس، ديميس؛ كوهلي، بوشميت (أكتوبر 2022). "اكتشاف خوارزميات ضرب المصفوفات الأسرع مع التعلم المعزز" . طبيعة . 610 (7930): 47–53 . بيب كود : 2022Natur.610...47F . دوى : 10.1038/s41586-022-05172-4 . ردمك 1476-4687 . بمك 9534758 . PMID 36198780 .
↑ كاورز، مانويل؛ موسباور، جاكوب (2022-12-02). "الرسوم البيانية المعكوسة لضرب المصفوفات". arXiv : 2212.01175 [ cs.SC ].
↑ بروبيكر، بن (23 نوفمبر 2022). "الذكاء الاصطناعي يكشف عن إمكانيات جديدة في ضرب المصفوفات" . مجلة كوانتا . تم الاطلاع عليه بتاريخ 26 نوفمبر 2022 .
1 2 راندال، كيث هـ. (1998). سيلك: الحوسبة متعددة الخيوط الفعالة (ملف PDF) (أطروحة دكتوراه). معهد ماساتشوستس للتكنولوجيا. الصفحات 54-57 . hdl : 1721.1/47519 . مؤرشف من الأصل (ملف PDF) بتاريخ 2020-11-06 . تم الاطلاع عليه بتاريخ 2015-01-16 .
↑ كانون، لين إليوت (14 يوليو 1969). حاسوب خلوي لتنفيذ خوارزمية مرشح كالمان (دكتوراه). جامعة ولاية مونتانا.
↑ هونغ، جيه دبليو؛ كونغ، إتش تي (1981). "تعقيد الإدخال/الإخراج: لعبة الحصى الأحمر والأزرق" ( ملف PDF) . وقائع الندوة السنوية الثالثة عشرة لجمعية ACM حول نظرية الحوسبة - STOC '81 . الصفحات 326-333 . doi : 10.1145/800076.802486 . S2CID 8410593. مؤرشف (ملف PDF) من الأصل في 15 ديسمبر 2019.
1 2 3 إيروني، درور؛ توليدو، سيفان؛ تيسكين، ألكسندر (سبتمبر 2004). "الحدود الدنيا للاتصال في ضرب المصفوفات في الذاكرة الموزعة". مجلة الحوسبة المتوازية والموزعة. 64 ( 9): 1017-26 . CiteSeerX 10.1.1.20.7034 . doi : 10.1016/j.jpdc.2004.03.021 .
1 2 أغاروال، آر سي؛ بال، إس إم؛ غوستافسون، إف جي؛ جوشي، إم؛ بالكار، بي. (سبتمبر 1995). "نهج ثلاثي الأبعاد لضرب المصفوفات المتوازي". مجلة آي بي إم للبحوث والتطوير 39 ( 5): 575-582 . CiteSeerX 10.1.1.44.3404 . doi : 10.1147/rd.395.0575 .
↑ سولومونيك، إدغار؛ ديميل، جيمس (2011). "خوارزميات ضرب المصفوفات ثنائية الأبعاد ونصف المتوازية ذات الاتصال الأمثل وخوارزميات تحليل LU" (ملف PDF) . وقائع المؤتمر الدولي السابع عشر للمعالجة المتوازية . المجلد، الجزء الثاني. الصفحات 90-109 . doi : 10.1007/978-3-642-23397-5_10 . ISBN 978-3-642-23397-5.
↑ بوساغ زاده، رضا؛ كارلسون، غونار (2013). "مربع المصفوفة المستقل عن الأبعاد باستخدام MapReduce" (ملف PDF) . arXiv : 1304.1467 . Bibcode : 2013arXiv1304.1467B . تاريخ الاسترجاع: 12 يوليو 2014 .
↑ باي، إس إي؛ شين، تي-دبليو؛ تاكاوكا، تي. (2014). "خوارزمية متوازية أسرع لضرب المصفوفات على مصفوفة شبكية" . بروسيديا لعلوم الحاسوب . 29 : 2230-40 . doi : 10.1016/j.procs.2014.05.208 .
↑ كاك، س. (1988). "مصفوفة شبكية ثنائية الطبقات لضرب المصفوفات". الحوسبة المتوازية . 6 (3): 383-385 . CiteSeerX 10.1.1.88.8527 . doi : 10.1016/0167-8191(88)90078-6 .
↑ كاك، س. (2014). "كفاءة ضرب المصفوفات على مصفوفة الشبكة المتصالبة". arXiv : 1411.3273 [ cs.DC ].
↑ كاك، س. (1988). "الحوسبة المصفوفية متعددة الطبقات". علوم المعلومات . 45 (3): 347-365 . CiteSeerX 10.1.1.90.4753 . doi : 10.1016/0020-0255(88)90010-2 .
↑ ديكل، إليعازر؛ نسيمي، ديفيد؛ ساهني، سرتاج (1981). "خوارزميات المصفوفات والرسوم البيانية المتوازية". مجلة SIAM للحوسبة . 10 (4): 657-675 . doi : 10.1137/0210049 .

للمزيد من القراءة

بوتاري، ألفريدو؛ لانغو، جوليان؛ كورزاك، جاكوب؛ دونغارا، جاك (2009). "فئة من خوارزميات الجبر الخطي المتوازية المُجزأة للمعالجات متعددة النوى". الحوسبة المتوازية . 35 : 38-53 . arXiv : 0709.1272 . doi : 10.1016/j.parco.2008.10.002 . S2CID 955 .
غوتو، كازوشيغي؛ فان دي غاين، روبرت أ. (2008). "تشريح ضرب المصفوفات عالي الأداء". معاملات ACM في البرمجيات الرياضية . 34 (3): 1-25 . CiteSeerX 10.1.1.140.3583 . doi : 10.1145/1356052.1356053 . S2CID 9359223 .
فان زي، فيلد جي؛ فان دي جين، روبرت أ. (2015). "BLIS: إطار عمل لإنشاء وظائف BLAS بسرعة". معاملات ACM في البرمجيات الرياضية . 41 (3): 1-33 . doi : 10.1145/2764454 . S2CID 1242360 .
كيفية تحسين GEMM

[skiena-1] 1 2 3 4 سكينا، ستيفن (2012). "الفرز والبحث". دليل تصميم الخوارزميات . سبرينغر. الصفحات 45-46 ، 401-403 . doi : 10.1007/978-1-84800-070-4_4 . ISBN 978-1-84800-069-8.

[alman2025-2] 1 2 ألمان، جوش؛ دوان، ران؛ ويليامز، فيرجينيا فاسيليفسكا؛ شو، ينزان؛ شو، زيكسوان؛ تشو، رينفي (2025). "زيادة عدم التناظر تؤدي إلى ضرب المصفوفات بشكل أسرع" . وقائع ندوة ACM-SIAM السنوية لعام 2025 حول الخوارزميات المنفصلة (SODA) . SIAM. الصفحات 2005-2039 . doi : 10.1137/1.9781611978322.63 .

[clrs-3] 1 2 3 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009) [1990]. مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ص 75 – 79. ISBN 0-262-03384-4.

[ocw-4] 1 2 3 4 5 أماراسينغ، سامان؛ ليسرسون، تشارلز (2010). "6.172 هندسة أداء أنظمة البرمجيات، المحاضرة 8" . MIT OpenCourseWare . معهد ماساتشوستس للتكنولوجيا. مؤرشف من الأصل في 7 أكتوبر 2019. تم الاسترجاع في 27 يناير 2015 .

[5] لام، مونيكا س .؛ روثبرغ، إدوارد إي.؛ وولف، مايكل إي. (1991). أداء ذاكرة التخزين المؤقت وتحسينات الخوارزميات المحظورة . ASPLOS91: المؤتمر الدولي الرابع حول دعم بنية لغات البرمجة وأنظمة التشغيل. doi : 10.1145/106972.106981 . ISBN 978-0-89791-380-5.

[prokop-6] ١ ٢ ٣ بروكوب، هارالد (١٩٩٩). خوارزميات غير مدركة لذاكرة التخزين المؤقت (ملف PDF) (رسالة ماجستير). معهد ماساتشوستس للتكنولوجيا. hdl : 1721.1/80568 . مؤرشف من الأصل (ملف PDF) بتاريخ ٢٠٢٣-١١-٢٢ . تم الاطلاع عليه بتاريخ ٢٠١٥-٠١-٢٨ .

[7] ميلر، ويب (1975)، "التعقيد الحسابي والاستقرار العددي"، أخبار SIAM ، 4 (2): 97-107 ، CiteSeerX 10.1.1.148.9947 ، doi : 10.1137/0204009

[8] بريس، ويليام هـ.؛ فلاني، برايان ب.؛ تيوكولسكي، شاول أ .؛ فيترلينغ، ويليام ت. (2007). وصفات عددية: فن الحوسبة العلمية ( الطبعة الثالثة). مطبعة جامعة كامبريدج . ص 108. ISBN 978-0-521-88068-8.

[9] ستراسن، فولكر (1969). "الحذف الغاوسي ليس الأمثل". الرياضيات العددية 13 (4): 354-356 . doi : 10.1007/BF02165411 . S2CID 121656251 .

[10] مراسلة خاصة مع بروبرت، روبرت ل. (1976). "حول التعقيد الجمعي لضرب المصفوفات" . مجلة SIAM للحوسبة . 5 (2): 187-203 . doi : 10.1137/0205016 .

[11] كارشتات، إيلاي؛ شوارتز، أوديد (يوليو 2017). "ضرب المصفوفات، أسرع قليلاً" . وقائع الندوة التاسعة والعشرين لجمعية الحوسبة الآلية حول التوازي في الخوارزميات والهياكل . SPAA '17. الصفحات 101-110 . doi : 10.1145/3087556.3087579 .

[12] شوارتز، عوديد؛ فاكنين، نوا (2023). "لعبة الحصى وأساس بديل لضرب المصفوفات عالي الأداء" . مجلة SIAM للحوسبة العلمية . الصفحات C277– C303. doi : 10.1137/22M1502719 .

[13] بروبرت، روبرت ل. (1976). "حول التعقيد الجمعي لضرب المصفوفات". مجلة SIAM للحوسبة 5 ( 2): 187-203 . doi : 10.1137/0205016 .

[14] بنياميني، غال؛ تشينغ، ناثان؛ هولتز، أولغا ؛ كارشتات، إيلاي؛ شوارتز، أوديد (2020). "تبسيط عوامل خوارزميات ضرب المصفوفات السريعة". arXiv : 2008.03759 [ cs.DS ].

[coppersmith-15] كوبرسميث، دون ؛ وينوغراد، شموئيل (1990)، "ضرب المصفوفات باستخدام المتتابعات الحسابية" (ملف PDF) ، مجلة الحساب الرمزي ، 9 (3): 251، doi : 10.1016/S0747-7171(08)80013-2

[16] إيليوبولوس، كوستاس س. (1989)، "حدود تعقيد الحالة الأسوأ لخوارزميات حساب البنية الأساسية للمجموعات الأبيلية المنتهية والأشكال الطبيعية لهيرميت وسميث لمصفوفة عددية" (PDF) ، مجلة SIAM للحوسبة ، 18 (4): 658-669 ، CiteSeerX 10.1.1.531.9309 ، doi : 10.1137/0218045 ، MR 1004789 ، مؤرشف من الأصل (PDF) في 2014-03-05 ، تم استرجاعه في 2015-01-16 ، خوارزمية كوبرسميث-وينوغراد غير عملية، بسبب الثابت الخفي الكبير جدًا في الحد الأعلى لعدد عمليات الضرب المطلوبة.

[robinson-17] روبنسون، سارة (نوفمبر 2005)، "نحو خوارزمية مثلى لضرب المصفوفات" (ملف PDF) ، أخبار SIAM ، 38 (9). حتى لو تمكن أحدهم من إثبات إحدى الفرضيات - وبالتالي إثبات أن $ω$ $= 2$ - فمن غير المرجح أن يكون أسلوب الضرب الإكليلي قابلاً للتطبيق على مسائل المصفوفات الكبيرة التي تظهر في الممارسة العملية. [...] يجب أن تكون مصفوفات الإدخال كبيرة للغاية حتى يكون الفرق في الوقت واضحًا.

[18] لادرمان، جوليان؛ بان، فيكتور؛ شا، شوان-هي (1992)، "حول الخوارزميات العملية لضرب المصفوفات المُسرّع"، الجبر الخطي وتطبيقاته ، 162-164 : 557-588 ، doi : 10.1016/0024-3795(92)90393-O

[19] "اكتشاف خوارزميات جديدة باستخدام AlphaTensor" . www.deepmind.com . 5 أكتوبر 2022. تاريخ الاسترجاع: 1 نوفمبر 2022 .

[alphatensor-20] 1 2 فوزي، الحسين؛ بالوج ماتيج. هوانغ، أجا؛ هيوبرت، توماس. روميرا باريديس، برناردينو؛ بركاتين، محمد أمين؛ نوفيكوف، الكسندر. ر. رويز، فرانسيسكو ج.؛ شريتويزر، جوليان؛ سويرزكز، جرزيجورز؛ الفضة، ديفيد؛ هاسابيس، ديميس؛ كوهلي، بوشميت (أكتوبر 2022). "اكتشاف خوارزميات ضرب المصفوفات الأسرع مع التعلم المعزز" . طبيعة . 610 (7930): 47–53 . بيب كود : 2022Natur.610...47F . دوى : 10.1038/s41586-022-05172-4 . ردمك 1476-4687 . بمك 9534758 . PMID 36198780 .

[21] كاورز، مانويل؛ موسباور، جاكوب (2022-12-02). "الرسوم البيانية المعكوسة لضرب المصفوفات". arXiv : 2212.01175 [ cs.SC ].

[22] بروبيكر، بن (23 نوفمبر 2022). "الذكاء الاصطناعي يكشف عن إمكانيات جديدة في ضرب المصفوفات" . مجلة كوانتا . تم الاطلاع عليه بتاريخ 26 نوفمبر 2022 .

[cilk-23] 1 2 راندال، كيث هـ. (1998). سيلك: الحوسبة متعددة الخيوط الفعالة (ملف PDF) (أطروحة دكتوراه). معهد ماساتشوستس للتكنولوجيا. الصفحات 54-57 . hdl : 1721.1/47519 . مؤرشف من الأصل (ملف PDF) بتاريخ 2020-11-06 . تم الاطلاع عليه بتاريخ 2015-01-16 .

[24] كانون، لين إليوت (14 يوليو 1969). حاسوب خلوي لتنفيذ خوارزمية مرشح كالمان (دكتوراه). جامعة ولاية مونتانا.

[25] هونغ، جيه دبليو؛ كونغ، إتش تي (1981). "تعقيد الإدخال/الإخراج: لعبة الحصى الأحمر والأزرق" ( ملف PDF) . وقائع الندوة السنوية الثالثة عشرة لجمعية ACM حول نظرية الحوسبة - STOC '81 . الصفحات 326-333 . doi : 10.1145/800076.802486 . S2CID 8410593. مؤرشف (ملف PDF) من الأصل في 15 ديسمبر 2019.

[irony-26] 1 2 3 إيروني، درور؛ توليدو، سيفان؛ تيسكين، ألكسندر (سبتمبر 2004). "الحدود الدنيا للاتصال في ضرب المصفوفات في الذاكرة الموزعة". مجلة الحوسبة المتوازية والموزعة. 64 ( 9): 1017-26 . CiteSeerX 10.1.1.20.7034 . doi : 10.1016/j.jpdc.2004.03.021 .

[Agarwal-27] 1 2 أغاروال، آر سي؛ بال، إس إم؛ غوستافسون، إف جي؛ جوشي، إم؛ بالكار، بي. (سبتمبر 1995). "نهج ثلاثي الأبعاد لضرب المصفوفات المتوازي". مجلة آي بي إم للبحوث والتطوير 39 ( 5): 575-582 . CiteSeerX 10.1.1.44.3404 . doi : 10.1147/rd.395.0575 .

[28] سولومونيك، إدغار؛ ديميل، جيمس (2011). "خوارزميات ضرب المصفوفات ثنائية الأبعاد ونصف المتوازية ذات الاتصال الأمثل وخوارزميات تحليل LU" (ملف PDF) . وقائع المؤتمر الدولي السابع عشر للمعالجة المتوازية . المجلد، الجزء الثاني. الصفحات 90-109 . doi : 10.1007/978-3-642-23397-5_10 . ISBN 978-3-642-23397-5.

[29] بوساغ زاده، رضا؛ كارلسون، غونار (2013). "مربع المصفوفة المستقل عن الأبعاد باستخدام MapReduce" (ملف PDF) . arXiv : 1304.1467 . Bibcode : 2013arXiv1304.1467B . تاريخ الاسترجاع: 12 يوليو 2014 .

[30] باي، إس إي؛ شين، تي-دبليو؛ تاكاوكا، تي. (2014). "خوارزمية متوازية أسرع لضرب المصفوفات على مصفوفة شبكية" . بروسيديا لعلوم الحاسوب . 29 : 2230-40 . doi : 10.1016/j.procs.2014.05.208 .

[31] كاك، س. (1988). "مصفوفة شبكية ثنائية الطبقات لضرب المصفوفات". الحوسبة المتوازية . 6 (3): 383-385 . CiteSeerX 10.1.1.88.8527 . doi : 10.1016/0167-8191(88)90078-6 .

[32] كاك، س. (2014). "كفاءة ضرب المصفوفات على مصفوفة الشبكة المتصالبة". arXiv : 1411.3273 [ cs.DC ].

[33] كاك، س. (1988). "الحوسبة المصفوفية متعددة الطبقات". علوم المعلومات . 45 (3): 347-365 . CiteSeerX 10.1.1.90.4753 . doi : 10.1016/0020-0255(88)90010-2 .

[34] ديكل، إليعازر؛ نسيمي، ديفيد؛ ساهني، سرتاج (1981). "خوارزميات المصفوفات والرسوم البيانية المتوازية". مجلة SIAM للحوسبة . 10 (4): 657-675 . doi : 10.1137/0210049 .

[ 1 ]

[ 2 ]

n

[

[

[ 6 ]

[ 7 ]

[ 8 ]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[

[ 24 ]

Ω

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

31 ] ويتحسن

[ 32 ]

[ 33 ]

[ 34 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗