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


1 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.