2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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} $$ $\endgroup$ – user2457602 May 23 '18 at 22:23
  • $\begingroup$ 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. $\endgroup$ – deasmhumnha May 24 '18 at 1:14
  • $\begingroup$ 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$. $\endgroup$ – user2457602 May 25 '18 at 12:20
  • $\begingroup$ I was thinking CG on the original system, the so-called normal equation form of QP. $\endgroup$ – deasmhumnha May 25 '18 at 17:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.