Multiplication of circulant matrices with a diagonal matrix

Question

Let $A_{i}$, $B_{i}$ be a sequence of circulant matrices of size $n \times n$.

We know that $\sum_{i=1}^{n}A_{i}B_{i}$ can be calculated in quadratic time (use FFT to diagonalize and add the diagonal matrices and apply IFFT).

Supposing $D$ is an arbitrary diagonal matrix (for simplicity, let $r$ be $n$th root of unity and consider the diagonal elements as all distinct powers less than $n$ of $r$).

What is the complexity of $\sum_{i=1}^{n}A_{i}DB_{i}$? I suspect it to be quadratic since I am including the same diagonal matrix($O(n)$ terms) in each term.

Consider $R$ a circulant matrix of size $n \times n$ with first row made of distinct powers less than $n$ of $r$. Let $X_{i}$ and $Y_{i}$ for $i=1\rightarrow n$ be full-rank diagonal matrices.

What is the complexity of $\sum_{i=1}^{n}X_{i}RY_{i}$? Again I suspect this to be quadratic.

The matrices $D$ and $R$ that are defined with respect to $r$ is artificial. I am looking for the case of general diagonal $D$ and general full-rank circulant $R$.

Answer 1

This problem is essentially equivalent to matrix multiplication. Let's look at $\sum_{i=1}^{n}X_{i}RY_{i}$ first, where $X_i$ and $Y_i$ are diagonal matrices. If $A$ is the matrix with the diagonal entries of $X_i$ as the $i$-th column, and $B$ is the matrix with the diagonal entires of $Y_i$ as the $i$-th row, then the entry-wise product of $AB$ and $R$ is equal to $\sum_{i=1}^{n}X_{i}RY_{i}$. If all entries of $R$ are non-zero (even if it should not be full rank), then $AB$ can be reconstructed from $\sum_{i=1}^{n}X_{i}RY_{i}$. Hence the computational complexity of this problem is identical to the computational complexity of matrix multiplication.

For the case $\sum_{i=1}^{n}A_{i}DB_{i}$, where $A_i$ and $B_i$ are circulant matrices, we first have to apply FFT to $A_i$, $B_i$ and $D$, to get back to the case $\sum_{i=1}^{n}X_{i}RY_{i}$. We need $2n+1$ FFTs of size $n$ for this, so this adds $n^2\log n$ to the complexity.
Also in this case, it can happen that the FFT of $D$ has only very few non-zero entries. In this special case, the complexity will be quadratic times the number of non-zero entries. This can happen, if the i-th entry on the diagonal of $D$ is $r^i$, where $r$ is the $n$th root of unity. But already when $D$ has the same entries but permuted arbitrarily, the FFT of $D$ will not be sparse (in general).