How to solve linear system of form $(A \otimes B + C^{T}C)x = b$ when $A \otimes B$ is too large to compute?
Solution 1:
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