التعقيد الحسابي لضرب المصفوفات

📅 آخر تحديث: ١٩ يوليو ٢٠٢٦
✍️ نُشر في: ١٩ يوليو ٢٠٢٦
📷 يحتوي على 59 صور
الموسوعة الحرة

مشكلة لم تُحل في علوم الحاسوب
ما هي أسرع خوارزمية لضرب المصفوفات؟
المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

في علوم الحاسوب النظرية ، تحدد التعقيدات الحسابية لعملية ضرب المصفوفات سرعة تنفيذها . تُعد خوارزميات ضرب المصفوفات إجراءً فرعيًا أساسيًا في الخوارزميات النظرية والرقمية للجبر الخطي العددي والتحسين ، لذا فإن إيجاد أسرع خوارزمية لضرب المصفوفات ذو أهمية عملية بالغة.

بتطبيق التعريف الرياضي المباشر لضرب المصفوفات ، نحصل على خوارزمية تتطلب n³ عملية حقلية لضرب مصفوفتين من الرتبة n × n على ذلك الحقل ( Θ( n³ ) في ترميز Big O ). والمثير للدهشة أن هناك خوارزميات أخرى توفر أوقات تشغيل أفضل من هذه الخوارزمية البسيطة. أول هذه الخوارزميات تم اكتشافها هي خوارزمية ستراسن ، التي ابتكرها فولكر ستراسن عام 1969، والتي تُعرف غالبًا باسم "ضرب المصفوفات السريع". [ 1 ] لا يزال العدد الأمثل للعمليات الحقلية اللازمة لضرب مصفوفتين مربعتين من الرتبة n × n حتى عوامل ثابتة غير معروف. وهذا سؤال مفتوح رئيسي في علوم الحاسوب النظرية .

اعتبارًا من يناير 2024 يُعدّ O( n² ) ²³⁷¹³¹ أفضل حدٍّ للتعقيد التقاربي لخوارزمية ضرب المصفوفات . [ 2 ] مع ذلك، لا تُستخدم هذه التحسينات، وما شابهها، لخوارزمية ستراسن عمليًا، لأنها خوارزميات ضخمة للغاية : فالمعامل الثابت الذي يُخفيه رمز O الكبير كبير جدًا لدرجة أنها لا تُجدي نفعًا إلا مع المصفوفات التي تفوق قدرة الحواسيب الحالية على التعامل معها. [ 3 ] [ 4 ]

خوارزميات بسيطة

إذا كانت A و B مصفوفتين من الرتبة n × n على حقل ما، فإن حاصل ضربهما AB هو أيضًا مصفوفة من الرتبة n × n على ذلك الحقل، معرفة عنصرًا عنصرًا على النحو التالي: (أب)أناج=∑ك=1نأأناكبكج.{\displaystyle (AB)_{ij}=\sum _{k=1}^{n}A_{ik}B_{kj}.}

خوارزمية الكتاب المدرسي

أبسط طريقة لحساب حاصل ضرب مصفوفتين A و B من الرتبة n × n هي حساب التعبيرات الحسابية الناتجة عن تعريف ضرب المصفوفات. (باللغة شبه البرمجية )

أدخل A و B ، وكلاهما مصفوفتان من الرتبة n × n. قم بتهيئة C لتكون مصفوفة من الرتبة n × n جميع عناصرها أصفار. من أجل i من 1 إلى n : من أجل j من 1 إلى n : من أجل k من 1 إلى n : C [ i ][ j ] = C [ i ][ j ] + A [ i ] [ k ]* B [ k ][ j ] أخرج C (كـ A*B)

تتطلب هذه الخوارزمية ⁠ن3{\displaystyle n^{3}}الضرب و​ن3-ن2{\displaystyle n^{3}-n^{2}}جمع القيم العددية لحساب حاصل ضرب مصفوفتين مربعتين من الرتبة n × n .وبالتالي ، فإن تعقيدها الحسابي هويا(ن3){\displaystyle O(n^{3})}، في نموذج حسابي حيث تستغرق عمليات الحقل (الجمع والضرب) وقتًا ثابتًا (في الممارسة العملية، هذا هو الحال بالنسبة للأرقام ذات الفاصلة العائمة ، ولكن ليس بالضرورة بالنسبة للأعداد الصحيحة).

خوارزمية ستراسن

تُحسّن خوارزمية ستراسن عملية ضرب المصفوفات البسيطة من خلال أسلوب فرق تسد . وتتمثل الملاحظة الأساسية في إمكانية ضرب مصفوفتين من الرتبة 2 × 2 بسبع عمليات ضرب فقط، بدلاً من ثماني عمليات كما هو معتاد (على حساب 11 عملية جمع وطرح إضافية). هذا يعني أنه عند التعامل مع مصفوفات الإدخال من الرتبة n × n كمصفوفات كتلية من الرتبة 2 × 2 ، يمكن اختزال مهمة ضرب مصفوفتين من الرتبة n × n إلى سبع مسائل فرعية لضرب مصفوفتين من الرتبة n /2 × n /2 . ويؤدي تطبيق هذا الأسلوب بشكل متكرر إلى خوارزمية تحتاج إلىيا(نسجل2⁡7)≈يا(ن2.807){\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}العمليات الميدانية.

