<p>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.</p>

<p>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.<br>
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).</p>

CC BY-SA 3.0
2014-12-01T20:34:37.693Z
2014-12-01T20:34:37.693Z
Thomas Klimpel
<p>Let <span class="math-container">$A_{i}$</span>, <span class="math-container">$B_{i}$</span> be a sequence of <a href="http://en.wikipedia.org/wiki/Circulant_matrix" rel="nofollow noreferrer">circulant matrices</a> of size <span class="math-container">$n \times n$</span>.</p>
<p>We know that <span class="math-container">$\sum_{i=1}^{n}A_{i}B_{i}$</span> can be calculated in quadratic time (use FFT to diagonalize and add the diagonal matrices and apply IFFT).</p>
<p>Supposing <span class="math-container">$D$</span> is an arbitrary diagonal matrix (for simplicity, let <span class="math-container">$r$</span> be <span class="math-container">$n$</span>th root of unity and consider the diagonal elements as all distinct powers less than <span class="math-container">$n$</span> of <span class="math-container">$r$</span>).</p>
<p>What is the complexity of <span class="math-container">$\sum_{i=1}^{n}A_{i}DB_{i}$</span>? I suspect it to be quadratic since I am including the same diagonal matrix(<span class="math-container">$O(n)$</span> terms) in each term.</p>
<p>Consider <span class="math-container">$R$</span> a <a href="http://en.wikipedia.org/wiki/Circulant_matrix" rel="nofollow noreferrer">circulant matrix</a> of size <span class="math-container">$n \times n$</span> with first row made of distinct powers less than <span class="math-container">$n$</span> of <span class="math-container">$r$</span>. Let <span class="math-container">$X_{i}$</span> and <span class="math-container">$Y_{i}$</span> for <span class="math-container">$i=1\rightarrow n$</span> be full-rank diagonal matrices.</p>
<p>What is the complexity of <span class="math-container">$\sum_{i=1}^{n}X_{i}RY_{i}$</span>? Again I suspect this to be quadratic.</p>
<p>The matrices <span class="math-container">$D$</span> and <span class="math-container">$R$</span> that are defined with respect to <span class="math-container">$r$</span> is artificial. I am looking for the case of general diagonal <span class="math-container">$D$</span> and general full-rank <a href="http://en.wikipedia.org/wiki/Circulant_matrix" rel="nofollow noreferrer">circulant</a> <span class="math-container">$R$</span>.</p>

<ds.algorithms><matrix-product>
Multiplication of circulant matrices with a diagonal matrix
Turbo
# Multiplication of circulant matrices with a diagonal matrix

(Asked by: username_0 on 2011-10-05)

Let $A\_{i}$, $B\_{i}$ be a sequence of [circulant matrices](http://en.wikipedia.org/wiki/Circulant_matrix) 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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Circulant_matrix) $R$.

**Tags:** ds.algorithms, matrix-product


---

## 1 answers

### Answer by username_1 on 2014-12-01. Score: 3 | Accepted answer

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


---

