เวลาเรามีเมทริกซ์สองตัว $A=[\;\begin{smallmatrix}a_{11}&a_{12} \newline a_{21}&a_{22}\end{smallmatrix}\;]$ กับ $B=[\;\begin{smallmatrix}b_{11}&b_{12} \newline b_{21}&b_{22}\end{smallmatrix}\;]$ เราสามารหาผลคูณ $C=AB$ ได้ว่า

\[\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{bmatrix} = \begin{bmatrix} 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{bmatrix}\]

จะเห็นว่าแต่ละสมาชิกในเมทริกซ์ผลลัพธ์นั้นอยู่ในรูป $c_{ij} = a_{i1}b_{1j}+a_{i2}b_{2j}$ ซึ่งก็คือมีการคูณกันสองครั้ง แล้วหลังจากนั้นจึงนำผลคูณมารวมกัน (สำหรับเมทริกซ์ขนาด $n{\times}n$ จะได้ $c_{ij} = \sum_1^n a_{i\square}b_{\square j}$ แทน)

ความเจ๋งของสมการข้างต้นก็คือ แต่ละค่า $a_{ij}$ และ $b_{ij}$ มันไม่ถูกจำกัดให้ต้องเป็นสเกลาร์เท่านั้น แต่ยังสามารถเป็นเมทริกซ์ย่อยของ $A$ และ $B$ ที่พาร์ทิชันมาให้มีขนาดเท่ากันได้อีกด้วย

ตัวอย่างเช่นเมื่อ $A$ และ $B$ เป็นเมทริกซ์ขนาด $4{\times}4$ เราจะได้

\[\begin{align} {\color{red}A}{\color{blue}B} &= {\color{red}\left[\;\begin{array}{c:c} \boxed{\begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{matrix}} & \boxed{\begin{matrix}a_{13} & a_{14} \\ a_{23} & a_{24}\end{matrix}} \\ \hdashline \boxed{\begin{matrix}a_{31} & a_{32} \\ a_{41} & a_{42}\end{matrix}} & \boxed{\begin{matrix}a_{33} & a_{34} \\ a_{43} & a_{44}\end{matrix}} \end{array}\;\right]} {\color{blue}\left[\;\begin{array}{c:c} \boxed{\begin{matrix}b_{11} & b_{12} \\ b_{21} & b_{22}\end{matrix}} & \boxed{\begin{matrix}b_{13} & b_{14} \\ b_{23} & b_{24}\end{matrix}} \\ \hdashline \boxed{\begin{matrix}b_{31} & b_{32} \\ b_{41} & b_{42}\end{matrix}} & \boxed{\begin{matrix}b_{33} & b_{34} \\ b_{43} & b_{44}\end{matrix}} \end{array}\;\right]} \\ &= \left[\;\begin{array}{c:c} {\color{red}\boxed{\begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{matrix}}}\, {\color{blue}\boxed{\begin{matrix}b_{11} & b_{12} \\ b_{21} & b_{22}\end{matrix}}} + {\color{red}\boxed{\begin{matrix}a_{13} & a_{14} \\ a_{23} & a_{24}\end{matrix}}}\, {\color{blue}\boxed{\begin{matrix}b_{31} & b_{32} \\ b_{41} & b_{42}\end{matrix}}} & \cdots \\ \hdashline \vdots & \ddots \end{array}\;\right] \\ &= \left[\;\begin{array}{c:c} \boxed{\begin{matrix} \sum_1^2 a_{1\square}b_{\square1} & \sum_1^2 a_{1\square}b_{\square2} \\ \sum_1^2 a_{2\square}b_{\square1} & \sum_1^2 a_{2\square}b_{\square2} \end{matrix}} + \boxed{\begin{matrix} \sum_3^4 a_{1\square}b_{\square1} & \sum_3^4 a_{1\square}b_{\square2} \\ \sum_3^4 a_{2\square}b_{\square1} & \sum_3^4 a_{2\square}b_{\square2} \end{matrix}} & \cdots \\ \hdashline \vdots & \ddots \end{array}\;\right] \\ &= \left[\;\begin{array}{cc:cc} \sum_1^4 a_{1\square}b_{\square1} & \sum_1^4 a_{1\square}b_{\square2} & \cdots & \sum_1^4 a_{1\square}b_{\square4} \\ \sum_1^4 a_{2\square}b_{\square1} & \sum_1^4 a_{2\square}b_{\square2} && \\ \hdashline \vdots && \ddots \\ \sum_1^4 a_{4\square}b_{\square1} &&& \sum_1^4 a_{4\square}b_{\square4} \end{array}\;\right] \end{align}\]

นั่นก็คือเราสามารถประยุกต์ใช้เทคนิคแบ่งแยกและเอาชนะเพื่อแก้ปัญหานี้ได้

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

เริ่มจากเมทริกซ์ $n{\times}n$ เมื่อ $n=2$ จากข้อสังเกตที่ว่าแต่ละสมาชิกในเมทริกซ์มีการคูณสองครั้ง ดังนั้นการคูณกันรวมทั้งหมดจึงเป็นแปดครั้ง ต่อมาเมื่อเราเพิ่มขนาดเมทริกซ์เป็น $n=4$ จะได้ว่าเราเรียกตัวเองเป็นการคูณเมทริกซ์ย่อยขนาด $2{\times}2$ เป็นจำนวนแปดครั้ง ดังนั้นการคูณพื้นฐานรวมคือ $8\cdot8=64$ ครั้ง

