เนื่องจากการคูณเมทริกซ์เป็นการดำเนินการหลักในอัลกอริทึมเชิงตัวเลข จำนวนมาก จึงมีการลงทุนอย่างมากในการพัฒนาอัลกอริทึมการคูณเมทริกซ์ให้มีประสิทธิภาพ การประยุกต์ใช้การคูณเมทริกซ์ในปัญหาการคำนวณพบได้ในหลายสาขา รวมถึงการคำนวณทางวิทยาศาสตร์และการรู้จำรูปแบบและในปัญหาที่ดูเหมือนไม่เกี่ยวข้องกัน เช่น การนับเส้นทางผ่านกราฟ[ ^{1 ] มี}การออกแบบอัลกอริทึมที่แตกต่างกันมากมายสำหรับการคูณเมทริกซ์บนฮาร์ดแวร์ประเภทต่างๆ รวมถึง ระบบ ขนานและ ระบบ กระจายซึ่งงานคำนวณจะกระจายไปทั่วโปรเซสเซอร์หลายตัว (อาจจะผ่านเครือข่าย)

การใช้นิยามทางคณิตศาสตร์ของการคูณเมทริกซ์โดยตรงทำให้ได้อัลกอริทึมที่ใช้เวลา ใน การคูณเมทริกซ์n × n สอง เมทริกซ์บนฟิลด์นั้นในลำดับของ การดำเนินการ ฟิลด์n ³ ( Θ( n ³ )ในสัญกรณ์ O ใหญ่ ) ขอบเขตเชิงอะซิมโทติก ที่ดีกว่า สำหรับเวลาที่จำเป็นในการคูณเมทริกซ์เป็นที่รู้จักกันมาตั้งแต่อัลกอริทึมของ Strassenในช่วงทศวรรษ 1960 แต่เวลาที่เหมาะสมที่สุด (นั่นคือความซับซ้อนในการคำนวณของการคูณเมทริกซ์ ) ยังคงไม่เป็นที่รู้จัก ณ เดือนกันยายน 2025 ขอบเขตที่ดีที่สุดของความซับซ้อนเชิงอะซิมโทติกของอัลกอริทึมการคูณเมทริกซ์คือ เวลา O( n ^2.371339 )ซึ่งกำหนดโดย Alman, Duan, Williams , Xu, Xu และ Zhou ^{[ 2 ]}อย่างไรก็ตาม อัลกอริทึมนี้เป็นอัลกอริทึมกาแล็กซีเนื่องจากค่าคงที่ขนาดใหญ่และไม่สามารถนำไปใช้ได้จริง

นิยามของการคูณเมทริกซ์คือ ถ้าC = ABสำหรับเมทริกซ์A ขนาด n × mและเมทริกซ์B ขนาด m × pแล้วCจะเป็น เมทริกซ์ขนาด n × pที่มีสมาชิกดังนี้

${\displaystyle c_{ij}=\sum _{k=1}^{m}a_{ik}b_{kj}.}$

จากนี้ เราสามารถสร้าง อัลกอริธึมอย่างง่ายที่วนซ้ำตามดัชนีiตั้งแต่ 1 ถึงnและjตั้งแต่ 1 ถึงpโดยคำนวณค่าข้างต้นโดยใช้ลูปซ้อนกัน:

อัลกอริทึมนี้ใช้เวลาΘ( nmp ) (ในสัญกรณ์เชิงอะซิมโทติก ) ^{[ 1 ]}การลดรูปทั่วไปเพื่อวัตถุประสงค์ในการวิเคราะห์อัลกอริทึมคือการสมมติว่าอินพุตทั้งหมดเป็นเมทริกซ์จัตุรัสขนาดn × nซึ่งในกรณีนี้เวลาในการทำงานคือΘ( n ³ )กล่าวคือ เป็นกำลังสามตามขนาดของมิติ^{[ 3 ]}

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

