หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซอร์สโค้ดอื่น ๆ
ดาวน์โหลด

อัลกอริทึมเวลาสี่เท่าสำหรับการคูณเมทริกซ์ด้วยจำนวนเต็มบวก

ซอร์สโค้ดนี้ (ใน Python) เป็นการดำเนินการเบื้องต้นของการคูณเมทริกซ์จำนวนเต็มบวกระยะเวลาสี่เท่าของฉันซึ่งได้รับการพิสูจน์ทางทฤษฎีเกี่ยวกับเวลาและความซับซ้อนของอวกาศในหนึ่งใน preprints ของฉัน [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' นอกจากนี้ทั้งหมดนี้ฉันได้รวมการใช้งานแบบมัลติเธรดซึ่งเป็นตัวอย่างที่ดีของเซลล์หุ่นยนต์มือถือ การใช้งานตามการใช้งานของ CA ที่ผ่านการทดสอบจะแสดงใน 'camatrix_mult_test.py' การวิเคราะห์ความซับซ้อนของเวลาได้แสดงใน 'camatrix_mult.py'

การอ้างอิง

[1] S. Mohapatra, "วิธีการเชิงทฤษฎีจำนวนมากเพื่อเพิ่มประสิทธิภาพการคูณเมทริกซ์จำนวนเต็ม", [arxiv: 1806.03701], 2018

[2] V. Strassen, "การกำจัดแบบเกาส์ไม่ดีที่สุด", ตัวเลข คณิตศาสตร์. 13, p. 354-356, 1969

[3] D. Bini, M. Capovani, F. Romani และ G. Lotti "O (n^2.7799) ความซับซ้อนสำหรับการคูณเมทริกซ์โดยประมาณ n × n" Inf. กระบวนการ. Lett., pp. 234–235, 1979

[4] V. Strassen, "สเปกตรัม asymptotic ของเทนเซอร์และเลขชี้กำลังของการคูณเมทริกซ์", Proc 27th Ann. IEEE Symp เกี่ยวกับรากฐานของวิทยาศาสตร์คอมพิวเตอร์, หน้า 49-54, 1984

[5] D. Coppersmith, S. Winograd, "การคูณเมทริกซ์ผ่านความก้าวหน้าทางคณิตศาสตร์" J. Symbolic Comput pp. 251–280, 1980

[6] V. Williams, "การคูณเมทริกซ์เร็วกว่า Coppersmith-Winograd" ACM: pp.887–898, 2012

[7] F. Le Gall, "พลังของเทนเซอร์และการคูณเมทริกซ์เร็ว", Proc 39th int. ตัวแสดง เกี่ยวกับการคำนวณเชิงสัญลักษณ์และพีชคณิต 2014

ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด