ความก้าวหน้าครั้งใหม่ทำให้การคูณเมทริกซ์เข้าใกล้อุดมคติมากขึ้น นิตยสารควอนต้า

นักวิทยาศาสตร์คอมพิวเตอร์เป็นกลุ่มที่มีความต้องการสูง สำหรับพวกเขา การได้รับคำตอบที่ถูกต้องสำหรับปัญหานั้นไม่เพียงพอ เป้าหมายเกือบทุกครั้งคือการได้รับคำตอบอย่างมีประสิทธิภาพมากที่สุดเท่าที่จะเป็นไปได้

ทำการคูณเมทริกซ์หรืออาร์เรย์ของตัวเลข ในปี 1812 Jacques Philippe Marie Binet นักคณิตศาสตร์ชาวฝรั่งเศสได้คิดค้นกฎพื้นฐานที่เรายังคงสอนนักเรียนอยู่ มันทำงานได้อย่างสมบูรณ์แบบ แต่นักคณิตศาสตร์คนอื่นๆ ได้ค้นพบวิธีที่จะทำให้กระบวนการนี้ง่ายขึ้นและเร็วขึ้น ตอนนี้หน้าที่ของ เร่งกระบวนการ การคูณเมทริกซ์เป็นจุดตัดระหว่างคณิตศาสตร์และวิทยาการคอมพิวเตอร์ ซึ่งนักวิจัยยังคงปรับปรุงกระบวนการนี้มาจนถึงทุกวันนี้ แม้ว่าในทศวรรษที่ผ่านมา การเพิ่มขึ้นจะค่อนข้างน้อยก็ตาม ตั้งแต่ปี 1987 เป็นต้นมา การปรับปรุงเชิงตัวเลขในการคูณเมทริกซ์นั้น “มีขนาดเล็กและ … ได้มายากมาก” กล่าว ฟรองซัวส์ เลอ กัลนักวิทยาศาสตร์คอมพิวเตอร์จากมหาวิทยาลัยนาโกย่า

ขณะนี้นักวิจัยสามคน ได้แก่ Ran Duan และ Renfei Zhou จาก Tsinghua University และ Hongxun Wu จาก University of California, Berkeley ได้ก้าวไปข้างหน้าในการโจมตีปัญหาที่ยืนต้นนี้ ของพวกเขา ผลลัพธ์ใหม่ซึ่งนำเสนอเมื่อเดือนพฤศจิกายนปีที่แล้วที่การประชุม Foundations of Computer Science โดยมีต้นกำเนิดมาจากเทคนิคใหม่ที่ไม่คาดคิด Le Gall กล่าว แม้ว่าการปรับปรุงจะมีขนาดค่อนข้างเล็ก แต่ Le Gall เรียกมันว่า "แนวความคิดที่ใหญ่กว่าการปรับปรุงอื่นๆ ก่อนหน้านี้"

เทคนิคนี้เผยให้เห็นแหล่งที่มาของการปรับปรุงที่อาจเกิดขึ้นซึ่งไม่เคยมีใครรู้จักมาก่อนและยังไม่ได้ใช้ และได้เกิดผลแล้ว: กระดาษแผ่นที่สองซึ่งเผยแพร่ในเดือนมกราคม สร้างขึ้นจากตัวแรกเพื่อแสดงให้เห็นว่าการคูณเมทริกซ์สามารถเพิ่มประสิทธิภาพให้ดียิ่งขึ้นได้อย่างไร

“นี่คือความก้าวหน้าทางเทคนิคครั้งสำคัญ” กล่าว วิลเลียม คุสซ์มอลนักวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีแห่งมหาวิทยาลัยฮาร์วาร์ด “นี่เป็นการปรับปรุงครั้งใหญ่ที่สุดในการคูณเมทริกซ์ที่เราเคยเห็นในรอบกว่าทศวรรษ”

เข้าสู่เมทริกซ์

