# How to solve linear system of form $(A \otimes B + C^{T}C)x = b$ when $A \otimes B$ is too large to compute?

For the given linear system:

$$(A \otimes B + C^{T}C)x = b$$

where $\otimes$ is the Kronecker product, $A$ and $B$ are dense and symmetric positive-definite, and $C^{T}C$ is a sparse symmetric block diagonal, is there a way I can determine $x$ in a way that takes advantage of the symmetric block structure of $A \otimes B$ and $C^{T}C$ without requiring explicit computation of those terms?

I'm particularly interested in the case where the sizes of the diagonal blocks in $C^{T}C$ are the same size as $B$.

I have attempted to implement the conjugate gradient method but have found it converges far too slowly for my purposes, so was looking to see if there are any alternative techniques I have overlooked. Many thanks for any assistance.

• Are the diagonal blocks in $C^TC$ the same? Also, is $b \neq 0$? Jul 25 '15 at 19:03
• @Calle The diagonal blocks are not necessarily the same, but I am aware of a solution for when they are all equal. $b$ can take any form, but again, if particular special cases admit a solution then that would be of interest in the absence of a more general solution. Jul 25 '15 at 19:23
• I have not read it, but I wonder if a recent paper by Simoncini and Benzi may be useful: arxiv.org/abs/1503.02615. You could, of course, take the function to be $f(z) = z^{-1}$, and then I bet certain simplifications could be made. Sep 21 '15 at 18:12

I would suggest premultiplying your system with $$I \otimes B^{-1}$$, either before you begin to solve, or as a preconditionner for the conjugate gradient. The system would look like:
$$((I \otimes B^{-1}) (A \otimes B) + (I \otimes B^{-1}) C^TC)x = I \otimes B^{-1} b$$ $$\Longleftrightarrow (A \otimes I + (I \otimes B^{-1}) C^TC)x = I \otimes B^{-1} b$$
which is a sparse system because $$I \otimes B^{-1}$$ is block-diagonal and $$A \otimes I$$ is sparse