علماء الكمبيوتر هم مجموعة متطلبة. بالنسبة لهم، لا يكفي الحصول على الإجابة الصحيحة لمشكلة ما - فالهدف، دائمًا تقريبًا، هو الحصول على الإجابة بأكبر قدر ممكن من الكفاءة.

لنأخذ عملية ضرب المصفوفات، أو صفائف الأرقام. في عام 1812، توصل عالم الرياضيات الفرنسي جاك فيليب ماري بينيه إلى مجموعة القواعد الأساسية التي لا نزال نعلمها للطلاب. إنها تعمل بشكل جيد تمامًا، لكن علماء رياضيات آخرين وجدوا طرقًا لتبسيط العملية وتسريعها. الآن مهمة تسريع العملية تكمن عملية ضرب المصفوفات في نقطة التقاطع بين الرياضيات وعلوم الكمبيوتر، حيث يواصل الباحثون تحسين العملية حتى يومنا هذا - على الرغم من أن المكاسب التي تحققت في العقود الأخيرة كانت متواضعة إلى حد ما. منذ عام 1987، كانت التحسينات العددية في ضرب المصفوفات "صغيرة و... صعبة المنال للغاية"، كما قال. فرانسوا لو غال، عالم كمبيوتر في جامعة ناغويا.

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

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

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

أدخل المصفوفة

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

الطريقة التقليدية لضرب اثنين nعلى حدةn المصفوفات — عن طريق ضرب الأرقام من كل صف في المصفوفة الأولى في الأرقام الموجودة في الأعمدة في الثانية — يتطلب n³ الضرب المنفصل. بالنسبة للمصفوفات 2 × 2، فهذا يعني 2³ أو 8 مضاعفات.

في عام 1969، كشف عالم الرياضيات فولكر ستراسن عن إجراء أكثر تعقيدًا يمكنه ضرب مصفوفات 2 × 2 في سبع خطوات ضرب و18 عملية جمع فقط. وبعد ذلك بعامين، أثبت عالم الكمبيوتر شموئيل فينوغراد أن العدد سبعة هو في الواقع الحد الأدنى المطلق لمصفوفات 2 × 2.

استغل ستراسين نفس الفكرة لإظهار أن كل شيء أكبر nعلى حدةn يمكن أيضًا ضرب المصفوفات في أقل من n³ خطوات. يتضمن أحد العناصر الأساسية في هذه الاستراتيجية إجراءً يسمى التحلل، وهو تقسيم مصفوفة كبيرة إلى مصفوفات فرعية أصغر على التوالي، والتي قد ينتهي بها الأمر إلى أن تكون صغيرة مثل 2 × 2 أو حتى 1 × 1 (هذه مجرد أرقام فردية).

إن الأساس المنطقي لتقسيم المصفوفة العملاقة إلى أجزاء صغيرة بسيط جدًا، وفقًا لـ فيرجينيا فاسيليفسكا ويليامز، عالم كمبيوتر في معهد ماساتشوستس للتكنولوجيا ومؤلف مشارك لإحدى الأوراق البحثية الجديدة. وقالت فاسيليفسكا ويليامز: "من الصعب على الإنسان أن ينظر إلى مصفوفة كبيرة (على سبيل المثال، في حدود 100 × 100) ويفكر في أفضل خوارزمية ممكنة". حتى المصفوفات 3 × 3 لم يتم حلها بالكامل بعد. "ومع ذلك، يمكن للمرء استخدام خوارزمية سريعة تم تطويرها بالفعل للمصفوفات الصغيرة للحصول أيضًا على خوارزمية سريعة للمصفوفات الأكبر حجمًا."

لقد قرر الباحثون أن مفتاح السرعة هو تقليل عدد خطوات الضرب، وخفض هذا الأس من n³ (للطريقة القياسية) بقدر ما يستطيعون. أدنى قيمة ممكنة، n²، هو في الأساس ما يستغرقه الأمر فقط لكتابة الإجابة. يشير علماء الكمبيوتر إلى هذا الأس باسم أوميغا، ω، مع n^ω كونها أقل عدد ممكن من الخطوات اللازمة لضرب اثنين بنجاح nعلى حدةn المصفوفات كما n ينمو بشكل كبير جدا. وقال تشو، الذي شارك أيضًا في تأليف ورقة بحثية صدرت في يناير/كانون الثاني 2024: "الهدف من هذا العمل هو معرفة مدى قربك من الرقم 2، وما إذا كان من الممكن تحقيق ذلك من الناحية النظرية".

التركيز بالليزر

في عام 1986، حقق ستراسن إنجازًا كبيرًا آخر عندما حقق نجاحًا كبيرًا أدخلت ما يسمى بطريقة الليزر لضرب المصفوفات. استخدمه ستراسن لتحديد قيمة عليا للأوميغا تبلغ 2.48. في حين أن الطريقة ليست سوى خطوة واحدة في عمليات ضرب المصفوفات الكبيرة، إلا أنها واحدة من أهم الخطوات لأن الباحثين استمروا في تحسينها.

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

