# Algorithm type

${X}^{3}{Y}^{2}Z+30{X}^{2}{Y}^{2}{Z}^{2}+2X{Y}^{4}Z+X{Y}^{2}{Z}^{3}+9{X}^{3}YZ+4{X}^{2}{Y}^{2}Z+3X{Y}^{3}Z+3X{Y}^{2}{Z}^{2}+8XY{Z}^{3}+7{X}^{2}YZ+21X{Y}^{2}Z+4XY{Z}^{2}+12XYZ$

# Algorithm definition

The algorithm ⟨3×5×9:105⟩ could be constructed using the following decomposition:

$\mathrm{⟨3×5×9:105⟩}=\mathrm{⟨3×5×4:47⟩}+\mathrm{⟨3×5×5:58⟩.}$

This decomposition is defined by the following equality:

$\mathrm{Trace}\left(\mathrm{Mul}\left(\left(\begin{array}{ccccc}\mathrm{A_1_1}& \mathrm{A_1_2}& \mathrm{A_1_3}& \mathrm{A_1_4}& \mathrm{A_1_5}\\ \mathrm{A_2_1}& \mathrm{A_2_2}& \mathrm{A_2_3}& \mathrm{A_2_4}& \mathrm{A_2_5}\\ \mathrm{A_3_1}& \mathrm{A_3_2}& \mathrm{A_3_3}& \mathrm{A_3_4}& \mathrm{A_3_5}\end{array}\right),\left(\begin{array}{ccccccccc}\mathrm{B_1_1}& \mathrm{B_1_2}& \mathrm{B_1_3}& \mathrm{B_1_4}& \mathrm{B_1_5}& \mathrm{B_1_6}& \mathrm{B_1_7}& \mathrm{B_1_8}& \mathrm{B_1_9}\\ \mathrm{B_2_1}& \mathrm{B_2_2}& \mathrm{B_2_3}& \mathrm{B_2_4}& \mathrm{B_2_5}& \mathrm{B_2_6}& \mathrm{B_2_7}& \mathrm{B_2_8}& \mathrm{B_2_9}\\ \mathrm{B_3_1}& \mathrm{B_3_2}& \mathrm{B_3_3}& \mathrm{B_3_4}& \mathrm{B_3_5}& \mathrm{B_3_6}& \mathrm{B_3_7}& \mathrm{B_3_8}& \mathrm{B_3_9}\\ \mathrm{B_4_1}& \mathrm{B_4_2}& \mathrm{B_4_3}& \mathrm{B_4_4}& \mathrm{B_4_5}& \mathrm{B_4_6}& \mathrm{B_4_7}& \mathrm{B_4_8}& \mathrm{B_4_9}\\ \mathrm{B_5_1}& \mathrm{B_5_2}& \mathrm{B_5_3}& \mathrm{B_5_4}& \mathrm{B_5_5}& \mathrm{B_5_6}& \mathrm{B_5_7}& \mathrm{B_5_8}& \mathrm{B_5_9}\end{array}\right),\left(\begin{array}{ccc}\mathrm{C_1_1}& \mathrm{C_1_2}& \mathrm{C_1_3}\\ \mathrm{C_2_1}& \mathrm{C_2_2}& \mathrm{C_2_3}\\ \mathrm{C_3_1}& \mathrm{C_3_2}& \mathrm{C_3_3}\\ \mathrm{C_4_1}& \mathrm{C_4_2}& \mathrm{C_4_3}\\ \mathrm{C_5_1}& \mathrm{C_5_2}& \mathrm{C_5_3}\\ \mathrm{C_6_1}& \mathrm{C_6_2}& \mathrm{C_6_3}\\ \mathrm{C_7_1}& \mathrm{C_7_2}& \mathrm{C_7_3}\\ \mathrm{C_8_1}& \mathrm{C_8_2}& \mathrm{C_8_3}\\ \mathrm{C_9_1}& \mathrm{C_9_2}& \mathrm{C_9_3}\end{array}\right)\right)\right)=\mathrm{Trace}\left(\mathrm{Mul}\left(\left(\begin{array}{ccccc}\mathrm{A_1_1}& \mathrm{A_1_2}& \mathrm{A_1_3}& \mathrm{A_1_4}& \mathrm{A_1_5}\\ \mathrm{A_2_1}& \mathrm{A_2_2}& \mathrm{A_2_3}& \mathrm{A_2_4}& \mathrm{A_2_5}\\ \mathrm{A_3_1}& \mathrm{A_3_2}& \mathrm{A_3_3}& \mathrm{A_3_4}& \mathrm{A_3_5}\end{array}\right),\left(\begin{array}{cccc}\mathrm{B_1_1}& \mathrm{B_1_2}& \mathrm{B_1_3}& \mathrm{B_1_4}\\ \mathrm{B_2_1}& \mathrm{B_2_2}& \mathrm{B_2_3}& \mathrm{B_2_4}\\ \mathrm{B_3_1}& \mathrm{B_3_2}& \mathrm{B_3_3}& \mathrm{B_3_4}\\ \mathrm{B_4_1}& \mathrm{B_4_2}& \mathrm{B_4_3}& \mathrm{B_4_4}\\ \mathrm{B_5_1}& \mathrm{B_5_2}& \mathrm{B_5_3}& \mathrm{B_5_4}\end{array}\right),\left(\begin{array}{ccc}\mathrm{C_1_1}& \mathrm{C_1_2}& \mathrm{C_1_3}\\ \mathrm{C_2_1}& \mathrm{C_2_2}& \mathrm{C_2_3}\\ \mathrm{C_3_1}& \mathrm{C_3_2}& \mathrm{C_3_3}\\ \mathrm{C_4_1}& \mathrm{C_4_2}& \mathrm{C_4_3}\end{array}\right)\right)\right)+\mathrm{Trace}\left(\mathrm{Mul}\left(\left(\begin{array}{ccccc}\mathrm{A_1_1}& \mathrm{A_1_2}& \mathrm{A_1_3}& \mathrm{A_1_4}& \mathrm{A_1_5}\\ \mathrm{A_2_1}& \mathrm{A_2_2}& \mathrm{A_2_3}& \mathrm{A_2_4}& \mathrm{A_2_5}\\ \mathrm{A_3_1}& \mathrm{A_3_2}& \mathrm{A_3_3}& \mathrm{A_3_4}& \mathrm{A_3_5}\end{array}\right),\left(\begin{array}{ccccc}\mathrm{B_1_5}& \mathrm{B_1_6}& \mathrm{B_1_7}& \mathrm{B_1_8}& \mathrm{B_1_9}\\ \mathrm{B_2_5}& \mathrm{B_2_6}& \mathrm{B_2_7}& \mathrm{B_2_8}& \mathrm{B_2_9}\\ \mathrm{B_3_5}& \mathrm{B_3_6}& \mathrm{B_3_7}& \mathrm{B_3_8}& \mathrm{B_3_9}\\ \mathrm{B_4_5}& \mathrm{B_4_6}& \mathrm{B_4_7}& \mathrm{B_4_8}& \mathrm{B_4_9}\\ \mathrm{B_5_5}& \mathrm{B_5_6}& \mathrm{B_5_7}& \mathrm{B_5_8}& \mathrm{B_5_9}\end{array}\right),\left(\begin{array}{ccc}\mathrm{C_5_1}& \mathrm{C_5_2}& \mathrm{C_5_3}\\ \mathrm{C_6_1}& \mathrm{C_6_2}& \mathrm{C_6_3}\\ \mathrm{C_7_1}& \mathrm{C_7_2}& \mathrm{C_7_3}\\ \mathrm{C_8_1}& \mathrm{C_8_2}& \mathrm{C_8_3}\\ \mathrm{C_9_1}& \mathrm{C_9_2}& \mathrm{C_9_3}\end{array}\right)\right)\right)$

N.B.: for any matrices A, B and C such that the expression Tr(Mul(A,B,C)) is defined, one can construct several trilinear homogeneous polynomials P(A,B,C) such that P(A,B,C)=Tr(Mul(A,B,C)) (P(A,B,C) variables are A,B and C's coefficients). Each trilinear P expression encodes a matrix multiplication algorithm: the coefficient in C_i_j of P(A,B,C) is the (i,j)-th entry of the matrix product Mul(A,B)=Transpose(C).

# Algorithm description

These encodings are given in compressed text format using the maple computer algebra system. In each cases, the last line could be understood as a description of the encoding with respect to classical matrix multiplication algorithm. As these outputs are structured, one can construct easily a parser to its favorite format using the maple documentation without this software.

Back to main table