Fast matrix multiplication for $a_{i,j}=a_{i-j}$ if $i\leq j$ else 0

Question

Let $A=(a_{ij})_{i,j=1,\dots,n}$ with $a_{ij}=\tilde{a}_{i-j}$ if $i\leq j$ and $a_{ij}=0$ else, where $\tilde{a}$ is an arbitrary vector.

Can I compute $Av$ for an arbitrary vector $v$ faster than with $\mathcal{O}(n^2)$ floating point operations?

Answer 1

Just for completeness, @hypernova 's hint was spot-on: In Python, the solution looks as follows:

from scipy import fft,ifft
from numpy import concatenate, zeros
def toeplitz_multiplication(a,v):
    n = len(a)
    c = concatenate((a[[0]],zeros(n),a[-1:0:-1]))
    vtilde = concatenate((v,zeros(n)))
    return ifft(fft(c)*fft(vtilde))[:n]

where a is my $\tilde{a}$. Storage and runtime requirement of this solution is $\mathcal{O}(n\log(n))$.

Intuitively (for me), the matrix multiplication is interpreted as a discrete convolution of $v$ with an extension of $\tilde{a}$ by zeros (this extension is necessary since else the lower-triangular entries would not be zeros). This convolution can then be computed using the fact that Fourier transforms turn convolutions into pointwise multiplications. Finally, the resulting vector, which is of length $2n$ because of the extension, is truncated.