## 3 Algorithms for Toeplitz Matrix-Vector Multiplication
### Algorithm for \(N=7\)  
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}\end{bmatrix} = \begin{bmatrix}t_{6}&t_{5}&t_{4}&t_{3}&t_{2}&t_{1}&t_{0}\\ t_{7}&t_{6}&t_{5}&t_{4}&t_{3}&t_{2}&t_{1}\\ t_{8}&t_{7}&t_{6}&t_{5}&t_{4}&t_{3}&t_{2}\\ t_{9}&t_{8}&t_{7}&t_{6}&t_{5}&t_{4}&t_{3}\\ t_{10}&t_{9}&t_{8}&t_{7}&t_{6}&t_{5}&t_{4}&t_{3}\\ t_{11}&t_{10}&t_{9}&t_{8}&t_{7}&t_{6}&t_{5}&t_{4}\\ t_{12}&t_{11}&t_{10}&t_{9}&t_{8}&t_{7}&t_{6}&t_{5}\\ t_{12}&t_{11}&t_{10}&t_{9}&t_{8}&t_{7}&t_{6}.\end{bmatrix} . \tag{15}\]  
The direct method of calculating this product requires 49 multiplications and 42 additions. **Proposition 5**: _To calculate the product (15), no more than 25 multiplications are required._  
Let us introduce auxiliary matrices:  
\[\mathbf{P}_{16\times 25}^{(7)}=\mathbf{I}_{4}\oplus\mathbf{P}_{3\times 6}^{(3)} \oplus\mathbf{I}_{2}\oplus\mathbf{P}_{3\times 6}^{(3)}\oplus 1\oplus\mathbf{P}_{3 \times 6^{\prime}}^{(3)}\]  
Figure 4: Data flow diagram of the algorithm (14) for \(N=6\). \[\mathbb{P}_{7\times 16}^{(7)}=\left[ \begin{array}{cccccccc}1&1&1&&&&1\\ &1&1&&&&1\\ &&1&&1&&1&1\\ &&1&&1&1\\ &&1&1&&1\\ 1&1&1&&1&1\\ \end{array} \right],\]  
\[\mathbb{T}_{16\times 7}^{(7)}= \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&1&1\\ 1&1\\ &&1\\ &&1\\ \end{bmatrix} ,\]  
\[\mathbb{T}_{25\times 16}^{(7)}=\mathbb{I}_{4}\oplus\mathbb{T}_{6\times 3}^{(3)} \oplus\mathbb{I}_{2}\oplus\mathbb{T}_{6\times 3}^{(3)}\oplus 1\oplus\mathbb{T}_{6 \times 3^{\prime}}^{(3)}\]  
and  
\[\mathbb{D}_{25}^{(7)}=\text{diag}\Big{(}s_{0}^{(7)},\ \ s_{1}^{(7)},\ \ \ldots,\ \ s_{24}^{(7)}\Big{)}, \tag{16}\]  
\[s_{0}^{(7)}=-t_{6}-t_{10}+t_{12}+w_{0}^{(7)},\ \ s_{1}^{(7)}=t_{6},\ \ s_{2}^{(7)}=t_{7},\]  
\[s_{3}^{(7)}=t_{11},\ \ \ s_{4}^{(7)}=t_{5},\ \ \ s_{5}^{(7)}=-w_{1}^{(7)}+t_{7},\]  
\[s_{6}^{(7)}=t_{6},\ \ \ s_{7}^{(7)}=-t_{4}+t_{5}-t_{6},\ \ \ s_{8}^{(7)}=t_{4},\]  
\[s_{9}^{(7)}=-t_{5}-w_{2}^{(7)},\ \ \ s_{10}^{(7)}=t_{10},\ \ \ s_{11}^{(7)}=t_{9},\]  
\[s_{12}^{(7)}=-t_{5}+t_{8},\ \ \ s_{13}^{(7)}=t_{10}+w_{0}^{(7)}+w_{1}^{(7)},\]  
\[s_{14}^{(7)}=-t_{6}+t_{9},\ \ \ s_{15}^{(7)}=-t_{7}+t_{8}-t_{9}-t_{10}-s_{7}^{(7 )},\]  
\[s_{16}^{(7)}=-t_{4}+t_{7},\ \ \ s_{17}^{(7)}=-t_{9}+w_{3}^{(7)},\ \ \ s_{18}^{(7)}=t_{8},\]  
\[s_{19}^{(7)}=t_{2}-t_{5},\ \ \ s_{20}^{(7)}=-t_{2}+w_{3}^{(7)},\ \ \ s_{21}^{(7)}=t_{3}-t_{6},\]  
\[\mathbb{D}_{25}^{(7)}=\text{diag}\Big{(}s_{0}^{(7)},\ \ s_{1}^{(7)},\ \ \ldots,\ \ s_{24}^{(7)}\Big{)}, \tag{16}\]0  
\[\mathbb{D}_{25}^{(7)}=\text{diag}\Big{(}s_{0}^{(7)},\ \ s_{1}^{(7)},\ \ \ldots,\ \ s_{24}^{(7)}\Big{)}, \tag{16}\]1  
where  
\[\mathbb{D}_{25}^{(7)}=\text{diag}\Big{(}s_{0}^{(7)},\ \ s_{1}^{(7)},\ \ \ldots,\ \ s_{24}^{(7)}\Big{)}, \tag{16}\]2  
\[\mathbb{D}_{25}^{(7)}=\text{diag}\Big{(}s_{0}^{(7)},\ \ s_{1}^{(7)},\ \ \ldots,\ \ s_{24}^{(7)}\Big{)}, \tag{16}\]3  
Taking into account the introduced matrix constructions, expression (3) can be written in the following form:  
\[\mathbb{D}_{25}^{(7)}=\text{diag}\Big{(}s_{0}^{(7)},\ \ s_{1}^{(7)},\ \ \ldots,\ \ s_{24}^{(7)}\Big{)}, \tag{16}\]4where  
\[ \begin{array}{l}\mathbf{X}_{7\times 1}=[x_{0},x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}]^{ T},\\ \mathbf{Y}_{7\times 1}=[y_{0},y_{2},y_{3},y_{3},y_{4},y_{5},y_{6}]^{ T}.\end{array} \]  
It is easy to see that the multiplicative complexity of calculating expression (17) is 25. The correctness of expression (17) can be checked by a simple substitution:  
\[\mathbf{T}_{7}=\mathbf{P}_{7\times 16}^{(7)}\mathbf{P}_{16\times 25}^{(7)} \mathbf{D}_{25}^{(7)}\mathbf{T}_{25\times 16}^{(7)}\mathbf{T}_{16\times 7}^{(7)},\]  
where \(\mathbf{T}_{7}\) is a \(7\times 7\) Toeplitz matrix. Expression (17) defines a reduced multiplicative complexity algorithm for calculating the matrix-vector product with a seventh-order Toeplitz matrix. **Remark 5**. : _The proposed algorithm (17) requires only 25 multiplications and 87 additions.