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.

  • $\begingroup$ Are the diagonal blocks in $C^TC$ the same? Also, is $b \neq 0$? $\endgroup$
    – Calle
    Jul 25 '15 at 19:03
  • $\begingroup$ @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. $\endgroup$
    – timxyz
    Jul 25 '15 at 19:23
  • $\begingroup$ 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. $\endgroup$ 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.