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.
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