الصفحة الرئيسية>المتعلقة بالبرمجة>شفرة المصدر الأخرى
تنزيل

خوارزمية الوقت التربيعي لضرب المصفوفة مع الأعداد الصحيحة الإيجابية

هذا الكود المصدر (في Python) هو تنفيذ أولي لضرب مصفوفة عدد صحيح إيجابي في الوقت التربيعي الذي ثبت نظريًا عن تعقيدها ومساحة الفضاء في أحد المطبوعات المسبقة [1]. كانت هناك العديد من المقترحات حول تحسينات الخوارزمية الفرعية منذ تحسين النسخة المتكررة بواسطة Strassen (تشغيل في O (n^log2 (7)) = O (n^2.807)) [2] ، مثل Bini et al. (الجري في O (n^2.78))) [3] ، واحد آخر من قبل strassen (الجري في O (n^2.479)) [4] ، بواسطة coppersmith و winograd (الجري في O (n^2.375)) [5] ، بواسطة Williams (تشغيل في O (n^2.3729)) [6] [7]. لكن جميعها سليمة من الناحية النظرية ولكنها لا يمكن تنفيذها عمليًا بسبب هياكل البيانات الثقيلة مثل قوى التوتر. تم عرض الخلفية النظرية وإثباتها على صوابها بناءً على الأساليب النظرية لعدد [1]. ملف "matrix_multiply_test.py" هو في الأساس ملف اختبار الوحدة الذي يثبت عملياً صحة طريقتي. ولكن تم تصميم هذه الطريقة واختبارها فقط للأعداد الصحيحة الإيجابية ، والتي يمكن تعديلها بشكل مناسب لتناسب الحالات ذات الأعداد الصحيحة السلبية والأرقام العائمة والأرقام المعقدة أيضًا. تم عرض التنفيذ الفعلي للخوارزمية في ملف 'matrix_multiply_quadratic.py'. إلى جانب كل هذا ، قمت بتضمين تطبيق متعدد الخيوط وهو مثال جيد حقًا على Automaton الخلوي. يتم عرض النسخة المختبرة من التنفيذ القائم على CA في "Camatrix_Mult_Test.py". تم عرض تحليل التعقيد الوقت في "camatrix_mult.py".

مراجع

[1] S. Mohapatra ، "الطريقة النظرية العدد التلافييل لتحسين مضاعفة مصفوفة عدد صحيح" ، [Arxiv: 1806.03701] ، 2018

[2] V. Strassen ، "Gaussian Delination ليس الأمثل" ، العدد. الرياضيات. 13 ، ص. 354-356 ، 1969

[3] D. Bini ، M. Capovani ، F. Romani ، and G. Lotti. "O (n^2.7799) التعقيد لضرب المصفوفة التقريبية n × n" inf. عملية. Lett. ، pp. 234–235 ، 1979

[4 " 27 آن. IEEE SYMP. على أسس علوم الكمبيوتر ، الصفحات 49-54 ، 1984

[5] D. Coppersmith ، S. Winograd ، "مضاعفة المصفوفة عبر تقدم الحساب". J. Comput. ص. 251-280 ، 1980

[6] V. Williams ، "مضاعفة المصفوفات أسرع من Coppersmith-Winograd". ACM: pp.887–898 ، 2012

[7] F. Le Gall ، "Powers of Tensors and Fast Matrix Multiplication" ، Proc. 39th int. سيمب. على الحساب الرمزي والجبر ، 2014

يوسع
معلومات إضافية
تطبيقات ذات صلة
نوصي لك
أخبار ذات صلة الكل