## 3 Algorithms for Toeplitz Matrix-Vector Multiplication
### Algorithm for \(N=8\)  
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}\end{bmatrix} = \begin{bmatrix}t_{7}&t_{6}&t_{5}&t_{4}&t_{3}&t_{2}&t_{1}&t_{0 }\\ t_{8}&t_{7}&t_{6}&t_{5}&t_{4}&t_{3}&t_{2}&t_{1}\\ t_{9}&t_{8}&t_{7}&t_{6}&t_{5}&t_{4}&t_{3}&t_{2}\\ t_{10}&t_{9}&t_{8}&t_{7}&t_{6}&t_{5}&t_{4}&t_{3}&t_{3}\\ t_{11}&t_{10}&t_{9}&t_{8}&t_{7}&t_{6}&t_{5}&t_{4}&t_{4}\\ t_{12}&t_{11}&t_{10}&t_{9}&t_{8}&t_{7}&t_{6}&t_{5}&t_{4}\\ t_{13}&t_{12}&t_{11}&t_{10}&t_{9}&t_{8}&t_{7}&t_{6}\\ t_{14}&t_{13}&t_{12}&t_{11}&t_{10}&t_{9}&t_{8}&t_{7}\end{bmatrix}\begin{bmatrix}x_{0} \\ x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ x_{5}\\ x_{6}\\ x_{7}\end{bmatrix} . \tag{18}\]  
The direct method of calculating this product requires 64 multiplications and 56 additions. **Proposition 6**. : _To calculate the product (18), no more than 27 multiplications are required._  
Proof. : Let us introduce auxiliary matrices:  
\[\mathbf{P}_{8\times 12}^{(8)}=\mathbf{P}_{2\times 3}^{(4)}\otimes\mathbf{I} _{\mathbf{4}},\quad\mathbf{P}_{12\times 18}^{(8)}=\mathbf{I}_{3}\otimes \mathbf{P}_{4\times 6}^{(8)},\]  
\[\mathbf{P}_{4\times 6}^{(8)}=\mathbf{P}_{2\times 3}^{(4)}\otimes\mathbf{I} _{2},\quad\mathbf{P}_{18\times 27}^{(8)}=\mathbf{I}_{9}\otimes\mathbf{P}_{2 \times 3}^{(4)},\]  
and  
\[\mathbf{T}_{2\times 18}^{(8)}=\mathbf{I}_{9}\otimes\mathbf{T}_{3\times 2}^{(4)}, \quad\mathbf{T}_{18\times 12}^{(8)}=\mathbf{I}_{3}\otimes\mathbf{T}_{6 \times 4}^{(8)},\]  
\[\mathbf{T}_{6\times 4}^{(8)}=\mathbf{T}_{3\times 2}^{(4)}\otimes\mathbf{I} _{2},\]  
\[\mathbf{T}_{12\times 8}^{(8)}=\left[ \begin{array}{ccccc}&&&1\\ &&&1\\ &&&1\\ &&1&&&1\\ 1&&&1\\ &&&1\\ &&1&&&\\ &1&&&\\ 1&&&\\ 1&&&&&&\\ \end{array} \right],\]  
\[\mathbf{D}_{27}^{(8)}=\text{diag}\Big{(}s_{0}^{(8)},\;\;s_{1}^{(8)},\;\;\;\ldots,\;\;s_{26}^{(8)}\Big{)}, \tag{19}\]  
\[s_{0}^{(8)}=t_{0}+w_{0}^{(8)}-w_{1}^{(8)},\;\;\;s_{1}^{(8)}=t_{1}-t_{3}-s_{10} ^{(8)},\]  
\[s_{2}^{(8)}=t_{8}+w_{0}^{(8)}+w_{1}^{(8)},\;\;\;s_{3}^{(8)}=w_{1}^{(8)}-s_{4} ^{(8)},\]  
\[s_{4}^{(8)}=t_{3}-t_{7},\;\;\;\;s_{5}^{(8)}=-s_{4}^{(8)}+w_{2}^{(8)},\]  
\[s_{6}^{(8)}=-t_{2}+s_{4}^{(8)}+w_{2}^{(8)}+w_{4}^{(8)},\;\;\;s_{7}^{(8)}=-s_{4} ^{(8)}-w_{3}^{(8)},\]  
\[s_{8}^{(8)}=-t_{10}-s_{5}^{(8)}+w_{4}^{(8)},\;\;\;s_{9}^{(8)}=t_{4}-t_{5}-s_{1 2}^{(8)},\]  
\[s_{10}^{(8)}=t_{5}-t_{7},\;\;\;\;s_{11}^{(8)}=t_{6}-t_{8}-s_{10}^{(8)},\]  
\[s_{12}^{(8)}=t_{6}-t_{7},\;\;\;\;s_{13}^{(8)}=t_{7},\;\;\;\;s_{14}^{(8)}=t_{8}- t_{7},\]  
\[s_{15}^{(8)}=-s_{12}^{(8)}+w_{5}^{(8)},\;\;\;s_{16}^{(8)}=t_{9}-t_{7},\]\[s_{17}^{(8)}=t_{7}-t_{8}+w_{6}^{(8)},\quad s_{18}^{(8)}=-t_{4}+t_{6}-t_{10}+w_{5}^{ (8)}+w_{7}^{(8)},\]  
\[s_{0}^{(8)}=t_{0}+w_{0}^{(8)}-w_{1}^{(8)},\;\;\;s_{1}^{(8)}=t_{1}-t_{3}-s_{10} ^{(8)},\]0  
\[s_{0}^{(8)}=t_{0}+w_{0}^{(8)}-w_{1}^{(8)},\;\;\;s_{1}^{(8)}=t_{1}-t_{3}-s_{10} ^{(8)},\]1  
\[s_{0}^{(8)}=t_{0}+w_{0}^{(8)}-w_{1}^{(8)},\;\;\;s_{1}^{(8)}=t_{1}-t_{3}-s_{10} ^{(8)},\]2  
\[s_{0}^{(8)}=t_{0}+w_{0}^{(8)}-w_{1}^{(8)},\;\;\;s_{1}^{(8)}=t_{1}-t_{3}-s_{10} ^{(8)},\]3  
\[s_{0}^{(8)}=t_{0}+w_{0}^{(8)}-w_{1}^{(8)},\;\;\;s_{1}^{(8)}=t_{1}-t_{3}-s_{10} ^{(8)},\]4  
where  
\[s_{0}^{(8)}=t_{0}+w_{0}^{(8)}-w_{1}^{(8)},\;\;\;s_{1}^{(8)}=t_{1}-t_{3}-s_{10} ^{(8)},\]5  
\[s_{0}^{(8)}=t_{0}+w_{0}^{(8)}-w_{1}^{(8)},\;\;\;s_{1}^{(8)}=t_{1}-t_{3}-s_{10} ^{(8)},\]6  
\[s_{0}^{(8)}=t_{0}+w_{0}^{(8)}-w_{1}^{(8)},\;\;\;s_{1}^{(8)}=t_{1}-t_{3}-s_{10} ^{(8)},\]7  
\[s_{0}^{(8)}=t_{0}+w_{0}^{(8)}-w_{1}^{(8)},\;\;\;s_{1}^{(8)}=t_{1}-t_{3}-s_{10} ^{(8)},\]8  
Taking into account the introduced matrix constructions, expression (18) can be written in the following form:  
\[s_{0}^{(8)}=t_{0}+w_{0}^{(8)}-w_{1}^{(8)},\;\;\;s_{1}^{(8)}=t_{1}-t_{3}-s_{10} ^{(8)},\]9  
where  
\[s_{2}^{(8)}=t_{8}+w_{0}^{(8)}+w_{1}^{(8)},\;\;\;s_{3}^{(8)}=w_{1}^{(8)}-s_{4} ^{(8)},\]0 \[s_{2}^{(8)}=t_{8}+w_{0}^{(8)}+w_{1}^{(8)},\;\;\;s_{3}^{(8)}=w_{1}^{(8)}-s_{4} ^{(8)},\]1  
It is easy to see that the multiplicative complexity of calculating expression (20) is 27.