โดยเฉพาะอย่างยิ่ง ในกรณีอุดมคติของแคชแบบเชื่อมโยงอย่างสมบูรณ์ซึ่งประกอบด้วยMไบต์และbไบต์ต่อบรรทัดแคช (เช่น⁠เอ็ม/ข(แคชไลน์) อัลกอริทึมข้างต้นจึงไม่เหมาะสมที่สุดสำหรับAและBที่จัดเก็บในลำดับแถวหลัก เมื่อn > ⁠เอ็ม/ขในแต่ละรอบของการวนซ้ำภายใน (การกวาดผ่านแถวของ Aและคอลัมน์ของ B พร้อมกัน ) จะเกิดแคชมิสเมื่อเข้าถึงองค์ประกอบของ B ซึ่งหมายความว่าอัลกอริทึมจะเกิดแคชมิส Θ(n³) ในกรณีที่เลว^ร้ายที่สุด ณ ปี 2010 ความเร็วของหน่วยความจำเมื่อเทียบกับโปรเซสเซอร์นั้นทำให้แคชมิสเป็นตัวกำหนดเวลาการทำงานมากกว่าการคำนวณจริงสำหรับเมทริกซ์ขนาดใหญ่ ^{[ 4 ]}

รูปแบบที่เหมาะสมที่สุดของอัลกอริธึมแบบวนซ้ำสำหรับAและBในเลย์เอาต์แบบแถวหลักคือ เวอร์ชัน แบบไทล์โดยที่เมทริกซ์จะถูกแบ่งโดยปริยายเป็นไทล์สี่เหลี่ยมจัตุรัสขนาด√ M x √ M : ^{[ 4 ] [ 5 ]}

ในแบบจำลองแคชในอุดมคติ อัลกอริทึมนี้ก่อให้เกิดค่าใช้จ่ายเพียงΘ( ⁠n ³/b √ M⁠ )แคชพลาด; ตัวหาร b √ Mมีค่าหลายลำดับขนาดบนเครื่องสมัยใหม่ ดังนั้นการคำนวณจริงจึงครอบงำเวลาการทำงานมากกว่าแคชพลาด ^{[ 4 ]}

ทางเลือกอื่นนอกเหนือจากอัลกอริธึมแบบวนซ้ำคือ อัลกอริธึ มแบบแบ่งและพิชิตสำหรับการคูณเมทริกซ์ ซึ่งอาศัยการแบ่งส่วนเป็นบล็อก

${\displaystyle C={\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}},\,A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}},\,B={\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}},}$

^{ซึ่งใช้ได้กับเมทริกซ์จัตุรัสทุกเมทริกซ์ที่มีมิติเป็นกำลังของสอง กล่าว}คือ รูปทรงเป็น2n × ²ⁿสำหรับn บาง ค่า ผลคูณของเมทริกซ์จึงเป็นดังนี้

${\displaystyle {\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}}{\begin{pmatrix}B_{11}&B_{12}\\B_{21}& B_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}}$

ซึ่งประกอบด้วยการคูณคู่ของเมทริกซ์ย่อยแปดครั้ง ตามด้วยขั้นตอนการบวก อัลกอริทึมแบบแบ่งและพิชิตจะคำนวณการคูณที่เล็กกว่าแบบเรียกซ้ำโดยใช้การคูณสเกลาร์c ₁₁ = a ₁₁ b ₁₁เป็นกรณีพื้นฐาน

ความซับซ้อนของอัลกอริทึมนี้เป็นฟังก์ชันของnถูกกำหนดโดยความสัมพันธ์เวียนเกิด^{[ 3 ]}

${\displaystyle T(1)=\Theta (1);}$

${\displaystyle T(n)=8T(n/2)+\Theta (n^{2}),}$

โดยคำนึงถึงการเรียกซ้ำแปดครั้งบนเมทริกซ์ขนาดn /2และΘ( n ² )เพื่อรวมเมทริกซ์ผลลัพธ์สี่คู่แบบองค์ประกอบต่อองค์ประกอบ การประยุกต์ใช้ทฤษฎีบทหลักสำหรับการแบ่งและพิชิตแบบเวียนเกิดแสดงให้เห็นว่าการเวียนเกิดนี้มีคำตอบΘ( n ³ )เช่นเดียวกับอัลกอริทึมแบบวนซ้ำ^{[ 3 ]}

อัลกอริทึมรูปแบบหนึ่งที่ใช้ได้กับเมทริกซ์ที่มีรูปร่างตามอำเภอใจและเร็วกว่าในทางปฏิบัติ^{[ 4 ]}จะแบ่งเมทริกซ์ออกเป็นสองส่วนแทนที่จะเป็นสี่ส่วนย่อย ดังนี้^{[ 6 ]} การแบ่งเมทริกซ์ในตอนนี้หมายถึงการแบ่งเมทริกซ์ออกเป็นสองส่วนที่มีขนาดเท่ากัน หรือมีขนาดใกล้เคียงกันมากที่สุดเท่าที่จะเป็นไปได้ในกรณีที่มิติเป็นเลขคี่