على عكس الخوارزميات ذات التعقيد التقاربي الأسرع، تُستخدم خوارزمية ستراسن عمليًا. صحيح أن استقرارها العددي أقل مقارنةً بالخوارزمية البسيطة [ 5 ] ، إلا أنها أسرع في الحالات التي يكون فيها n أكبر من 100 تقريبًا [ 6 ] ، وتظهر في العديد من المكتبات، مثل BLAS [ 7 ] . لا تستطيع خوارزميات ضرب المصفوفات السريعة تحقيق الاستقرار على مستوى كل عنصر ، ولكن يمكن إثبات أن بعضها يُظهر استقرارًا على مستوى المعيار [ 8 ] . وهي مفيدة جدًا للمصفوفات الكبيرة على المجالات الدقيقة، مثل الحقول المنتهية ، حيث لا يُمثل الاستقرار العددي مشكلة.

أس ضرب المصفوفات

تحسين تقديرات الأس ω بمرور الوقت للتعقيد الحسابي لضرب المصفوفاتيا(نω){\displaystyle O(n^{\أوميغا })}
نظرة عن قرب للفترة من 1990 إلى 2024
الجدول الزمني لأس ضرب المصفوفات
سنةالحد على ωالمؤلفون
19692.8074ستراسن [ 1 ]
19782.796بان [ 9 ]
19792.780بيني، كابوفاني ، روماني [ 10 ]
19812.522شونهاج [ 11 ]
19812.517روماني [ 12 ]
19812.496صانع النحاس ، وينوغراد [ 13 ]
19862.479ستراسن [ 14 ]
19902.3755صانع النحاس ، وينوغراد [ 15 ]
20102.3737ستوثرز [ 16 ]
20122.3729ويليامز [ 17 ] [ 18 ]
20142.3728639لو غال [ 19 ]
20202.3728596ألمان، ويليامز [ 20 ] [ 21 ]
20222.371866دوان، وو، تشو [ 22 ]
20242.371552ويليامز ، شو، شو، وتشو [ 23 ]
20242.371339ألمان، دوان، ويليامز ، شو، شو، وتشو [ 2 ]

أس ضرب المصفوفات ، والذي يُرمز إليه عادةً بالرمز ω ، هو أصغر عدد حقيقي يكون عنده أي عددين من المصفوفات موجبين في المصفوفة سالبين.ن×ن{\displaystyle n\times n}يمكن ضرب المصفوفات الموجودة على حقل معًا باستخدامنω+o(1){\displaystyle n^{\أوميغا +o(1)}}عمليات الحقول. تُستخدم هذه الصيغة بشكل شائع في أبحاث الخوارزميات ، بحيث يكون للخوارزميات التي تستخدم ضرب المصفوفات كإجراء فرعي حدود على وقت التشغيل يمكن تحديثها مع تحسن الحدود على ω .

باستخدام حد أدنى بسيط وضرب المصفوفات التقليدي للحد الأعلى، يمكن استنتاج أن 2 ≤ ω ≤ 3 بشكل مباشر . يُعدّ ما إذا كانت ω = 2 سؤالًا مفتوحًا رئيسيًا في علوم الحاسوب النظرية ، وهناك خط بحثي لتطوير خوارزميات ضرب المصفوفات للحصول على حدود محسّنة لـ ω .

تستخدم جميع الخوارزميات الحديثة في هذا المجال البحثي طريقة الليزر ، وهي تعميم لخوارزمية كوبرسميث-وينوغراد، التي وضعها دون كوبرسميث وشموئيل وينوغراد عام 1990، وكانت أفضل خوارزمية لضرب المصفوفات حتى عام 2010. [ 24 ] وتتشابه الفكرة الأساسية لهذه الخوارزميات مع خوارزمية ستراسن: حيث تُبتكر طريقة لضرب مصفوفتين من الرتبة k × k بأقل من k³ عملية ضرب ، وتُطبق هذه التقنية بشكل تكراري. إلا أن لطريقة الليزر حدودًا في فعاليتها: فقد أثبت أمبينيس وفيلموس وفرانسوا لو غال [ أ ] أنه لا يمكن استخدامها لإثبات أن ω < 2.3725 بتحليل قوى موترية متزايدة لمعادلة معينة لكوبرسميث ووينوغراد، كما لا يمكن إثبات أن ω < 2.3078 لمجموعة واسعة من متغيرات هذه الطريقة. [ 25 ] في عام 2022، ابتكر دوان وو وتشو نسخة معدلة تكسر الحاجز الأول من الحاجزين مع ω < 2.37188 ، [ 22 ] وقد فعلوا ذلك من خلال تحديد مصدر للتحسين المحتمل في طريقة الليزر يسمى فقدان التجميع والذي يعوضونه باستخدام نسخة غير متماثلة من طريقة التجزئة في خوارزمية كوبرسميث-وينوغراد.

ومع ذلك، تُعدّ الأمثلة المذكورة أعلاه أمثلة كلاسيكية للخوارزميات المجرية . في المقابل، تتميز خوارزمية ستراسن لعام 1969 وخوارزمية بان لعام 1978، اللتان تزيد أسسهما قليلاً عن 2.8 وتقلّ عنها قليلاً، بمعاملات ثابتة تجعلهما قابلتين للتطبيق. [ 26 ]

إعادة صياغة خوارزميات ضرب المصفوفات باستخدام نظرية الزمر