إليك طريقة مبسطة للتفكير في كيفية تناسب هذه العناصر المختلفة معًا. لنبدأ بمصفوفتين كبيرتين، A وB، ترغبان في ضربهما معًا. أولاً، تقوم بتحليلها إلى العديد من المصفوفات الفرعية الأصغر، أو الكتل، كما يطلق عليها أحيانًا. بعد ذلك، يمكنك استخدام خوارزمية كوبرسميث ووينوغراد لتكون بمثابة دليل تعليمات للتعامل مع الكتل وتجميعها في النهاية. قالت فاسيليفسكا ويليامز: "إنها تخبرني بما يجب أن أضربه وما الذي يجب إضافته وما هي المدخلات التي تذهب إلى أين" في مصفوفة المنتج C. "إنها مجرد وصفة لبناء C من A وB."

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

هذا هو المكان الذي تلعب فيه طريقة الليزر Strassen أخيرًا. وقال لو غال: "عادة ما تعمل طريقة الليزر بشكل جيد للغاية وتجد بشكل عام طريقة جيدة لقتل مجموعة فرعية من الكتل لإزالة التداخل". بعد أن يزيل الليزر أو "يحرق" جميع التداخلات، يمكنك إنشاء مصفوفة المنتج النهائية، C.

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

وهذا التحليل هو ما أدى إلى أكبر تحسن في الأوميغا منذ أكثر من عقد من الزمن.

تم العثور على خسارة

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

تعمل طريقة الليزر عن طريق تصنيف الكتل المتداخلة على أنها قمامة، ومن المقرر التخلص منها؛ تعتبر الكتل الأخرى جديرة وسيتم حفظها. ومع ذلك، فإن عملية الاختيار تكون عشوائية إلى حد ما. في الواقع، قد يتبين أن الكتلة التي تم تصنيفها على أنها قمامة مفيدة بعد كل شيء. لم تكن هذه مفاجأة تامة، ولكن من خلال فحص العديد من هذه الاختيارات العشوائية، قرر فريق دوان أن طريقة الليزر تقلل من قيمة الكتل بشكل منهجي: يجب حفظ المزيد من الكتل ورمي عدد أقل. وكما هو الحال عادة، فإن تقليل النفايات يترجم إلى كفاءة أكبر.

وقال لو غال: "إن القدرة على الاحتفاظ بعدد أكبر من الكتل دون تداخل تؤدي إلى ... خوارزمية مضاعفة أسرع للمصفوفات".

وبعد إثبات وجود هذه الخسارة، قام فريق دوان بتعديل الطريقة التي صنفت بها طريقة الليزر الكتل، مما أدى إلى تقليل النفايات بشكل كبير. ونتيجة لذلك، فقد وضعوا حدًا أعلى جديدًا للأوميغا عند حوالي 2.371866 - وهو تحسن عن الحد الأعلى السابق البالغ 2.3728596. تعيين في عام 2020 بقلم جوش ألمان وفاسيليفسكا ويليامز. قد يبدو هذا بمثابة تغيير متواضع، حيث يخفض الحد بحوالي 0.001 فقط. ولكنه أكبر تحسن شهده العلماء منذ عام 2010. وبالمقارنة، تحسنت نتيجة فاسيليفسكا ويليامز وألمان لعام 2020 عن سابقتها بمقدار 0.00001 فقط.

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

وقد قامت ورقة يناير 2024 بتحسين هذا النهج الجديد، مما مكن فاسيليفسكا ويليامز وتشو والمؤلفين المشاركين من تقليل الخسارة الخفية بشكل أكبر. أدى هذا إلى تحسن إضافي في الحد الأعلى للأوميغا، مما أدى إلى خفضه إلى 2.371552. قام المؤلفون أيضًا بتعميم نفس الأسلوب لتحسين عملية الضرب للمستطيلات (nعلى حدةm) المصفوفات - إجراء له تطبيقات في نظرية الرسم البياني والتعلم الآلي ومجالات أخرى.

إن تحقيق المزيد من التقدم على هذا المنوال أمر مؤكد، ولكن هناك حدود. في عام 2015، لو غال واثنين من المتعاونين ثبت أن النهج الحالي - طريقة الليزر المقترنة بوصفة كوبرسميث-فينوغراد - لا يمكن أن ينتج أوميغا أقل من 2.3078. ولإجراء المزيد من التحسينات، قال لو غال، "أنت بحاجة إلى تحسين [النهج] الأصلي لكوبرسميث وفينوغراد الذي لم يتغير حقًا منذ عام 1987". لكن حتى الآن، لم يتوصل أحد إلى طريقة أفضل. قد لا يكون هناك حتى واحد.

وقال تشو: "إن تحسين الأوميغا هو في الواقع جزء من فهم هذه المشكلة". "إذا تمكنا من فهم المشكلة جيدًا، فيمكننا تصميم خوارزميات أفضل لها. [و] لا يزال الناس في المراحل المبكرة جدًا من فهم هذه المشكلة القديمة.