# Efficiently solve linear system with matrix quadratic form

Take the system $$A^TCAx=b$$ where $$A\in\mathbb{R}^{n\times m},\;C\in\mathbb{R}^{n\times n},\;x,b\in\mathbb{R}^{m}, \;m\leq n$$ and $$A^TA=I$$ and $$Cy=d$$ can be solved efficiently in general (specifically $C$ is SPD and it/it's inverse already has Cholesky decomposition). Clearly, if $m\ll n$, then it probably best to just generate and factor the new matrix, but if $m$ and $n$ are both large and $A,C$ are sparse/structured, generating this (typically dense) matrix may not be possible. While I could just use iterative techniques (CG, etc.) at this point, I was curious if there is any to use the knowledge of the inverse of $C$ to develop a more direct (and potentially more efficient) method?

For more context, $A,C$ are Kronecker products in my particular problem.

• Would it help to recognize that the solution you are looking for is also the solution of the system $$\begin{bmatrix } C & A \\ A^T & 0 \end{bmatrix}\begin{bmatrix } x \\ y \end{bmatrix} = \begin{bmatrix } 0 \\ -b\end{bmatrix}$$ May 23 '18 at 22:23
• Ha, the block matrix from QP! I didn't even see that. Doesn't seem to help much with a direct method for large $n,m$, and if anything might even suggest CG is the best bet since that is the general course of action in QP. $A^TC^{-1}A$ will probably make a good preconditioner. May 24 '18 at 1:14
• The block matrix is indefinite, so MINRES is a better choice than CG. CG would be good to use on the system $A^TC^{-1}A = b$. May 25 '18 at 12:20
• I was thinking CG on the original system, the so-called normal equation form of QP. May 25 '18 at 17:09