وضع هنري كوهن ، وروبرت كلاينبرغ ، وبالاز سيجيدي، وكريس أومانس، خوارزميات مثل خوارزميتي ستراسن وكوبرسميث-وينوغراد في سياق نظري مختلف تمامًا ، وذلك باستخدام ثلاثيات من مجموعات جزئية من زمر منتهية تحقق خاصية عدم التداخل المعروفة بخاصية الضرب الثلاثي (TPP) . كما قدموا تخمينات، إذا صحت، فإنها ستشير إلى وجود خوارزميات لضرب المصفوفات ذات تعقيد تربيعي أساسًا. وهذا يعني أن الأس الأمثل لضرب المصفوفات هو 2، وهو ما يعتقد معظم الباحثين أنه صحيح بالفعل. [ 4 ] ومن هذه التخمينات أن عائلات الضرب الإكليلي للزمر الأبيلية مع الزمر المتناظرة تحقق عائلات من ثلاثيات المجموعات الجزئية التي تحقق نسخة متزامنة من خاصية الضرب الثلاثي. [ 27 ] [ 28 ] تم دحض العديد من فرضياتهم لاحقًا بواسطة بلاسياك، وكوهن، وتشرش، وغروشو، وناسلوند، وساوين، وأومانز باستخدام طريقة رتبة الشريحة. [ 29 ] علاوة على ذلك، أظهر ألون، وشبيلكا، وكريس أومانز مؤخرًا أن بعض هذه الفرضيات التي تشير إلى ضرب المصفوفات السريع تتعارض مع فرضية أخرى معقولة، وهي فرضية عباد الشمس ، [ 30 ] والتي ترتبط بدورها بمشكلة مجموعة الغطاء. [ 29 ]

الحدود الدنيا لـ ω

يوجد حد أدنى بسيط لـ ⁠ω≥2{\displaystyle \omega \geq 2}بما أن أي خوارزمية لضرب مصفوفتين من الرتبة n × n يجب أن تعالج جميع عناصرها البالغ عددها 2^ n^ 2 ، فإن هناك حدًا أدنى تقاربيًا بديهيًا لعددعمليات ضرب المصفوفات يبلغ Ω( n^ 2 ) . وبالتالي ،2≤ω<2.37188{\displaystyle 2\leq \أوميغا <2.37188}من غير المعروف ما إذا كانω>2{\displaystyle \omega >2}⁠ . إن أفضل حد أدنى معروف لتعقيد ضرب المصفوفات هو Ω( n 2 log( n )) ، بالنسبة لدوائر الحساب ذات المعاملات المحدودة على الأعداد الحقيقية أو المركبة، ويعود الفضل في ذلك إلى ران راز . [ 31 ]

من المعروف أنه في ظل نموذج الحساب الذي تمت دراسته عادةً، لا توجد خوارزمية لضرب المصفوفات تستخدم بالضبط O ( n ω ) عملية؛ يجب أن يكون هناك عامل إضافي هو n o(1) . [ 13 ]

ضرب المصفوفات المستطيلة

تُطبَّق تقنيات مماثلة أيضًا على ضرب المصفوفات المستطيلة. والهدف الرئيسي للدراسة هوω(ك){\displaystyle \omega (k)}وهو الأصغرج{\displaystyle c}بحيث يمكن ضرب مصفوفة بحجمن×⌈نك⌉{\displaystyle n\times \lceil n^{k}\rceil }بمصفوفة بحجم⌈نك⌉×ن{\displaystyle \lceil n^{k}\rceil \times n}معيا(نج+o(1)){\displaystyle O(n^{c+o(1)})}العمليات الحسابية. تنص إحدى نتائج التعقيد الجبري على أن ضرب المصفوفات ذات الحجمن×⌈نك⌉{\displaystyle n\times \lceil n^{k}\rceil }و⌈نك⌉×ن{\displaystyle \lceil n^{k}\rceil \times n}يتطلب نفس عدد العمليات الحسابية التي يتطلبها ضرب المصفوفات ذات الحجمن×⌈نك⌉{\displaystyle n\times \lceil n^{k}\rceil }ون×ن{\displaystyle n\times n}وبحجمن×ن{\displaystyle n\times n}ون×⌈نك⌉{\displaystyle n\times \lceil n^{k}\rceil }لذا، يشمل هذا تعقيد ضرب المصفوفات المستطيلة. [ 32 ] وهذا يعمم أس ضرب المصفوفات المربعة ، لأنω(1)=ω{\displaystyle \أوميغا (1)=\أوميغا }.

بما أن ناتج عملية ضرب المصفوفات هو الحجمن2{\displaystyle n^{2}}لديناω(ك)≥2{\displaystyle \أوميغا (ك)\geq 2}لجميع قيمك{\displaystyle k}إذا استطاع المرء إثبات ذلك لبعض قيمك{\displaystyle k}بين 0 و 1ω(ك)≤2{\displaystyle \omega (k)\leq 2}إذاً، تُظهر هذه النتيجة أنω(ك)=2{\displaystyle \omega (k)=2}لأولئكك{\displaystyle k}أكبر قيمة لـ k بحيثω(ك)=2{\displaystyle \omega (k)=2}يُعرف باسم أس ضرب المصفوفات الثنائي ، ويُرمز له عادةً بالرمز α . يُشار إلى α باسم " الثنائي " لأنه يُظهر أنα=1{\displaystyle \alpha =1}وهذا يعادل إثبات أنω=2{\displaystyle \omega =2}وكما هو الحال مع أس ضرب المصفوفات، يظهر أس ضرب المصفوفات الثنائي أحيانًا في تعقيد الخوارزميات في الجبر الخطي العددي والتحسين. [ 33 ]