อัตราการพลาดแคชของการคูณเมทริกซ์แบบเรียกซ้ำจะเท่ากับของ เวอร์ชันแบบวนซ้ำ แบบเรียงต่อกันแต่ต่างจากอัลกอริทึมนั้นตรงที่อัลกอริทึมแบบเรียกซ้ำไม่คำนึงถึงแคช^{[ 6 ]}ไม่จำเป็นต้องมีพารามิเตอร์การปรับแต่งใดๆ เพื่อให้ได้ประสิทธิภาพแคชที่ดีที่สุด และทำงานได้ดีใน สภาพแวดล้อม มัลติโปรแกรมมิ่งที่ขนาดแคชเป็นแบบไดนามิกเนื่องจากกระบวนการอื่นๆ ใช้พื้นที่แคช^{[ 4 ]} (อัลกอริทึมแบบวนซ้ำอย่างง่ายก็ไม่คำนึงถึงแคชเช่นกัน แต่ในทางปฏิบัติจะช้ากว่ามากหากรูปแบบเมทริกซ์ไม่เหมาะกับอัลกอริทึม)

จำนวนแคชพลาดที่เกิดขึ้นจากอัลกอริทึมนี้ บนเครื่องที่มี แคชในอุดมคติ Mบรรทัด แต่ละบรรทัดมีขนาดbไบต์ จะถูกจำกัดโดย^{[ 6 ] : 13}

${\displaystyle \Theta \left(m+n+p+{\frac {mn+np+mp}{b}}+{\frac {mnp}{b{\sqrt {M}}}}\right)}$

มีอัลกอริทึมที่ให้เวลาการทำงานที่ดีกว่าอัลกอริทึมแบบตรงไปตรงมา อัลกอริทึมแรกที่ถูกค้นพบคืออัลกอริทึมของ Strassenซึ่งคิดค้นโดยVolker Strassenในปี 1969 และมักถูกเรียกว่า "การคูณเมทริกซ์แบบเร็ว" อัลกอริทึมนี้มีพื้นฐานมาจากวิธีการคูณเมทริกซ์ 2×2 สองเมทริกซ์ซึ่งต้องใช้การคูณเพียง 7 ครั้ง (แทนที่จะเป็น 8 ครั้งตามปกติ) โดยแลกกับการดำเนินการ บวกและ ลบ เพิ่มเติมหลายครั้ง การใช้อัลกอริทึมนี้แบบเรียกซ้ำจะให้ต้นทุนการคูณเท่ากับ อัลกอริทึมของ Strassen มีความซับซ้อนกว่า และความเสถียรเชิงตัวเลขลดลงเมื่อเทียบกับอัลกอริทึมแบบง่าย^{[ 7 ]}แต่จะเร็วกว่าในกรณีที่n > 100หรือประมาณนั้น^{[ 1 ]}และปรากฏในไลบรารีหลายแห่ง เช่นBLAS [ ^{8 ]}มีประโยชน์มากสำหรับเมทริกซ์ขนาดใหญ่บนโดเมนที่แน่นอน เช่น^{ฟิลด์}จำกัดซึ่งความเสถียรเชิงตัวเลขไม่ใช่ปัญหา ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$

เนื่องจากอัลกอริทึมของ Strassen ถูกนำไปใช้จริงในซอฟต์แวร์เชิงตัวเลขและระบบพีชคณิตคอมพิวเตอร์การปรับปรุงค่าคงที่ที่ซ่อนอยู่ในสัญกรณ์ Big-O จึงมีข้อดี ตารางต่อไปนี้เปรียบเทียบแง่มุมสำคัญของเวอร์ชันที่ปรับปรุงแล้วโดยอิงจากการคูณแบบเวียนซ้ำของเมทริกซ์บล็อก 2×2 ผ่านการคูณเมทริกซ์บล็อก 7 ครั้ง ตามปกติแสดงถึงมิติของเมทริกซ์และระบุขนาดหน่วยความจำ ${\displaystyle n}$${\displaystyle M}$

ความคืบหน้าสำหรับการคูณเมทริกซ์บล็อก 2x2 แบบเรียกซ้ำคล้าย Strassen

