How to efficently multiply a circulant matrix A $\in \{-1,+1\}^{d \times d}$ with a vector x $ \in \mathbb{R}^{d} $?

Asked Sep 15 '14 at 06:15

Active Sep 15 '14 at 12:40

Viewed 33 times

I know the way of multiplying using FFT which takes $O(dlgd)$. If you know something better please share. If you have some nontrivial method for general matrices (not circulant), then also please reply. Any suggestions related to this question will help.

edited Sep 15 '14 at 12:40

asked Sep 15 '14 at 06:15

Jagdeep

It will be sufficent for me, if you can give a better way to multiply circulant matrix A$\in {0,1}^{d\times d}$ with vector x$\in \mathbb{R}^{d}$. – Jagdeep Sep 15 '14 at 13:38

How to efficently multiply a circulant matrix A $\in \{-1,+1\}^{d \times d}$ with a vector x $ \in \mathbb{R}^{d} $?

0 Answers0