## 3 Algorithms for Toeplitz Matrix-Vector Multiplication
### Algorithm for \(N=9\)  
Let it be necessary to calculate the matrix-vector product of the following form:  
\[ \begin{bmatrix}y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\\ y_{4}\\ y_{5}\\ y_{6}\\ y_{7}\\ y_{8}\\ \end{bmatrix}\begin{bmatrix}y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\\ t_{10}\\ t_{12}\\ t_{13}\\ t_{14}\\ t_{15}\\ t_{16}\\ t_{17}\\ t_{18}\\ t_{19}\\ t_{19}\\ t_{18}\\ t_{19}\\ t_{20}\\ t_{21}\\ t_{22}\\ t_{23}\\ t_{24}\\ t_{25}\\ t_{26}\\ t_{27}\\ t_{28}\\ \end{bmatrix}\begin{bmatrix}x_{0}\\ x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ x_{5}\\ x_{6}\\ x_{7}\\ x_{8}\\ \end{bmatrix} . \tag{21}\]  
The direct method of calculating this product requires 81 multiplications and 72 additions. **Proposition 7**. : _To calculate the product (21), no more than 36 multiplications are required._  
Figure 6: Data flow diagram of the algorithm (20) for \(N=8\). Proof. : Let us introduce auxiliary matrices:  
\[\mathbf{T}_{18\times 9}^{(9)}= \begin{bmatrix}1&&&&1&&\\ &1&&&&1&\\ &1&&&&1&\\ &1&&1&&&\\ &1&&1&&&\\ &1&&&&1&&\\ &1&&&&\\ &&1&&&&\\ &&1&&&&\\ &&1&&&&1&\\ &&1&&&&1\\ &&&&&1&\\ &&&&1\end{bmatrix} ,\]  
\[\mathbf{T}_{36\times 18}^{(9)}=\mathbf{I}_{6}\otimes\mathbf{T}_{6\times 3 }^{(3)},\ \ \mathbf{T}_{6\times 3}^{(3)}= \begin{bmatrix}1&&1\\ 1&1\\ 1&1\\ &1&1\\ &1\end{bmatrix} ,\]  
\[\mathbf{P}_{18\times 36}^{(9)}=\mathbf{I}_{6}\otimes\mathbf{P}_{3\times 6}^{(9)}\]  
\[\mathbf{P}_{3\times 6}^{(9)}= \begin{bmatrix}1&&&&1&1&1\\ &1&1&1&\\ 1&1&1&&&\end{bmatrix} ,\]  
\[\mathbf{P}_{9\times 18}^{(9)}= \begin{bmatrix}1&&&&&&&1&1\\ &1&&&&1&1&\\ &1&&&&1&1&\\ &&1&&&1&1&\\ 1&1&1&&&&\\ &1&1&1&&&&\\ &1&1&1&&&&\\ &1&1&1&&&&\\ \end{bmatrix} ,\]  
and  
\[\mathbf{D}_{36}^{(9)}=\text{diag}\Big{(}s_{0}^{(9)},\ \ s_{1}^{(9)},\ \ \ldots,\ \ s_{35}^{(9)}\Big{)}, \tag{22}\]  
\[s_{0}^{(9)}=t_{8},\ \ \ s_{1}^{(9)}=-t_{8}-w_{0}^{(9)},\ \ \ s_{2}^{(9)}=t_{9},\]  
\[s_{3}^{(9)}=-t_{7}+t_{8}-t_{9},\ \ \ s_{4}^{(9)}=t_{7},\ \ \ s_{5}^{(9)}=-t_{8}+w_{1}^{(9)},\]  
\[s_{6}^{(9)}=t_{11},\ \ \ s_{7}^{(9)}=-t_{11}-w_{2}^{(9)},\ \ \ s_{8}^{(9)}=t_{12},\]  
\[s_{9}^{(9)}=-t_{10}+t_{11}-t_{12},\ \ \ s_{10}^{(9)}=t_{10},\]  
\[s_{11}^{(9)}=-t_{11}+w_{0}^{(9)},\ \ \ s_{12}^{(9)}=-t_{11}+t_{14}-t_{8},\]\[s_{13}^{(9)}=-t_{15}+t_{16}-s_{1}^{(9)}+w_{3}^{(9)},\quad s_{14}^{(9)}=-t_{12}+t_{15 }-t_{9},\]  
\[s_{15}^{(9)}=-t_{13}+t_{14}-t_{15}-s_{3}^{(9)}-s_{9}^{(9)},\]  
\[s_{16}^{(9)}=-t_{10}+t_{13}-t_{7},\quad s_{17}^{(9)}=-w_{0}^{(9)}-s_{5}^{(9)}+w_ {3}^{(9)},\]  
\[s_{18}^{(9)}=t_{8}-w_{4}^{(9)},\quad s_{19}^{(9)}=-w_{0}^{(9)}+s_{5}^{(9)}+w_{2 }^{(9)}+w_{4}^{(9)},\]  
\[s_{0}^{(9)}=t_{8},\ \ \ s_{1}^{(9)}=-t_{8}-w_{0}^{(9)},\ \ \ s_{2}^{(9)}=t_{9},\]0  
\[s_{0}^{(9)}=t_{8},\ \ \ s_{1}^{(9)}=-t_{8}-w_{0}^{(9)},\ \ \ s_{2}^{(9)}=t_{9},\]1  
\[s_{0}^{(9)}=t_{8},\ \ \ s_{1}^{(9)}=-t_{8}-w_{0}^{(9)},\ \ \ s_{2}^{(9)}=t_{9},\]2  
\[s_{0}^{(9)}=t_{8},\ \ \ s_{1}^{(9)}=-t_{8}-w_{0}^{(9)},\ \ \ s_{2}^{(9)}=t_{9},\]3  
\[s_{0}^{(9)}=t_{8},\ \ \ s_{1}^{(9)}=-t_{8}-w_{0}^{(9)},\ \ \ s_{2}^{(9)}=t_{9},\]4  
\[s_{0}^{(9)}=t_{8},\ \ \ s_{1}^{(9)}=-t_{8}-w_{0}^{(9)},\ \ \ s_{2}^{(9)}=t_{9},\]5  
\[s_{0}^{(9)}=t_{8},\ \ \ s_{1}^{(9)}=-t_{8}-w_{0}^{(9)},\ \ \ s_{2}^{(9)}=t_{9},\]6  
\[s_{0}^{(9)}=t_{8},\ \ \ s_{1}^{(9)}=-t_{8}-w_{0}^{(9)},\ \ \ s_{2}^{(9)}=t_{9},\]7  
where  
\[s_{0}^{(9)}=t_{8},\ \ \ s_{1}^{(9)}=-t_{8}-w_{0}^{(9)},\ \ \ s_{2}^{(9)}=t_{9},\]8  
\[s_{0}^{(9)}=t_{8},\ \ \ s_{1}^{(9)}=-t_{8}-w_{0}^{(9)},\ \ \ s_{2}^{(9)}=t_{9},\]9  
\[s_{3}^{(9)}=-t_{7}+t_{8}-t_{9},\ \ \ s_{4}^{(9)}=t_{7},\ \ \ s_{5}^{(9)}=-t_{8}+w_{1}^{(9)},\]0  
Taking into account the introduced matrix constructions, expression (21) can be written in the following form:  
\[s_{3}^{(9)}=-t_{7}+t_{8}-t_{9},\ \ \ s_{4}^{(9)}=t_{7},\ \ \ s_{5}^{(9)}=-t_{8}+w_{1}^{(9)},\]1  
where  
\[s_{3}^{(9)}=-t_{7}+t_{8}-t_{9},\ \ \ s_{4}^{(9)}=t_{7},\ \ \ s_{5}^{(9)}=-t_{8}+w_{1}^{(9)},\]2  
\[s_{3}^{(9)}=-t_{7}+t_{8}-t_{9},\ \ \ s_{4}^{(9)}=t_{7},\ \ \ s_{5}^{(9)}=-t_{8}+w_{1}^{(9)},\]3  
It is easy to see that the multiplicative complexity of calculating expression (23) is 36.