multi_dot: لماذا يختلف الناتج عند تغيير الأقواس؟

الأقواس غير ترتيب العوامل

multi_dot تختار تجميعًا أمثل لأقواس سلسلة الضرب؛ لا يلزم أن تتبع الأقواس التي كتبتها يدويًا. [1]

dot مع مدخلين ثنائيي الأبعاد تحسب ضرب مصفوفتين. [2]

نحافظ على القائمة A ثم B ثم C في الطلبين. التجميع (AB)C يبدأ بـ A و B، ثم يضرب الناتج في C؛ أما A(BC) فيبدأ بـ B و C. لم ننقل مصفوفة إلى مكان آخر، ولم نضف محورًا أو نحذفه.

في هذا المقال كل عامل ثنائي الأبعاد، والاستدعاءات كلها تنجح. نسأل عن القيمة التي أعادها كل مسار في حساب عائم؛ لا نختبر صلاحية متجه أحادي البعد في منتصف السلسلة.

صفر وواحد من المدخلات نفسها

في مثال float64: ‏A بالشكل (1,2)، و B بالشكل (2,3)، و C بالشكل (3,1)؛ أعادت (AB)C القيمة 0، و A(BC) و multi_dot القيمة 1، بالشكل (1,1).

عدّ ضربات الحساب المدرسي أعطى 9 للتجميع اليساري و 8 لليميني؛ لم نقس زمن التنفيذ، والعدد الأقل ليس معيار دقة عامًا.

import numpy as np A=np.array([[2**54,1]],dtype=np.float64) B=np.array([[1,-1,0],[1,0,0]],dtype=np.float64) C=np.array([[1],[1],[1]],dtype=np.float64) L=np.dot(np.dot(A,B),C) R=np.dot(A,np.dot(B,C)) M=np.linalg.multi_dot([A,B,C])

على NumPy 2.3.5 و CPython 3.12.14 كانت L=[[0.0]] و R=M=[[1.0]]. الثلاثة من float64 وبالشكل (1,1). نسمي H=2**54؛ قيمته الصحيحة 18014398509481984، وهو العدد الكبير الذي اخترناه للمثال.

في المرجع الصحيح، حاصل AB هو [[H+1,-H,0]]. جمع خاناته مع العمود C يعطي (H+1)-H+0=1. أما الحاصل العائم المسجل لـ AB فكان [[H,-H,0.0]]؛ لم يحتفظ هذا الوسيط بالزيادة 1 في الخانة الأولى، وأعطى الضرب التالي 0.

بالتجميع اليميني كان BC=[[0.0],[1.0]]، لأن الصف الأول يعطي 1-1+0=0 والصف الثاني يعطي 1+0+0=1. ثم A(BC) تجمع H×0+1×1=1 في المرجع، وأعادت 1 في التشغيل. وافقت multi_dot هذا المسار على هذه المدخلات.

صيغة كلفة ضرب مصفوفة m×k في k×n هي mkn ضربات عددية في هذا النموذج الحسابي. [1]

للتجميع اليساري: ضرب 1×2 في 2×3 يعد 6 ضربات، ثم ضرب 1×3 في 3×1 يعد 3؛ المجموع 9. لليميني: ضرب 2×3 في 3×1 يعد 6، ثم ضرب 1×2 في 2×1 يعد 2؛ المجموع 8. لا يدخل في هذا العد الجمع أو إدارة الذاكرة أو زمن المكتبة.

فرق 8 عن 9 يخص تنظيم هذه الأبعاد، وفرق 1 عن 0 يخص الأعداد والمسارات المنفذة هنا. لا نجعل الاتفاق مع المرجع الصحيح هدفًا مضمونًا لاختيار الأقواس الأمثل، ولا نحول عدّ الضربات إلى قياس سرعة.

تحكم بالأعداد الأصغر

تحكم باستبدال 2**54 بـ 2**20 أعطى 1 في المسارات الثلاثة؛ اتفاق التحكم لم يلغ فرق المثال الكبير.

أبقينا B و C والأشكال وترتيب العوامل، وغيرنا الخانة الكبيرة في A فقط إلى 1048576. سجل AB العائم حينها [[1048577.0,-1048576.0,0.0]]؛ بقيت الزيادة 1 موجودة في الوسيط.

أعادت L و R و M في التحكم [[1.0]] من float64 وبالشكل (1,1). ظلت كلفتا العد 9 و 8 لأن الأبعاد لم تتغير؛ اختلاف الاتفاق بين المثال والتحكم لم ينتج عن تعديل الأشكال.

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

مرجع صحيح وحدود الفحوص

مرت 31 مقارنة تشمل أربع حالات كبيرة والتحكم الصغير وعدّ الضربات؛ النطاق هذه الأشكال و float64 على التشغيل المسجل، دون ضمان دقة أو سرعة عام.

بنينا المرجع من قوائم Python وأعداد صحيحة. لكل خانة نضرب عناصر الصف والعمود المناظرة ونجمعها بحلقة مفهرسة، ثم نطبق الدالة على التجميعين. لم نستخدم dot أو multi_dot لصنع الإجابة المتوقعة؛ أعاد المرجعان [[1]].

فحصنا الحالة الرئيسية بالأس 54 وثلاث حالات بالأسس 55 و 56 و 57، إضافة إلى التحكم بالأس 20. مع الأسس الكبيرة المسجلة كانت L صفرًا و R و M واحدًا؛ مع الأس 20 كانت كلها واحدًا. بقيت بايتات A و B و C دون تغيير.

لكل حالة ست مقارنات: قيم L، وقيم R، وقيم M؛ أنواع النواتج وأشكالها وأشكال الوسيطين؛ ثبات المدخلات؛ واتفاق التجميعين الصحيحين مع [[1]]. بذلك 5×6=30؛ وأضفنا مقارنة لعدّ 9 و 8، فصار المجموع 31.

عدّادنا الأخير يمر على مواضع الصف والعمود والفهرس الداخلي ويعد كل حاصل ضرب في المسارين. هذا يعد عمل النموذج المدرسي؛ لم نراقب تعليمات المعالج أو نقيس مدة الاستدعاء أو نفحص قرارًا داخليًا للمكتبة.

استبعدنا out والدفعات والمركبة والأشكال الأخرى والسلاسل الأطول وقواعد فك التعادل والأنظمة الأخرى. سجّل الأقواس والقيم والأشكال حين تقارن مسارين، وراجع أثر الأعداد نفسها بدل الاستدلال من تساوي التعبير في حساب صحيح على تطابقه العائم.