# Fast multiplication of highly structured matrix

I want to compute a fast matrix-vector product using a matrix $T$ which has a peculiar quasi-Hankel structure. For example, \begin{equation} T_2= \left( \begin{array}{c|ccc|cccccc} a & b & c & d & e & f & g & h & i & j\\\hline b & e & f & h & 0 & 0 & 0 & 0 & 0 & 0\\ c & f & g & i & 0 & 0 & 0 & 0 & 0 & 0\\ d & h & i & j & 0 & 0 & 0 & 0 & 0 & 0\\\hline e & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ f & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ g & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ h & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ i & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ j & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right). \end{equation} \begin{equation*} T_3=\left( \begin{array}{c|ccc|cccccc|cccccccccc} a & b & c & d & e & f & g & h & i & j & k & l & m & n & o & p & q & r & s & t\\\hline b & e & f & h & k & l & m & o & p & r\\ c & f & g & i & l & m & n & p & q & s\\ d & h & i & j & o & p & q & r & s & t\\\hline e & k & l & o\\ f & l & m & p\\ g & m & n & q \\ h & o & p & r\\ i & p & q & s\\ j & r & s & t\\\hline k & \\ l & \\ m & \\ n & \\ o & \\ p & \\ q & \\ r & \\ s & \\ t \end{array} \right) \end{equation*} Larger matrices $(T_4,T_5,...)$ have the same block structure; in fact, each successive $T_i$ is contained as a partial block of all $T_j,j>i$ (see above examples). All of the unique elements are contained in the first column or row, but the matrix does not possess classical Hankel/Toeplitz/etc. structure typical of fast structured matrix vector multiplication. This matrix arises from a convolution of a certain sort, so I am convinced that the matrix-vector product can be computed in $\mathcal{O}(N\log N)$ time or something close rather than $\mathcal{O}(N^2)$. I'd appreciate the input of others, or potentially helpful references.

Edit: The block structure is controlled by the parameter $P$ so that the matrix $T_P$ has a $(P+1)\times(P+1)$ upper left triangular block structure. The $p$th row or column block is of dimension $(p+1)(p+2)/2$.

• The product can be performed in almost linear time. Look this reference. – The Doctor Dec 15 '17 at 22:36
• I am aware of those types of algorithms but the standard algorithms referred to in the reference do not apply here due to the particular structure of these matrices. I think maybe my use of "quasi-Hankel" might be confusing. All I meant is that the blocks along the upper block antidiagonals contain the same matrix elements, not necessarily that the matrices themselves are identical. – sssssssssssss Dec 15 '17 at 23:09
• Looking at $T_3$, doesn't it mean your matrix has $<N\times (P+1)$ nonzero elements, $\ll N^2$? So the direct straightforward matrix-vector product will take $N(P+1)$ operations. I'm not sure how $P+1$ compares to $\log N$, but it's not clear to me that you even need any complicated algorithm here. – Kirill Dec 16 '17 at 17:41
• The complexity is certainly $P^6$ when worked out for $T_P$. The constant is small but the scaling is suboptimal – sssssssssssss Dec 29 '17 at 1:32

Late answer but the matrix can be thought of the following sum of rank-$2$ matrices which allows for having smaller block sizes as the number of blocks increase.
\begin{align*} c_{20}=\left( \begin{array}{cc} \frac{a}2 & 1 \\ b & 0\\ c & 0\\ d & 0\\ e & 0\\ \vdots&\vdots\\ r & 0\\ s & 0\\ t & 0 \end{array} \right) \left( \begin{array}{cccccccccccccccc} 1&0&0&0&0&\cdots&0&0&0&\\\frac{a}2 & b & c & d & e &\cdots & r & s & t \end{array} \right)\begin{pmatrix}x_1\\\vdots\\x_{20}\end{pmatrix}+\\ \left( \begin{array}{cc} \frac{e}2 & 1 \\ f & 0\\ h & 0\\ k & 0\\ l & 0\\ m & 0\\ o & 0\\ p & 0\\ r & 0 \end{array} \right) \left( \begin{array}{cccccccccccccccc} 1&0&0&0&0&0&0&0&0&\\\frac{e}2 & f & h & k & l &m & o & p & r \end{array} \right)\begin{pmatrix}x_2\\\vdots\\x_{10}\end{pmatrix}+\\\textrm{etc.} \\ \end{align*}