STP Computation

The basic Semi-Tensor Product (STP) Computation based on Eigen Library

Basic STP Computation

Native Definition

Given two matrices \(A_{m \times n}\) and \(B_{p \times q}\), the STP of \(A\) and \(B\) is defined as

\[A \ltimes B = (A \bigotimes I_{t/n}) \cdot (B \bigotimes I_{t/p})\]

where \(\bigotimes\) is Kronecker product, \(I\) is identity matrix, and \(t\) is least common multiple (LCM) of \(n\) and \(p\). As an example, suppose

\[\begin{split}A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \end{bmatrix}\end{split}\]

and

\[\begin{split}B = \begin{bmatrix} 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix},\end{split}\]

then \(m=2, n=4\) and \(p=2, q=4\), the LCM \(t\) is thus 4. According to the definition,

\[\begin{split}\begin{align} A \ltimes B = (A \bigotimes I_{4/4}) \cdot (B \bigotimes I_{4/2}) &= \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} \notag \\ &= \begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \end{bmatrix}. \notag \end{align}\end{split}\]

Copy Definition

Continue with the above example, we can view \(A\) be composed by two submatrices \(A_{left}=\begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}\) and \(A_{right} = \begin{bmatrix}0 & 0 \\ 1 & 1\end{bmatrix}\). When we compute the STP \(A \bigotimes B\), we can examine \(B\) column by column from leftside to rightside, if the column in \(B\) is \(\begin{bmatrix} 1 \\ 0 \end{bmatrix}\), we copy \(A_{left}\) as a partial result; otherwise, we copy \(A_{right}\). One can verify the results are exactly the same as the ones computed by native definition.

Functions

In header file stp/stp_eigen.hpp, we provide function:

matrix semi_tensor_product( const matrix& A, const matrix& B
                            const bool verbose = false,
                            const stp_method method = stp_method::copy_method )

to compute the STP of matrices \(A\) and \(B\), where toggle verbose is off and toggle stp_method is used by the copy definition by default.

Example

matrix A;
matrix B;

//default
auto result = stp::semi_tensor_product( A, B );

//print verbose information
auto result = stp::semi_tensor_product( A, B, true );

//use native definition for STP computation
auto result = stp::semi_tensor_product( A, B, true, stp::stp_method::native_method );

One can find more examples or test cases in examples/stp_eigen.cpp and test/stp_eigen.cpp.

Matrix Chain STP Computation

When we have \(n\) matrices multiplication and \(n \ge 3\), we call this as matrix chain STP computation.

Sequence

The matrix chain STP is calculated by sequential order. For example, we have 4 matrices \(A\), \(B\), \(C\), and \(D\). The parenthesized expression of the matrix chain multiplication is as follows:

\[ABCD = (((AB)C)D).\]

Dynamic Programming

Since the computational complexity varies depending on the method of parenthesizing, we also propose a dynamic programming approach for matrix chain STP computation. This approach allows us to determine the optimal parenthesization of the matrix chain.

\[ABCD = ((AB)(CD)).\]

Multi-threads

Once we obtained the computation orders based on dynamic programming, the computation can also invoke multi-threads to accerlerate.

Functions

In header file stp/stp_eigen.hpp, we provide function:

matrix matrix_chain_multiply( const matrix_chain& mc,
                              const bool verbose = false,
                              const mc_multiply_method method = mc_multiply_method::dynamic_programming )

to compute the STP of matrix chain \(mc\), where toggle verbose is off and toggle mc_multiply_method is used by the dynamic programming by default.

Example

matrix_chain mc;

//default
auto result = stp::matrix_chain_multiply( mc );

//print verbose information
auto result = stp::matrix_chain_multiply( mc, true );

//use sequence method for matrix chain STP computation
auto result = stp::matrix_chain_multiply( mc, false, mc_multiply_method::sequence );

One can find more test cases in test/stp_eigen.cpp.