I have a symmetric circulant matrix $C \in \mathbb{R}^{n\times n}$, a sparse matrix $G \in \mathbb{R}^{m\times n}$, and a vector $x \in \mathbb{R}^{2m\times 1}$. I need to find the most numerically efficient way to calculate $M=Ax$. Where:
\begin{equation*} A = \frac{1}{2} \begin{bmatrix} GC^{-1}(GC^{-1})^T & -GC^{-1}(GC^{-1})^T \\ -GC^{-1}(GC^{-1})^T & GC^{-1}(GC^{-1})^T \\ \end{bmatrix} \end{equation*}
Since $C$ is circulant, I know that $C^{-1}p = F^{-1}[\frac{F(p)}{F(c)}]^T$ which can be calculated very efficiently using the fast Fourier transform (FFT). Note $c$ is the first column of $C$. Perhaps there is an equivalent formula I can use for matrix multiplication to help me find $M$?
If it helps, I know I can rewrite the expression for $A$ as:
\begin{equation*} 2A =\begin{bmatrix}I \\ -I \end{bmatrix} GC^{-2}G^T \begin{bmatrix} I & -I \end{bmatrix} \end{equation*}