อาจดูเหมือนเป็นปัญหาที่ไม่ชัดเจน แต่การคูณเมทริกซ์เป็นการดำเนินการคำนวณขั้นพื้นฐาน มันถูกรวมเข้ากับอัลกอริธึมส่วนใหญ่ที่ผู้คนใช้ทุกวันสำหรับงานต่างๆ ตั้งแต่การแสดงคอมพิวเตอร์กราฟิกที่คมชัดยิ่งขึ้นไปจนถึงการแก้ปัญหาลอจิสติกส์ในทฤษฎีเครือข่าย และเช่นเดียวกับในด้านอื่น ๆ ของการคำนวณ ความเร็วเป็นสิ่งสำคัญยิ่ง การปรับปรุงแม้เพียงเล็กน้อยก็สามารถประหยัดเวลา พลังในการคำนวณ และเงินได้อย่างมากในที่สุด แต่สำหรับตอนนี้ นักทฤษฎีส่วนใหญ่สนใจที่จะคิดว่ากระบวนการนี้จะเร็วแค่ไหน

วิธีดั้งเดิมในการคูณสอง nAKbAr-byn เมทริกซ์ — โดยการคูณตัวเลขจากแต่ละแถวในเมทริกซ์แรกด้วยตัวเลขในคอลัมน์ในคอลัมน์ที่สอง — ต้องใช้ n³ การคูณแบบแยกกัน สำหรับเมทริกซ์ขนาด 2 คูณ 2 นั่นหมายถึง 2³ หรือการคูณ 8 ครั้ง

ในปี 1969 นักคณิตศาสตร์ โวลเกอร์ สตราสเซน เปิดเผยขั้นตอนที่ซับซ้อนมากขึ้นซึ่งสามารถคูณเมทริกซ์ขนาด 2 x 2 ได้โดยใช้ขั้นตอนการคูณ 18 ขั้นตอนและการบวก 2 ขั้นตอน สองปีต่อมา นักวิทยาศาสตร์คอมพิวเตอร์ ชมูเอล วิโนกราด แสดงให้เห็นว่าจริงๆ แล้ว เจ็ดคือค่าต่ำสุดสัมบูรณ์สำหรับเมทริกซ์ขนาด 2 คูณ XNUMX

Strassen ใช้ประโยชน์จากแนวคิดเดียวกันนี้เพื่อแสดงให้เห็นว่าใหญ่กว่าทั้งหมด nAKbAr-byn เมทริกซ์สามารถคูณได้น้อยกว่าด้วย n³ ขั้นตอน องค์ประกอบสำคัญในกลยุทธ์นี้เกี่ยวข้องกับขั้นตอนที่เรียกว่าการสลายตัว โดยแบ่งเมทริกซ์ขนาดใหญ่ออกเป็นเมทริกซ์ย่อยที่มีขนาดเล็กลงตามลำดับ ซึ่งอาจท้ายที่สุดจะมีขนาดเล็กเพียง 2 คูณ 2 หรือแม้กระทั่ง 1 คูณ 1 (ซึ่งเป็นเพียงตัวเลขเดี่ยว)

เหตุผลในการแบ่งอาเรย์ขนาดยักษ์ออกเป็นชิ้นเล็กๆ นั้นค่อนข้างง่าย เวอร์จิเนีย วาสซิเลฟสกา วิลเลียมส์นักวิทยาศาสตร์คอมพิวเตอร์ที่สถาบันเทคโนโลยีแมสซาชูเซตส์และเป็นผู้เขียนร่วมในรายงานฉบับใหม่ “มันยากสำหรับมนุษย์ที่จะมองเมทริกซ์ขนาดใหญ่ (เช่น ตามลำดับ 100 x 100) และคิดถึงอัลกอริทึมที่ดีที่สุดเท่าที่จะเป็นไปได้” Vassilevska Williams กล่าว แม้แต่เมทริกซ์ขนาด 3 คูณ 3 ก็ยังไม่ได้รับการแก้ไขอย่างสมบูรณ์ “อย่างไรก็ตาม เราสามารถใช้อัลกอริธึมที่รวดเร็วซึ่งเราได้พัฒนาไว้แล้วสำหรับเมทริกซ์ขนาดเล็ก เพื่อให้ได้อัลกอริธึมที่รวดเร็วสำหรับเมทริกซ์ขนาดใหญ่ด้วย”