ปี	อ้างอิง	จำนวนการคูณเมทริกซ์ต่อขั้นตอน	จำนวนการบวกเมทริกซ์ต่อขั้นตอน	การดำเนินการทางคณิตศาสตร์ทั้งหมด	ความซับซ้อนของอินพุต/เอาต์พุตโดยรวม
1969	สตราสเซิน[ 9 ]	7	18	${\displaystyle 7n^{\log _{2}7}-6n^{2}}$	${\displaystyle 6\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-18n^{2}+3M}$
1971	วินโนกราด[ 10 ]	7	15	${\displaystyle 6n^{\log _{2}7}-5n^{2}}$	${\displaystyle 5\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-15n^{2}+3M}$
2017	คาร์สตัดท์, ชวาร์ตซ์[ 11 ]	7	12	${\displaystyle 5n^{\log _{2}7}-4n^{2}+3n^{2}\log _{2}n}$	${\displaystyle 4\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-12n^{2}+3n^{2}\cdot \log _{2}\left({\frac {{\sqrt {2}}n}{\sqrt {M}}}\right)+5M}$
2023	ชวาร์ตซ์, วาคิน[ 12 ]	7	12	${\displaystyle 5n^{\log _{2}7}-4n^{2}+1.5n^{2}\log _{2}n}$	${\displaystyle 4\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-12n^{2}+1.5n^{2}\cdot \log _{2}\left({\frac {{\sqrt {2}}n}{\sqrt {M}}}\right)+5M}$

เป็นที่ทราบกันดีว่าอัลกอริทึมแบบ Strassen ที่มีขั้นตอนเมทริกซ์บล็อก 2×2 ต้องใช้การคูณเมทริกซ์บล็อกอย่างน้อย 7 ครั้ง ในปี 1976 Probert ^{[ 13 ]}แสดงให้เห็นว่าอัลกอริทึมดังกล่าวต้องใช้การบวกอย่างน้อย 15 ครั้ง (รวมถึงการลบ) อย่างไรก็ตาม ข้อสมมติฐานที่ซ่อนอยู่คือบล็อกและเมทริกซ์บล็อก 2×2 ถูกแสดงในฐานเดียวกัน Karstadt และ Schwartz คำนวณในฐานที่แตกต่างกันและแลกเปลี่ยนการบวก 3 ครั้งกับการแปลงฐานที่มีราคาถูกกว่า พวกเขายังพิสูจน์ได้ว่าไม่สามารถลดการบวกต่อขั้นตอนลงต่ำกว่า 12 ครั้งได้โดยใช้ฐานที่แตกต่างกัน ในงานต่อมา Beniamini et al. ^{[ 14 ]}ได้นำกลอุบายการเปลี่ยนฐานนี้ไปใช้กับการแยกส่วนที่ทั่วไปมากกว่าเมทริกซ์บล็อก 2×2 และปรับปรุงค่าคงที่นำหน้าสำหรับเวลาการทำงานของพวกเขา

ใน วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎียังคงเป็นคำถามที่เปิดกว้างว่าอัลกอริทึมของ Strassen สามารถปรับปรุงให้ดีขึ้นได้มากเพียงใดในแง่ของความซับซ้อนเชิงอะ ซิ มโทติก เลขชี้กำลังการคูณเมทริกซ์ ซึ่ง มักจะใช้ สัญลักษณ์ เป็นจำนวนจริงที่เล็กที่สุดที่เมทริกซ์ใดๆ บนฟิลด์สามารถคูณกันได้โดยใช้การดำเนินการของฟิลด์ ขอบเขตที่ดีที่สุดในปัจจุบันของคือโดย Alman, Duan, Williams , Xu, Xu และ Zhou ^{[ 2 ]}อัลกอริทึมนี้ เช่นเดียวกับอัลกอริทึมล่าสุดอื่นๆ ในสายงานวิจัยนี้ เป็นการวางนัยทั่วไปของอัลกอริทึม Coppersmith–Winograd ซึ่งDon CoppersmithและShmuel Winograd ได้เสนอไว้ ในปี 1990 ^{[ 15 ]}แนวคิดของอัลกอริทึมเหล่านี้คล้ายกับอัลกอริทึมของ Strassen กล่าวคือ มีการคิดค้นวิธีการคูณเมทริกซ์k × k สอง เมทริกซ์โดยใช้การคูณน้อยกว่าk ³ครั้ง และเทคนิคนี้จะถูกนำไปใช้แบบเรียกซ้ำ อย่างไรก็ตาม ค่าสัมประสิทธิ์คงที่ที่ซ่อนอยู่ภาย ใต้ สัญกรณ์บิ๊กโอมีขนาดใหญ่มากจนอัลกอริทึมเหล่านี้คุ้มค่าเฉพาะกับเมทริกซ์ที่มีขนาดใหญ่เกินกว่าจะจัดการได้บนคอมพิวเตอร์ในปัจจุบัน^{[ 16 ] [ 17 ]} Victor Panได้เสนออัลกอริทึมการคูณเมทริกซ์ย่อยลูกบาศก์ที่สามารถทำได้จริง โดยมีเลขชี้กำลังสูงกว่า 2.77 เล็กน้อย แต่แลกมาด้วยค่าสัมประสิทธิ์คงที่ที่ซ่อนอยู่ที่เล็กกว่ามาก^{[ 18 ]}${\displaystyle \omega }$${\displaystyle n\times n}$${\displaystyle n^{\โอเมก้า +o(1)}}$${\displaystyle \omega }$${\displaystyle \โอเมก้า <2.371339}$

