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. 490
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$. 945