เราจึงอาจสรุปได้คร่าวๆ ว่าความซับซ้อนของอัลกอริทึมคือ $O(n^3)$ ด้วยการนับจำนวนการคูณพื้นฐาน กอปรกับเมื่อเราย้อนกลับไปดูนิยามการคูณเมทริกซ์ข้างต้นแล้ว ความซับซ้อนที่ได้นี้ก็ดูจะสอดคล้องและไม่น่าจะถูกปรับปรุงให้ดีขึ้นกว่าเดิมได้อีก …

จนกระทั่ง Volker Strassen เสนออัลกอริทึมสำหรับคูณเมทริกซ์ในปี 1969 ที่สามารถลดจำนวนการคูณในแต่ละชั้นให้ลดลงเหลือเพียงแค่เจ็ดครั้งได้ โดยอาศัยข้อสังเกตว่าเราไม่จำเป็นต้องคำนวณแต่ละ $c_{ij}$ ตรงๆ แต่เราจะเดินอ้อมด้วยการคำนวณผลคูณระหว่างทางที่ซับซ้อนกว่าเดิมเล็กน้อยเก็บไว้ก่อน แล้วค่อยนำผลคูณเหล่านั้นมาบวกกันเพื่อสร้างเป็นแต่ละ $c_{ij}$ ทีหลัง ซึ่งจุดสำคัญคือเราจะใช้ผลคูณบางค่าซ้ำในหลายที่ จึงทำให้เราประหยัดการคูณลงไปได้นั่นเอง

เขียนให้ชัดๆ ก็คือ เราจะเริ่มคำนวณผลคูณระหว่างทางเหล่านี้ทิ้งไว้

\[\begin{align} m_1 &= (a_{11}+a_{22})(b_{11}+b_{22}) \\ m_2 &= (a_{21}+a_{22})b_{11} \\ m_3 &= a_{11}(b_{12}-b_{22}) \\ m_4 &= a_{22}(b_{21}-b_{11}) \\ m_5 &= (a_{11}+a_{12})b_{22} \\ m_6 &= (a_{21}-a_{11})(b_{11}+b_{12}) \\ m_7 &= (a_{12}-a_{22})(b_{21}+b_{22}) \end{align}\]

แล้วจึงหา $C=AB$ จาก

\[\begin{bmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \end{bmatrix} = \begin{bmatrix} m_1 + m_4 - m_5 + m_7 & m_3 + m_5 \\ m_2 + m_4 & m_1 - m_2 + m_3 + m_6 \end{bmatrix}\]

เนื่องจากเราลดการคูณเหลือเพียงเจ็ดครั้ง จึงได้ว่าความซับซ้อนลดเหลือ $O(n^{\log_27}) \approx O(n^{2.8})$

ชุดสมการข้างต้นนั้นจะว่าไปก็ดูซับซ้อนพอสมควร แต่ผมพบว่าภาพประกอบบนวิกิพีเดียนั้นช่วยให้เห็นภาพแนวคิดหลักของอัลกอริทึมได้ดีมากๆ ซึ่งก็คือเราอาจมองมันเป็นเกมประกอบตัวต่อให้ได้รูปทรงตามที่ต้องการก็ได้ โดยตัวต่อที่เราสนใจนั้นมีรูปร่างเป็นตารางขนาด $4{\times}4$ ของทุกความเป็นไปได้ของการจับคู่คูณกันระหว่างทุกสมาชิกใน $A$ กับ $B$ และเราจะสร้างแต่ละ $c_{ij}$ ผ่านการจับตัวต่อ $m_1$ ถึง $m_7$ มาประกอบกัน

$c_{11}$

$c_{12}$

$c_{21}$

$c_{22}$

$m_1$

- 0 +

$m_2$

- 0 +

$m_3$

- 0 +

$m_4$

- 0 +

$m_5$

- 0 +

$m_6$

- 0 +

$m_7$

- 0 +

invert clear

แม้อัลกอริทึมของ Strassen จะดูว่าเป็นการปรับปรุงความซับซ้อนเพียงเล็กน้อย แต่ก็นับเป็นหมุดหมายสำคัญของการเริ่มต้นศึกษาวิจัยการคูณเมทริกซ์ กว่าครึ่งศตวรรษที่ผ่านมาก็มีการพัฒนามาตลอดโดยนักวิจัยที่หลากหลาย (Strassen เองก็เสนออัลกอริทึมที่ดีกว่าเดิมอีกด้วย แต่ทั่วไปแล้วเมื่อพูดถึงอัลกอริทึมของ Strassen ก็จะหมายถึงอัลกอริทึมแรกสุดที่เขานำเสนอ) โดยล่าสุดเมื่อปี 2020 ที่ผ่านมา ทีมวิจัยที่ประกอบด้วย Josh Alman และ Virginia Vassilevska Williams ได้พัฒนาเทคนิคใหม่ๆ ซึ่งสามารถปรับปรุงความซับซ้อนของการคูณเมทริกซ์ให้เหลือเพียง $O(n^{2.3728596})$