ขั้นตอนวิธีของแคนนอน

ขั้นตอนวิธีของแคนนอน  คือขั้นตอนวิธีสำหรับการคูณเมทริกซ์สองเมทริกซ์ที่มีมิติ <math>n \times n</math> ด้วยการทำงานแบบขนาน นำเสนอโดย "ลิน เอลเลียต แคนนอน (Lynn Elliot Cannon)" ในปี ค.ศ. 1969
อธิบายขั้นตอนวิธี.
ให้ A และ B เป็นเมทริกซ์ที่ถูกดำเนินการ และ C เป็นเมทริกซ์ผลลัพธ์
แบ่งเมทริกซ์สองเมทริกซ์ A และ B ให้เป็นเมทริกซ์จตุรัสย่อย ๆ จำนวน p เมทริกซ์ โดยที่ p คือจำนวนกระบวนการ (process) ทั้งหมด โดยที่ทุกกระบวนการทำงานไปพร้อม ๆ กัน และสามารถส่งผ่านข้อมูลระหว่างกันได้ ส่งเมทริกซ์ย่อย <math>A_{ij} </math> และ <math>B_{ij}</math> ลงในกระบวนการ <math>P_{ij}</math>
เริ่มต้นเรียงตำแหน่งของเมทริกซ์ย่อย ให้แถวที่ i ของเมทริกซ์ A เลื่อนหมุนตามแนวนอนไปด้านซ้ายเป็นจำนวน i ช่อง และสดมภ์ที่ j ของเมทริกซ์ B เลื่อนหมุนตามแนวตั้งไปด้านบนเป็นจำนวน j ช่อง (i และ j มีค่าตั้งแต่ 0 ถึง n-1) 
 ตัวอย่างการเรียงเริ่มต้นของเมทริกซ์ขนาด 4 x 4 
" เมทริกซ์ A " 
<math>
 A_{00} & A_{01} & A_{02} & A_{03} \\ A_{10} & A_{11} & A_{12} & A_{13} \\ A_{20} & A_{21} & A_{22} & A_{23} \\ A_{30} & A_{31} & A_{32} & A_{33} \end{bmatrix}</math>
<math>
 A_{00} & A_{01} & A_{02} & A_{03} \\ A_{11} & A_{12} & A_{13} & A_{10} \\ A_{22} & A_{23} & A_{20} & A_{21} \\ A_{33} & A_{30} & A_{31} & A_{32} \end{bmatrix}</math> 
" เมทริกซ์ B " 
<math>
 B_{00} & B_{01} & B_{02} & B_{03} \\ B_{10} & B_{11} & B_{12} & B_{13} \\ B_{20} & B_{21} & B_{22} & B_{23} \\ B_{30} & B_{31} & B_{32} & B_{33} \end{bmatrix}</math>
<math>
 B_{00} & B_{11} & B_{22} & B_{33} \\ B_{10} & B_{21} & B_{32} & B_{03} \\ B_{20} & B_{31} & B_{02} & B_{13} \\ B_{30} & B_{01} & B_{12} & B_{23} \end{bmatrix}</math>
ให้แต่ละกระบวนการ <math>P_{i j}</math> คำนวณหาผลคูณของ <math>A_{i j} </math> และ <math>B_{i j}</math> ในกระบวนการนั้น ๆ แล้วนำไปบวกเพิ่มใน <math>C_{i j}</math> จากนั้นเลื่อนเมทริกซ์ย่อยของ A ไปด้านซ้ายในแต่ละแถว และเมทริกซ์ย่อยของ B ไปด้านบนในแต่ละแถว
ทำเช่นเดิมทั้งหมด <math>\sqrt{p}</math> ครั้ง จะได้เมทริกซ์ผลลัพธ์ คือ เมทริกซ์ C
 ตัวอย่างการเลื่อนครั้งที่ 1 ของเมทริกซ์ขนาด 4 x 4 
" เมทริกซ์ A " 
<math>
A_{00} & A_{01} & A_{02} & A_{03} \\ A_{11} & A_{12} & A_{13} & A_{10} \\ A_{22} & A_{23} & A_{20} & A_{21} \\ A_{33} & A_{30} & A_{31} & A_{32} \end{bmatrix}</math>
<math>
 A_{01} & A_{02} & A_{03} & A_{00} \\ A_{12} & A_{13} & A_{10} & A_{11} \\ A_{23} & A_{20} & A_{21} & A_{22} \\ A_{30} & A_{31} & A_{32} & A_{33} \end{bmatrix}</math> 
" เมทริกซ์ B " 
<math>
 B_{00} & B_{11} & B_{22} & B_{33} \\ B_{10} & B_{21} & B_{32} & B_{03} \\ B_{20} & B_{31} & B_{02} & B_{13} \\ B_{30} & B_{01} & B_{12} & B_{23} \end{bmatrix}</math>
<math>
B_{10} & B_{21} & B_{32} & B_{03} \\ B_{20} & B_{31} & B_{02} & B_{13} \\ B_{30} & B_{01} & B_{12} & B_{23} \\ B_{00} & B_{11} & B_{22} & B_{33} \end{bmatrix}</math>
วิเคราะห์ขั้นตอนวิธี.
ทางด้านเวลาการทำงาน ถ้ากระบวนการทุกกระบวนการทำงานพร้อมกันแบบขนาน และกระบวนการแต่ละกระบวนการสามารถส่งเมทริกซ์ย่อยไปยังกระบวนการข้างเคียงได้เพียงหนึ่งกระบวนการต่อครั้ง จะเกิดการส่งเมทริกซ์ย่อยทั้งหมด <math>4\sqrt{p}-2</math> ครั้ง และการคูณเมทริกซ์ย่อยแต่ละครั้งใช้การคูณตัวเลขทั้งหมด <math>(\frac{n}{\sqrt{p}})^3</math> จะได้เวลาการทำงานเป็น <math>\boldsymbol{\Theta} (\frac{n^3}{p})</math> ทางด้านหน่วยความจำจะใช้หน่วยความจำคงที่เป็น <math>\boldsymbol{\Theta}(n^2)</math>
อย่างไรก็ตาม ขั้นตอนวิธีนี้จะใช้ได้ก็ต่อเมื่อจำนวนกระบวนการเป็นตัวเลขที่เกิดจากการยกกำลังสอง เมทริกซ์ที่นำมาคูณกันเป็นเมทริกซ์จตุรัส และขนาดของเมทริกซ์หารจำนวนกระบวนการลงตัว