อัลกอริทึมของ Freivaldsเป็นอัลกอริทึม Monte Carlo ที่เรียบง่าย ซึ่งเมื่อกำหนดเมทริกซ์A , BและC แล้ว จะตรวจสอบว่า AB = CในเวลาΘ( n² ⁾ หรือ ไม่

ในปี 2022 DeepMindได้เปิดตัว AlphaTensor ซึ่งเป็นโครงข่ายประสาทเทียมที่ใช้การเปรียบเทียบเกมผู้เล่นคนเดียวเพื่อคิดค้นอัลกอริทึมการคูณเมทริกซ์หลายพันรายการ รวมถึงบางรายการที่มนุษย์เคยค้นพบมาก่อนและบางรายการที่ยังไม่เคย ค้นพบ ^{[ 19 ]}การดำเนินการถูกจำกัดไว้ที่ฟิลด์พื้นฐานที่ไม่สลับที่ (เลขคณิตปกติ) และฟิลด์จำกัด${\displaystyle \mathbb {Z} /2\mathbb {Z} }$ (เลขคณิต mod 2) อัลกอริทึม "เชิงปฏิบัติ" ที่ดีที่สุด (การแยกส่วนอันดับต่ำที่ชัดเจนของเทนเซอร์การคูณเมทริกซ์) ที่พบนั้นทำงานใน O(n ^2.778 ) ^{[ 20 ]}การค้นหาการแยกส่วนอันดับต่ำของเทนเซอร์ดังกล่าว (และอื่นๆ) เป็นปัญหา NP-hard การคูณที่เหมาะสมที่สุดแม้แต่สำหรับเมทริกซ์ 3×3 ก็ยังคงไม่เป็นที่รู้จักแม้แต่ในฟิลด์ที่สลับที่^{[ 20 ]}สำหรับเมทริกซ์ 4×4 นั้น AlphaTensor ค้นพบวิธีแก้ปัญหาโดยไม่คาดคิดด้วยขั้นตอนการคูณ 47 ขั้นตอน ซึ่งเป็นการปรับปรุงจาก 49 ขั้นตอนที่จำเป็นสำหรับอัลกอริทึมของ Strassen ในปี 1969 แม้ว่าจะจำกัดเฉพาะการคำนวณแบบ mod 2 ก็ตาม ในทำนองเดียวกัน AlphaTensor แก้ปัญหาเมทริกซ์ 5×5 ด้วย 96 ขั้นตอน แทนที่จะเป็น 98 ขั้นตอนของ Strassen จากการค้นพบที่น่าประหลาดใจว่ามีการปรับปรุงดังกล่าว นักวิจัยคนอื่นๆ จึงสามารถค้นหาอัลกอริทึม 4×4 ที่คล้ายกันได้อย่างรวดเร็ว และปรับแต่งอัลกอริทึม 5×5 96 ขั้นตอนของ Deepmind ให้เหลือ 95 ขั้นตอนในการคำนวณแบบ mod 2 และเหลือ 97 ขั้นตอน^{[ 21 ]}ในการคำนวณแบบปกติ^{[ 22 ]}อัลกอริทึมบางตัวเป็นของใหม่ทั้งหมด เช่น (4, 5, 5) ได้รับการปรับปรุงเป็น 76 ขั้นตอนจากค่าพื้นฐาน 80 ขั้นตอนทั้งในการคำนวณแบบปกติและแบบ mod 2

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

${\displaystyle {\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}}$

สามารถดำเนินการได้อย่างอิสระจากกันและกัน เช่นเดียวกับผลรวมทั้งสี่ (แม้ว่าอัลกอริทึมจะต้อง "รวม" การคูณก่อนที่จะทำการบวก) การใช้ประโยชน์จากความขนานเต็มรูปแบบของปัญหา ทำให้ได้อัลกอริทึมที่สามารถแสดงได้ในรูปแบบรหัสเทียมแบบ fork–join : ^{[ 23 ]}

ในที่นี้forkเป็นคำหลักที่บ่งชี้ว่าการคำนวณอาจทำงานแบบขนานกับส่วนที่เหลือของการเรียกใช้ฟังก์ชัน ในขณะที่joinจะรอให้การคำนวณที่ "แยก" ออกมาก่อนหน้านี้เสร็จสมบูรณ์ ส่วนpartitionบรรลุเป้าหมายโดยการจัดการตัวชี้เท่านั้น

อัลกอริทึมนี้มีความยาวเส้นทางวิกฤตเท่ากับΘ(log ² n )ขั้นตอน ซึ่งหมายความว่าต้องใช้เวลามากเท่านั้นบนเครื่องในอุดมคติที่มีโปรเซสเซอร์จำนวนอนันต์ ดังนั้นจึงมีอัตราเร่ง สูงสุดที่เป็นไปได้ เท่ากับΘ( n ³ /log ² n )บนคอมพิวเตอร์จริงใดๆ อัลกอริทึมนี้ไม่สามารถใช้งานได้จริงเนื่องจากต้นทุนการสื่อสารที่เกิดขึ้นจากการย้ายข้อมูลไปและกลับจากเมทริกซ์ชั่วคราวTแต่รูปแบบที่ใช้งานได้จริงมากกว่าจะบรรลุ อัตราเร่ง Θ( n ² )โดยไม่ต้องใช้เมทริกซ์ชั่วคราว^{[ 23 ]}

ในสถาปัตยกรรมสมัยใหม่ที่มีหน่วยความจำแบบลำดับชั้น ต้นทุนในการโหลดและจัดเก็บองค์ประกอบเมทริกซ์อินพุตมักจะสูงกว่าต้นทุนในการคำนวณทางคณิตศาสตร์ ในเครื่องเดียว ต้นทุนนี้คือปริมาณข้อมูลที่ถ่ายโอนระหว่าง RAM และแคช ในขณะที่ใน เครื่องหลายโหนด ที่มีหน่วยความจำแบบกระจาย ต้นทุนนี้คือปริมาณข้อมูลที่ถ่ายโอนระหว่างโหนด ในทั้งสองกรณีเรียกว่าแบนด์วิดท์การสื่อสาร อัลกอริทึมแบบง่ายที่ใช้ ลูปซ้อนกันสามลูปใช้แบนด์วิดท์การสื่อสาร Ω( n³ ⁾

อัลกอริทึมของแคนนอนหรือที่รู้จักกันในชื่ออัลกอริทึม 2 มิติเป็นอัลกอริทึมที่หลีกเลี่ยงการสื่อสารซึ่งแบ่งเมทริกซ์อินพุตแต่ละเมทริกซ์ออกเป็นเมทริกซ์บล็อกที่มีองค์ประกอบเป็นเมทริกซ์ย่อยขนาด√M / 3คูณ√M /3โดยที่Mคือขนาดของหน่วยความจำเร็ว^{[ 24 ]} จาก^นั้นใช้อัลกอริทึมแบบง่ายกับเมทริกซ์บล็อก โดยคำนวณผลคูณของเมทริกซ์ย่อยทั้งหมดในหน่วยความจำเร็ว ซึ่งช่วยลดแบนด์วิดท์การสื่อสารเป็นO ( n3 / √M )ซึ่งเหมาะสมที่สุดในเชิงอะซิมโทติก (สำหรับอัลกอริทึมที่ทำการคำนวณ Ω ( n3 ⁾ ) ^{[ 25 ] [ 26 ]}

ในการตั้งค่าแบบกระจายที่มี โปรเซสเซอร์ pตัวเรียงกันใน ตาข่าย 2 มิติ ขนาด √p x √p เมท ^{ริก ซ์}ย่อยหนึ่งเมทริกซ์ของผลลัพธ์สามารถกำหนดให้กับโปรเซสเซอร์แต่ละตัวได้ และสามารถคำนวณผลคูณได้โดยแต่ละโปรเซสเซอร์ส่งคำ O ( n² / √p )ซึ่งถือว่าเหมาะสมที่สุดในเชิงอะซิมโทติก โดยสมมติว่าแต่ละโหนดเก็บองค์ประกอบขั้นต่ำO(n²/ p ) [ 26 ^] สามารถปรับปรุง^{ได้ด้วยอั}ลกอริทึม 3 มิติซึ่งจัดเรียงโปรเซสเซอร์ในตาข่ายลูกบาศก์ 3 มิติ โดยกำหนดผลคูณของเมทริกซ์ย่อยอินพุตสองเมทริกซ์ให้กับโปรเซสเซอร์ตัวเดียว จากนั้นจะสร้างเมทริกซ์ย่อยผลลัพธ์โดยการลดขนาดในแต่ละแถว^{[ 27 ]}อัลกอริทึมนี้ส่ง คำ O ( n² ^/ p² ^/3 )ต่อโปรเซสเซอร์ ซึ่งถือว่าเหมาะสมที่สุดในเชิง อะซิ ม โทติก ^{[ 26 ]}อย่างไรก็ตาม วิธีนี้จำเป็นต้องทำซ้ำองค์ประกอบเมทริกซ์อินพุตแต่ละรายการp ^1/3ครั้ง ดังนั้นจึงต้องการหน่วยความจำมากกว่าที่จำเป็นในการจัดเก็บอินพุต ถึง p ^{1/3 เท่า อัลกอริทึมนี้สามารถรวมเข้ากับ Strassen เพื่อลดเวลาการทำงานลงได้อีก [ 27 ]}อัลกอริทึม "2.5D" ให้ความสมดุลอย่างต่อเนื่องระหว่างการใช้หน่วยความจำและแบนด์วิดท์การสื่อสาร^{[ 28 ]}ในสภาพแวดล้อมการประมวลผลแบบกระจายที่ทันสมัย ​​เช่นMapReduceได้มีการพัฒนาอัลกอริทึมการคูณเฉพาะ ทางขึ้น ^{[ 29 ]}

มีอัลกอริธึมหลากหลายสำหรับการคูณบนเมชสำหรับการคูณเมทริกซ์n × n สอง เมทริกซ์บนเมชสองมิติมาตรฐานโดยใช้อัลกอริธึมของแคนนอน แบบ 2 มิติ สามารถทำการคูณให้เสร็จสมบูรณ์ได้ใน 3 n -2 ขั้นตอน แม้ว่าจำนวนนี้จะลดลงครึ่งหนึ่งสำหรับการคำนวณซ้ำ^{[ 30 ]}อาร์เรย์มาตรฐานไม่มีประสิทธิภาพเนื่องจากข้อมูลจากเมทริกซ์ทั้งสองไม่ได้มาพร้อมกันและต้องเติมด้วยศูนย์

ผลลัพธ์จะเร็วขึ้นไปอีกบนตาข่ายไขว้สองชั้น ซึ่งต้องการ เพียง 2 n -1 ขั้นตอนเท่านั้น ^{[ 31 ]}ประสิทธิภาพจะดีขึ้นไปอีกสำหรับการคำนวณซ้ำๆ จนได้ประสิทธิภาพ 100% ^{[ 32 ]}อาร์เรย์ตาข่ายไขว้สามารถมองได้ว่าเป็นกรณีพิเศษของโครงสร้างการประมวลผลที่ไม่เป็นระนาบ (เช่น หลายชั้น) ^{[ 33 ]}

ในตาข่าย 3 มิติที่มี องค์ประกอบการประมวลผล n ³เมทริกซ์สองเมทริกซ์สามารถคูณกันได้โดยใช้อัลกอริธึม DNS ^{[ 34 ]}${\displaystyle {\mathcal {O}}(\log n)}$

• ความซับซ้อนในการคำนวณของการดำเนินการทางคณิตศาสตร์
• ความซับซ้อนในการคำนวณของการคูณเมทริกซ์
• อัลกอริทึม CYK § อัลกอริทึมของ Valiant
• การคูณโซ่เมทริกซ์
• วิธีการของชาวรัสเซียสี่คน
• อัลกอริทึมการคูณ
• การคูณเมทริกซ์แบบเบาบางกับเวกเตอร์