กุญแจสำคัญในการเร่งความเร็ว นักวิจัยได้กำหนดไว้คือการลดจำนวนขั้นตอนการคูณ โดยลดเลขชี้กำลังนั้นลง n³ (สำหรับวิธีมาตรฐาน) ให้มากที่สุดเท่าที่จะทำได้ ค่าต่ำสุดที่เป็นไปได้ n²โดยพื้นฐานแล้วตราบใดที่ต้องใช้เวลาในการเขียนคำตอบ นักวิทยาศาสตร์คอมพิวเตอร์เรียกเลขชี้กำลังนั้นว่า omega, ω, with n^ω เป็นขั้นตอนน้อยที่สุดที่จำเป็นในการคูณสองให้สำเร็จ nAKbAr-byn เมทริกซ์เป็น n เติบโตขึ้นอย่างมาก “จุดประสงค์ของงานนี้” โจว ผู้ร่วมเขียนรายงานฉบับเดือนมกราคม 2024 กล่าว “คือการดูว่าคุณสามารถเข้าใกล้ 2 ได้แค่ไหน และในทางทฤษฎีจะทำสำเร็จหรือไม่”

เลเซอร์โฟกัส

ในปี 1986 Strassen มีความก้าวหน้าครั้งใหญ่อีกครั้งเมื่อเขา แนะนำ วิธีที่เรียกว่าวิธีเลเซอร์สำหรับการคูณเมทริกซ์ Strassen ใช้เพื่อสร้างค่าบนของโอเมก้าที่ 2.48 แม้ว่าวิธีนี้จะเป็นเพียงขั้นตอนเดียวในการคูณเมทริกซ์ขนาดใหญ่ แต่ก็เป็นหนึ่งในขั้นตอนที่สำคัญที่สุดเนื่องจากนักวิจัยได้ปรับปรุงอย่างต่อเนื่อง

หนึ่งปีต่อมา Winograd และ Don Coppersmith ได้เปิดตัวอัลกอริธึมใหม่ที่ช่วยเสริมวิธีการเลเซอร์ได้อย่างสวยงาม การรวมกันของเครื่องมือนี้มีส่วนสำคัญในความพยายามที่ตามมาเกือบทั้งหมดในการเร่งการคูณเมทริกซ์

ต่อไปนี้เป็นวิธีคิดง่ายๆ ว่าองค์ประกอบต่างๆ เหล่านี้เข้ากันได้อย่างไร เริ่มจากเมทริกซ์ขนาดใหญ่สองตัว A และ B ที่คุณต้องการคูณเข้าด้วยกัน ขั้นแรก คุณแยกพวกมันออกเป็นเมทริกซ์ย่อยหรือบล็อกเล็กๆ หลายๆ ชิ้น ตามที่บางครั้งเรียกว่า จากนั้น คุณสามารถใช้อัลกอริธึมของ Coppersmith และ Winograd เพื่อทำหน้าที่เป็นคู่มือการใช้งานประเภทหนึ่งสำหรับการจัดการและการประกอบบล็อกในท้ายที่สุด “มันบอกฉันว่าต้องคูณอะไร และจะเพิ่มอะไร และรายการใดไปอยู่ที่ไหน” ในเมทริกซ์ผลิตภัณฑ์ C, Vassilevska Williams กล่าว “มันเป็นเพียงสูตรในการสร้าง C จาก A และ B”

อย่างไรก็ตาม มีข้อเสียอยู่บ้าง: บางครั้งคุณจะพบกับบล็อกที่มีรายการเหมือนกัน การปล่อยสิ่งเหล่านี้ไว้ในผลิตภัณฑ์จะคล้ายกับการนับรายการเหล่านั้นสองครั้ง ดังนั้น ณ จุดหนึ่ง คุณจำเป็นต้องกำจัดคำที่ซ้ำกันเหล่านั้น ซึ่งเรียกว่าการทับซ้อนกัน นักวิจัยทำเช่นนี้โดยการ "ฆ่า" บล็อกที่พวกเขาอยู่ โดยตั้งค่าส่วนประกอบให้เท่ากับศูนย์เพื่อลบออกจากการคำนวณ

นั่นคือจุดที่วิธีการเลเซอร์ของ Strassen เข้ามามีบทบาทในที่สุด “วิธีการเลเซอร์มักจะทำงานได้ดีมากและโดยทั่วไปจะพบวิธีที่ดีในการทำลายบล็อกย่อยเพื่อกำจัดส่วนที่ทับซ้อนกัน” Le Gall กล่าว หลังจากที่เลเซอร์กำจัดหรือ "เผาไหม้" การทับซ้อนกันทั้งหมดแล้ว คุณสามารถสร้างเมทริกซ์ผลิตภัณฑ์ขั้นสุดท้าย C ได้

การนำเทคนิคต่างๆ เหล่านี้มารวมกันจะทำให้เกิดอัลกอริธึมสำหรับการคูณเมทริกซ์สองตัวด้วยจำนวนการคูณโดยรวมที่จงใจ อย่างน้อยก็ในทางทฤษฎี วิธีการเลเซอร์ไม่ได้ตั้งใจให้ใช้งานได้จริง มันเป็นเพียงวิธีคิดหาวิธีที่ดีที่สุดในการคูณเมทริกซ์ “เราไม่เคยใช้วิธีนี้ [บนคอมพิวเตอร์]” โจวกล่าว “เราวิเคราะห์มัน”

และการวิเคราะห์นั้นคือสิ่งที่นำไปสู่การพัฒนาโอเมก้าครั้งใหญ่ที่สุดในรอบกว่าทศวรรษ

พบการสูญเสีย

บทความเมื่อฤดูร้อนที่แล้วโดย Duan, Zhou และ Wu แสดงให้เห็นว่ากระบวนการของ Strassen ยังคงสามารถเร่งความเร็วได้อย่างมีนัยสำคัญ ทั้งหมดนี้เป็นเพราะแนวคิดที่พวกเขาเรียกว่าการสูญเสียที่ซ่อนอยู่ ซึ่งฝังลึกอยู่ในการวิเคราะห์ก่อนหน้านี้ “เป็นผลมาจากการฆ่าบล็อกมากเกินไปโดยไม่ได้ตั้งใจ” Zhou กล่าว

วิธีการเลเซอร์ทำงานโดยการติดฉลากบล็อกที่ทับซ้อนกันว่าเป็นขยะซึ่งกำหนดให้นำไปกำจัด บล็อกอื่นถือว่าคุ้มค่าและจะได้รับการบันทึกไว้ อย่างไรก็ตาม กระบวนการคัดเลือกค่อนข้างสุ่ม บล็อกที่ได้รับการจัดอันดับว่าเป็นขยะ แท้จริงแล้วกลับกลายเป็นว่ามีประโยชน์ นี่ไม่ใช่เรื่องน่าแปลกใจเลย แต่จากการตรวจสอบตัวเลือกแบบสุ่มเหล่านี้ ทีมงานของ Duan พบว่าวิธีการเลเซอร์นั้นมีการประเมินมูลค่าบล็อกต่ำเกินไปอย่างเป็นระบบ กล่าวคือ ควรเก็บบล็อกให้มากขึ้น และโยนทิ้งให้น้อยลง และตามปกติแล้ว ของเสียที่น้อยลงจะทำให้มีประสิทธิภาพมากขึ้น

“ความสามารถในการเก็บบล็อกได้มากขึ้นโดยไม่ทับซ้อนกันจึงนำไปสู่ ​​… อัลกอริธึมการคูณเมทริกซ์ที่เร็วขึ้น” Le Gall กล่าว

หลังจากพิสูจน์การมีอยู่ของการสูญเสียนี้แล้ว ทีมงานของ Duan ได้ปรับเปลี่ยนวิธีที่วิธีเลเซอร์ติดป้ายกำกับบล็อก ช่วยลดของเสียได้อย่างมาก ด้วยเหตุนี้ พวกเขาจึงกำหนดขอบเขตบนใหม่สำหรับโอเมก้าที่ประมาณ 2.371866 ซึ่งเพิ่มขึ้นจากขอบเขตบนก่อนหน้าที่ 2.3728596 ตั้งในปี 2020 โดย Josh Alman และ Vassilevska Williams นั่นอาจดูเหมือนเป็นการเปลี่ยนแปลงเล็กน้อย โดยลดขอบเขตลงเพียงประมาณ 0.001 แต่นี่เป็นการปรับปรุงครั้งใหญ่ที่สุดที่นักวิทยาศาสตร์เคยเห็นมาตั้งแต่ปี 2010 เมื่อเปรียบเทียบกันแล้ว ผลลัพธ์ในปี 2020 ของ Vassilevska Williams และ Alman ปรับปรุงจากรุ่นก่อนเพียง 0.00001 เท่านั้น

แต่สิ่งที่น่าตื่นเต้นที่สุดสำหรับนักวิจัยไม่ใช่แค่เพียงสถิติใหม่เท่านั้น ซึ่งอยู่ได้ไม่นาน นอกจากนี้ ยังเป็นข้อเท็จจริงที่ว่าบทความนี้ได้เปิดเผยแนวทางใหม่ในการปรับปรุง ซึ่งจนถึงตอนนั้นไม่มีใครสังเกตเห็นโดยสิ้นเชิง เป็นเวลาเกือบสี่ทศวรรษแล้วที่ทุกคนพึ่งพาวิธีการเลเซอร์แบบเดียวกัน Le Gall กล่าว “แล้วพวกเขาก็พบว่า เอาล่ะ เราทำได้ดีกว่านี้”

รายงานฉบับเดือนมกราคม พ.ศ. 2024 ได้ปรับปรุงแนวทางใหม่นี้ โดยช่วยให้ Vassilevska Williams, Zhou และผู้เขียนร่วมสามารถลดการสูญเสียที่ซ่อนอยู่เพิ่มเติมได้ สิ่งนี้นำไปสู่การปรับปรุงขอบเขตบนของโอเมก้าเพิ่มเติม โดยลดลงเหลือ 2.371552 ผู้เขียนยังได้สรุปเทคนิคเดียวกันนี้ในการปรับปรุงกระบวนการคูณของรูปสี่เหลี่ยมผืนผ้า (nAKbAr-bym) เมทริกซ์ — กระบวนการที่มีการประยุกต์ในทฤษฎีกราฟ การเรียนรู้ของเครื่อง และด้านอื่นๆ

ความคืบหน้าเพิ่มเติมบางประการในบรรทัดเหล่านี้ล้วนแต่มีความแน่นอน แต่ก็มีข้อจำกัด ในปี 2015 Le Gall และผู้ร่วมงานสองคน พิสูจน์แล้วว่า วิธีการปัจจุบัน — วิธีเลเซอร์ควบคู่กับสูตร Coppersmith-Winograd — ไม่สามารถให้โอเมก้าต่ำกว่า 2.3078 ได้ เพื่อทำการปรับปรุงเพิ่มเติม Le Gall กล่าวว่า “คุณต้องปรับปรุงตาม [แนวทาง] ดั้งเดิมของ Coppersmith และ Winograd ที่ไม่มีการเปลี่ยนแปลงจริงๆ ตั้งแต่ปี 1987". แต่จนถึงขณะนี้ยังไม่มีใครคิดวิธีที่ดีกว่านี้ได้ อาจจะไม่มีเลยด้วยซ้ำ

“การปรับปรุงโอเมก้าเป็นส่วนหนึ่งของการทำความเข้าใจปัญหานี้จริงๆ” โจวกล่าว “หากเราเข้าใจปัญหาได้ดี เราก็สามารถออกแบบอัลกอริธึมที่ดีขึ้นสำหรับปัญหานั้นได้ [และ] ผู้คนยังอยู่ในช่วงเริ่มต้นของการทำความเข้าใจปัญหาเก่าแก่นี้”