أول حدٍّ لقيمة α كان من قِبل كوبرسميث في عام 1982، الذي أثبت أنα>0.17227{\displaystyle \alpha >0.17227}[ 34 ] أفضل حدٍّ حاليٍّ مُراجَعٍ من قِبَل النظراء على α هوα≥0.321334{\displaystyle \alpha \geq 0.321334}، مقدمة من ويليامز، شو، شو، وتشو. [ 23 ]

تعقيد البتات في ضرب المصفوفات

يفترض النموذج الجبري المفصل أعلاه أن كل عملية حسابية في الحقل، مثل الجمع أو الضرب، تتطلب تكلفة موحدة .يا(1){\displaystyle O(1)}. هذا افتراض واقعي للحساب الدقيق في الحقول المنتهية أو الحساب التقريبي للأعداد العشرية.

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

يسجل هارفي وفان دير هوفن [ 35 ] الحد العام لـيا(دωم(ن+إل جي⁡(د)){\displaystyle O(d^{\omega }{\text{M}}(n+\lg(d))}العمليات في نموذج آلة تورينج متعددة الأشرطة حيثد{\displaystyle d}يمثل بُعد المصفوفتين المربعتين،ن{\displaystyle n}يمثل الحد الأقصى لحجم البتات لمعاملات مصفوفة الأعداد الصحيحة،ω{\displaystyle \omega }يشير إلى أس ضرب المصفوفات في النموذج الجبري المذكور أعلاه،م(x)=يا(xسجل⁡(x)){\displaystyle {\text{M}}(x)=O(x\log(x))}يشير إلى تعقيد عملية ضرب عددين صحيحين بطول x بت وإل جي⁡(د)=⌈سجل2⁡(د)⌉{\displaystyle \lg(d)=\lceil \log _{2}(d)\rceil }يُعد هذا اختيارًا خاصًا للوغاريتم. كما أنها تُعطي حدودًا مُحسّنة بشرط ألا يكون بُعد المصفوفة كبيرًا جدًا مقارنةً بطول بتات المعاملات، على سبيل المثال إذاإل جي⁡(د)<جن{\displaystyle \lg(d)<Cn}لبعض الثوابتج>1{\displaystyle C>1}.

يوضح المثال السابق للحقول المنتهية مقابل الأعداد الصحيحة أن تعقيد البتات في ضرب المصفوفات يعتمد على المجال الحسابي لمعاملات المصفوفة. بالنسبة للحقول المنتهية، يمكن تحديد طول بتات المعاملات بثابت، ولا يمكن أن يحدث نمو وسيط للمعاملات . أما بالنسبة للأعداد الصحيحة، فتؤدي هذه الظاهرة إلى تضمين الحدإل جي⁡(د){\displaystyle \lg(d)}في العاملم(ن+إل جي⁡(د)){\displaystyle {\text{M}}(n+\lg(d))}يعكس ذلك عملية ضرب الأعداد الصحيحة ذات أطوال البتات التي قد تكون أكبر فأصغر خلال مسار خوارزمية ضرب المصفوفات.

تشمل المسائل التي لها نفس التعقيد التقاربي لضرب المصفوفات: حساب المحدد ، وعكس المصفوفة ، والحذف الغاوسي (انظر القسم التالي). أما المسائل ذات التعقيد الذي يمكن التعبير عنه بدلالةω{\displaystyle \omega }وتشمل متعددة الحدود المميزة ، والقيم الذاتية (ولكن ليس المتجهات الذاتية)، والشكل الطبيعي لهرميت ، والشكل الطبيعي لسميث .

معكوس المصفوفة، والمحدد، والحذف الغاوسي

في بحثه الذي نشره عام 1969، حيث أثبت التعقيديا(نسجل2⁡7)≈يا(ن2.807){\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}في حسابات المصفوفات، أثبت ستراسن أيضًا أن معكوس المصفوفة ، والمحدد، والحذف الغاوسي، لها، حتى ثابت ضربي، نفس التعقيد الحسابي لضرب المصفوفات. لا يفترض البرهان أي افتراضات حول ضرب المصفوفات المستخدم، باستثناء أن تعقيده هويا(نω){\displaystyle O(n^{\أوميغا })}بالنسبة للبعضω≥2{\displaystyle \omega \geq 2}.

تعتمد نقطة انطلاق برهان ستراسن على استخدام ضرب المصفوفات المقطعية . تحديدًا، يمكن تقسيم مصفوفة ذات بُعد زوجي 2n × 2n إلى أربعة مقاطع بحجم n × n .[أبجد].{\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}.} في هذا الشكل، يكون معكوسه هو [أبجد]-1=[أ-1+أ-1ب(د-جأ-1ب)-1جأ-1-أ-1ب(د-جأ-1ب)-1-(د-جأ-1ب)-1جأ-1(د-جأ-1ب)-1]،{\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}^{-1}={\begin{bmatrix}{A}^{-1}+{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&-{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}\\-({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&({D}-{CA}^{-1}{B})^{-1}\end{bmatrix}},} بشرط أن يكون A ود-جأ-1ب{\displaystyle {D}-{CA}^{-1}{B}}قابلة للعكس.

وبالتالي، يمكن حساب معكوس مصفوفة من الرتبة 2n × 2n بعمليتي قلب، وست عمليات ضرب ، وأربع عمليات جمع أو معكوسات جمعية لمصفوفات من الرتبة n × n . ويترتب على ذلك أنه إذا رمزنا على التوالي بـ I ( n ) و M ( n ) و A ( n ) = n² لعدد العمليات اللازمة لقلب وضرب وجمع مصفوفات من الرتبة n × n ، فإن أنا(2ن)≤2أنا(ن)+6م(ن)+4أ(ن).{\displaystyle I(2n)\leq 2I(n)+6M(n)+4A(n).} لون=2ك،{\displaystyle n=2^{k},}يمكن تطبيق هذه الصيغة بشكل متكرر: أنا(2ك)≤2أنا(2ك-1)+6م(2ك-1)+4أ(2ك-1)≤22أنا(2ك-2)+6(م(2ك-1)+2م(2ك-2))+4(أ(2ك-1)+2أ(2ك-2))⋮{\displaystyle {\begin{aligned}I(2^{k})&\leq 2I(2^{k-1})+6M(2^{k-1})+4A(2^{k-1})\\&\leq 2^{2}I(2^{k-2})+6(M(2^{k-1})+2M(2^{k-2}))+4(A(2^{k-1})+2A(2^{k-2}))\\&\,\,\,\vdots \end{aligned}}} لوم(ن)≤جنω،{\displaystyle M(n)\leq cn^{\omega },}وα=2ω≥4،{\displaystyle \alpha =2^{\omega }\geq 4,}يحصل المرء في النهاية أنا(2ك)≤2كأنا(1)+6ج(αك-1+2αك-2+⋯+2ك-1α0)+ك2ك+1≤2ك+6جαك-2كα-2+ك2ك+1≤د(2ك)ω{\displaystyle {\begin{aligned}I(2^{k})&\leq 2^{k}I(1)+6c(\alpha ^{k-1}+2\alpha ^{k-2}+\cdots +2^{k-1}\alpha ^{0})+k2^{k+1}\\&\leq 2^{k}+6c{\frac {\alpha ^{k}-2^{k}}{\alpha -2}}+k2^{k+1}\\&\leq d(2^{k})^{\omega }\end{aligned}}} لبعض الثوابت d .

بالنسبة للمصفوفات التي لا يكون بُعدها قوة للعدد اثنين، يتم الوصول إلى نفس التعقيد عن طريق زيادة بُعد المصفوفة إلى قوة للعدد اثنين، وذلك عن طريق حشو المصفوفة بصفوف وأعمدة تكون مدخلاتها 1 على القطر و0 في أي مكان آخر.

يثبت هذا التعقيد المزعوم للمصفوفات بحيث تكون جميع المصفوفات الفرعية التي يجب قلبها قابلة للقلب بالفعل. وبذلك، يُثبت هذا التعقيد لجميع المصفوفات تقريبًا، حيث أن المصفوفة ذات العناصر المختارة عشوائيًا قابلة للقلب باحتمال واحد.

وينطبق نفس المنطق على تحليل LU ، فإذا كانت المصفوفة A قابلة للعكس، فإن المساواة [أبجد]=[أنا0جأ-1أنا][أب0د-جأ-1ب]{\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}={\begin{bmatrix}I&0\\CA^{-1}&I\end{bmatrix}}\,{\begin{bmatrix}A&B\\0&D-CA^{-1}B\end{bmatrix}}} يُعرّف هذا التعريف تحليل LU الكتلي الذي يمكن تطبيقه بشكل متكرر علىأ{\displaystyle A}ود-جأ-1ب،{\displaystyle D-CA^{-1}B,}للحصول في النهاية على تحليل LU حقيقي للمصفوفة الأصلية.

ينطبق هذا الاستدلال أيضًا على المحدد، لأنه ينتج عن تحليل LU الكتلي أن المحقق[أبجد]=المحقق(أ)المحقق(د-جأ-1ب).{\displaystyle \det {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}=\det(A)\det(D-CA^{-1}B).}

تقليل عدد عمليات الضرب

يرتبط بمشكلة تقليل عدد العمليات الحسابية تقليل عدد عمليات الضرب، وهي عملية عادةً ما تكون أكثر تكلفة من عملية الجمع.يا(نω){\displaystyle O(n^{\omega })}يجب أن تستخدم خوارزمية ضرب المصفوفات بالضرورة فقطيا(نω){\displaystyle O(n^{\omega })}عمليات الضرب، لكن هذه الخوارزميات غير عملية. تحسين من الخوارزمية البسيطةن3{\displaystyle n^{3}}جداول الضرب لكتاب الضرب المدرسي،4×4{\displaystyle 4\times 4}المصفوفات فيZ/2Z{\displaystyle \mathbb {Z} /2\mathbb {Z} }يمكن القيام بذلك باستخدام 47 عملية ضرب، [ 36 ]3×3{\displaystyle 3\times 3}يمكن إجراء عملية ضرب المصفوفات على حلقة تبديلية في 21 عملية ضرب [ 37 ] [ 38 ] (23 إذا كانت الحلقة غير تبديلية [ 39 ] ). الحد الأدنى لعدد عمليات الضرب المطلوبة هو 2mn + 2n - m - 2 (ضرب مصفوفات من الرتبة n × m بمصفوفات من الرتبة m × n باستخدام طريقة الاستبدال).م≥ن≥3{\displaystyle m\geq n\geq 3}وهذا يعني أن حالة n=3 تتطلب 19 عملية ضرب على الأقل، وحالة n=4 تتطلب 34 عملية ضرب على الأقل. [ 40 ] أما بالنسبة لحالة n=2، فإن سبع عمليات ضرب و15 عملية جمع هي الحد الأدنى الأمثل، مقارنةً بأربع عمليات جمع فقط لثماني عمليات ضرب. [ 41 ] [ 42 ]

انظر أيضاً

ملحوظات

  1. ↑ لا ينبغي الخلط بينه وبين جان فرانسوا لو غال

مراجع

  1. 1 2 فولكر ستراسن (أغسطس 1969). "الإزالة الغوسية ليست مثالية" . الرياضيات الرقمية . 13 (4): 354-356 . دوى : 10.1007 / BF02165411 . S2CID 121656251 . 
  2. 1 2 ألمان، جوش. دوان، ران؛ ويليامز، فيرجينيا فاسيليفسكا؛ شو، ينزان؛ شو، زيكسوان؛ تشو، رينفي (2024). “المزيد من عدم التماثل يؤدي إلى مضاعفة أسرع للمصفوفة”. أرخايف : 2404.16349 [ cs.DS ].
  3. ↑ إيليوبولوس، كوستاس س. (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 . خوارزمية كوبرسميث-وينوغراد غير عملية، نظرًا للثابت الخفي الكبير جدًا في الحد الأعلى لعدد عمليات الضرب المطلوبة.  
  4. ١ ٢ روبنسون، سارة (نوفمبر ٢٠٠٥). "نحو خوارزمية مثلى لضرب المصفوفات" (ملف PDF) . أخبار SIAM . ٣٨ (٩). حتى لو تمكن أحدهم من إثبات إحدى الفرضيات - وبالتالي إثبات أن ω = ٢ - فمن غير المرجح أن يكون أسلوب الضرب الإكليلي قابلاً للتطبيق على مسائل المصفوفات الكبيرة التي تظهر في الممارسة العملية. [...] يجب أن تكون مصفوفات الإدخال كبيرة للغاية حتى يكون الفرق في الوقت واضحًا.
  5. ↑ ميلر، ويب (1975). "التعقيد الحسابي والاستقرار العددي". أخبار SIAM . 4 (2): 97-107 . CiteSeerX 10.1.1.148.9947 . doi : 10.1137/0204009 . 
  6. ↑ سكينا، ستيفن (2012). "الفرز والبحث". دليل تصميم الخوارزميات . سبرينغر. الصفحات 45-46 ، 401-403 . doi : 10.1007/978-1-84800-070-4_4 . ISBN  978-1-84800-069-8.
  7. ↑ بريس، ويليام هـ.؛ فلاني، برايان ب.؛ تيوكولسكي، شاول أ .؛ فيترلينغ، ويليام ت. (2007). وصفات عددية: فن الحوسبة العلمية ( الطبعة الثالثة). مطبعة جامعة كامبريدج . ص 108. ISBN   978-0-521-88068-8.
  8. ↑ بالارد، غراي؛ بنسون، أوستن ر.؛ دروينسكي، أليكس؛ ليبشيتز، بنجامين؛ شوارتز، أوديد (2016). "تحسين الاستقرار العددي لضرب المصفوفات السريع". مجلة SIAM لتحليل المصفوفات وتطبيقاتها . 37 (4): 1382-1418 . arXiv : 1507.00687 . doi : 10.1137/15M1032168 . S2CID 2853388 . 
  9. ↑ فيكتور ياكوفليفيتش بان (أكتوبر 1978). "خوارزمية ستراسن ليست مثالية: تقنية ثلاثية الخطوط للتجميع والتوحيد والإلغاء لبناء خوارزميات سريعة لعمليات المصفوفات". وقائع المؤتمر التاسع عشر لأسس علوم الحاسوب . الصفحات 166-176 . doi : 10.1109/SFCS.1978.34 . S2CID 14348408 .  
  10. ^ داريو أندريا بيني. ميلفيو كابوفاني؛ فرانشيسكو روماني؛ غراتسيا لوتي (يونيو 1979). "يا(ن2.7799){\displaystyle O(n^{2.7799})}تعقيد لـن×ن{\displaystyle n\times n}"الضرب التقريبي للمصفوفات" . رسائل معالجة المعلومات . 8 (5): 234-235 . doi : 10.1016/0020-0190(79)90113-3 .
  11. ↑ أ. شونهاج (1981). "الضرب الجزئي والكلي للمصفوفات". مجلة SIAM للحوسبة . 10 (3): 434-455 . doi : 10.1137/0210032 .
  12. ↑ فرانشيسكو روماني (1982). "بعض خصائص المجاميع المنفصلة للموترات المتعلقة بضرب المصفوفات". مجلة SIAM للحوسبة . 11 (2): 263-267 . doi : 10.1137/0211020 .
  13. 1 2 د. كوبرسميث؛ س. وينوغراد (1981). "حول التعقيد التقاربي لضرب المصفوفات". وقائع الندوة السنوية الثانية والعشرين حول أسس علوم الحاسوب (FOCS) . الصفحات 82-90 . doi : 10.1109/SFCS.1981.27 . S2CID 206558664 .  
  14. ↑ فولكر ستراسن (أكتوبر 1986). "الطيف التقاربي للموترات وأسّ ضرب المصفوفات". وقائع الندوة السنوية السابعة والعشرين حول أسس علوم الحاسوب (FOCS) . الصفحات 49-54 . doi : 10.1109/SFCS.1986.52 . ISBN  0-8186-0740-8. S2CID 15077423 . 
  15. ↑ د. كوبرسميث؛ س. وينوغراد (مارس 1990). "ضرب المصفوفات باستخدام المتتابعات الحسابية" . مجلة الحساب الرمزي . 9 (3): 251-280 . doi : 10.1016/S0747-7171(08)80013-2 .
  16. ↑ ستوثرز، أندرو جيمس (2010). حول تعقيد ضرب المصفوفات (أطروحة دكتوراه). جامعة إدنبرة.
  17. ↑ فيرجينيا فاسيلفسكا ويليامز (2012). "ضرب المصفوفات أسرع من خوارزمية كوبرسميث-وينوغراد". في: هوارد ج. كارلوف؛ تونيان بيتاسي (محرران). وقائع الندوة الرابعة والأربعين حول نظرية الحوسبة (STOC) . ACM. الصفحات 887-898 . doi : 10.1145/2213977.2214056 . ISBN  978-1-4503-1245-5. S2CID 14350287 . 
  18. ↑ ويليامز، فيرجينيا فاسيلفسكا . ضرب المصفوفات فييا(ن2.373){\displaystyle O(n^{2.373})}الوقت (ملف PDF) (تقرير فني). جامعة ستانفورد.
  19. ↑ لو غال، فرانسوا (2014). "نظرية التعقيد الجبري وضرب المصفوفات". في كاتسوسوكي نابيشيما (محرر). وقائع الندوة الدولية التاسعة والثلاثين حول الحساب الرمزي والجبري - ISSAC '14 . الصفحات 296-303 . arXiv : 1401.7714 . Bibcode : 2014arXiv1401.7714L . doi : 10.1145/2608628.2627493 . ISBN  978-1-4503-2501-1. S2CID 2597483 . 
  20. ↑ ألمان، جوش؛ ويليامز، فيرجينيا فاسيليفسكا (2024). "طريقة ليزر محسّنة وضرب مصفوفات أسرع". ثيوريتكس 11261. arXiv : 2010.05846 . doi : 10.46298/theoretics.24.21 .
  21. ↑ هارتنيت، كيفن (23 مارس 2021). "ضرب المصفوفات يقترب خطوة من الهدف الأسطوري" . مجلة كوانتا . تم الاطلاع عليه بتاريخ 1 أبريل 2021 .
  22. 1 2 دوان، ران؛ وو، هونغشون؛ تشو، رينفي (2022). "ضرب المصفوفات بشكل أسرع عبر التجزئة غير المتماثلة". arXiv : 2210.10173 [ cs.DS ].
  23. 12Vassilevska Williams, Virginia; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei. New Bounds for Matrix Multiplication: from Alpha to Omega. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 3792–3835. arXiv:2307.07970. doi:10.1137/1.9781611977912.134.
  24. ↑Coppersmith, Don; Winograd, Shmuel (1990). "Matrix multiplication via arithmetic progressions"(PDF). Journal of Symbolic Computation. 9 (3): 251. doi:10.1016/S0747-7171(08)80013-2.
  25. ↑Ambainis, Andris; Filmus, Yuval; Le Gall, François (2015-06-14). "Fast Matrix Multiplication". Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. STOC '15. Portland, Oregon, USA: Association for Computing Machinery. pp. 585–593. arXiv:1411.5414. doi:10.1145/2746539.2746554. ISBN 978-1-4503-3536-2. S2CID 8332797.
  26. ↑Laderman, Julian; Pan, Victor; Sha, Xuan-He (1992). "On practical algorithms for accelerated matrix multiplication". Linear Algebra and Its Applications. 162–164: 557–588. doi:10.1016/0024-3795(92)90393-O.
  27. ↑Cohn, H.; Kleinberg, R.; Szegedy, B.; Umans, C. (2005). "Group-theoretic Algorithms for Matrix Multiplication". 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). p. 379. arXiv:math/0511460. doi:10.1109/SFCS.2005.39. ISBN 0-7695-2468-0. S2CID 41278294.
  28. ↑Cohn, Henry; Umans, Chris (2003). "A Group-theoretic Approach to Fast Matrix Multiplication". Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 11–14 October 2003. IEEE Computer Society. pp. 438–449. arXiv:math.GR/0307321. doi:10.1109/SFCS.2003.1238217. ISBN 0-7695-2040-5. S2CID 5890100.
  29. 1 2 بلاسياك، ج.؛ كوهن، هـ.؛ تشيرش، ت.؛ غروشو، ج.؛ ناسلوند، إ.؛ ساوين، و.؛ أومانس، س. (2017). "حول مجموعات الغطاء والنهج النظري للمجموعات في ضرب المصفوفات". التحليل المتقطع . ص 1245. doi : 10.19086/da.1245 . S2CID 9687868 .  
  30. ↑ ألون، ن .؛ شبيلكا، أ.؛ أومانس، س. (أبريل 2011). "حول عباد الشمس وضرب المصفوفات" . ندوة إلكترونية حول التعقيد الحسابي . TR11-067.
  31. ↑ راز، ران (2002). "حول تعقيد ضرب المصفوفات". وقائع الندوة السنوية الرابعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة . الصفحات 144-151 . doi : 10.1145/509907.509932 . ISBN  1581134959. S2CID 9582328 . 
  32. ↑ غال، فرانسوا لو؛ أوروتيا، فلورنت (2018). "تحسين ضرب المصفوفات المستطيلة باستخدام قوى موتر كوبرسميث-وينوغراد". في تشوماج، أرتور (محرر). وقائع الندوة السنوية التاسعة والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة، ​​SODA 2018، نيو أورليانز، لويزيانا، الولايات المتحدة الأمريكية، 7-10 يناير 2018. جمعية الرياضيات الصناعية والتطبيقية. ص 1029-1046 . arXiv : 1708.05622 . doi : 10.1137/1.9781611975031.67 . ISBN  978-1-61197-503-1.
  33. ↑ كوهين، مايكل ب.؛ لي، ين تات؛ سونغ، تشاو (2021-01-05). "حل البرامج الخطية في زمن ضرب المصفوفات الحالي" . مجلة ACM . 68 (1): 3:1–3:39. arXiv : 1810.07896 . doi : 10.1145/3424305 . ISSN 0004-5411 . S2CID 231955576 .  
  34. ↑ كوبرسميث، د. (1982-08-01). "الضرب السريع للمصفوفات المستطيلة" . مجلة SIAM للحوسبة . 11 (3): 467-471 . doi : 10.1137/0211037 . ISSN 0097-5397 . 
  35. ↑ هارفي، د.؛ فان دير هوفن، ج. (2018). "حول تعقيد ضرب المصفوفات الصحيحة" . مجلة الحساب الرمزي . 89 (1): 1-8 . doi : 10.1016/j.jsc.2017.11.001 . ISSN 0747-7171 . 
  36. ↑ انظر الشكل 1 من البيانات الموسعة: خوارزمية لضرب المصفوفات 4 × 4 في الحساب النمطي (Z2{\displaystyle \mathbb {Z} _{2}})) مع 47 عملية ضرب في فوزي، أ.؛ بالوغ، م.؛ هوانغ، أ.؛ هوبرت، ت.؛ روميرا-باريديس، ب.؛ باريكاتين، م.؛ نوفيكوف، أ.؛ رويز، ف. ج.؛ شريتويزر، ج.؛ سويرشز، ج.؛ سيلفر، د.؛ حسابيس، د.؛ كوهلي، ب. (2022). "اكتشاف خوارزميات أسرع لضرب المصفوفات باستخدام التعلم المعزز" . مجلة نيتشر . 610 (7930): 47-53 . Bibcode : 2022Natur.610...47F . doi : 10.1038/s41586-022-05172-4 . PMC 9534758. PMID 36198780 .  
  37. ↑ روسوفسكي، أندرياس (2023). "خوارزميات المصفوفات التبادلية السريعة". مجلة الحساب الرمزي . 114 : 302-321 . arXiv : 1904.07683 . doi : 10.1016/j.jsc.2022.05.002 . MR 4433063 . 
  38. ^ ماكاروف، أوم (1986). "خوارزمية ضرب المصفوفات 3 × 3" . Zhurnal Vychislitel'noi Matematiki I Matematicheskoi Fiziki . 26 (2): 293 – 294 . تم الاسترجاع في 5 أكتوبر 2022 .
    انظر أيضًا: ماكاروف، أوم (1986). "خوارزمية لضرب المصفوفات 3×3". الرياضيات الحاسوبية والفيزياء الرياضية في الاتحاد السوفيتي . 26 : 179-180 . doi : 10.1016/0041-5553(86)90203-X .
  39. ↑ لادرمان، جوليان د. (1976). "خوارزمية غير تبادلية لضرب المصفوفات 3×3 باستخدام 23 عملية ضرب" . نشرة الجمعية الرياضية الأمريكية . 82 (1): 126-128 . doi : 10.1090/S0002-9904-1976-13988-2 . ISSN 0002-9904 . 
  40. ↑ بلازر، ماركوس (فبراير 2003). "حول تعقيد ضرب المصفوفات ذات الأحجام الصغيرة" . مجلة التعقيد . 19 (1): 43-60 . doi : 10.1016/S0885-064X(02)00007-9 .
  41. ↑ وينوغراد، س. (1971-10-01). "حول ضرب المصفوفات من الرتبة 2 × 2" . الجبر الخطي وتطبيقاته . 4 (4): 381-388 . doi : 10.1016/0024-3795(71)90009-7 . ISSN 0024-3795 . 
  42. ↑ ل.، بروبرت، ر. (1973). حول تعقيد ضرب المصفوفات . جامعة واترلو. OCLC 1124200063 . {{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )