1
$\begingroup$

When solving a linear system $Ax=b$ where $A=B^TCB$ do I need to form $A$ explicitly by two matrix-matrix multiplications or is there another more simple way? $C$ is a NxN matrix and not always symmetric. $B$ is NxM and not symmetric.

$\endgroup$
  • 1
    $\begingroup$ Not if you use an iterative method like conjugate gradients or (since your matrix is not symmetric) GMRES. $\endgroup$ – Christian Clason Oct 13 '18 at 16:06
5
$\begingroup$

The beauty of iterative methods is that all they require you to do is matrix-vector multiplications. In your case, the product of your matrix $A$ with a vector $y$ can be written as $z=Ay = (B^TCB)y= B^T(C(By))$ which shows that all you need is three matrix-vector products but no matrix-matrix products.

If $C$ happens to be symmetric and positive semi-definite, then so is $A$ and you can use the Conjugate Gradients method. Otherwise you probably want to think about GMRES, another iterative method.

$\endgroup$
  • $\begingroup$ Does this really work if matrix $B$ is NxM and not NxN? The matrix multiplication shrinks the system from NxN to MxM. $\endgroup$ – vydesaster Oct 15 '18 at 5:52
  • 3
    $\begingroup$ @vydesaster It "works" regardless of the dimensions. But if M is much smaller than N, you might be better off doing the matrix-matrix multiplication. $\endgroup$ – David Ketcheson Oct 15 '18 at 7:01
  • $\begingroup$ Just for my understanding. How does it work? I always thought that the dimensions must match for a matrix-vector multiplication. Is there some trick or something? $\endgroup$ – vydesaster Oct 15 '18 at 7:04
  • 1
    $\begingroup$ @vydesaster It works because matrix-matrix multiplication is an associative operation. $z = Ay = (B^TCB) y = B^T C (By) = B^T (C v) = B^T w$ where I've defined $v := By$ and $w := Cw$. As an exercise, you should (1) check that the dimensions for the matrix-vector products all match up and (2) tally up all the floating point ops and convince yourself that iterating is computationally cheaper than forming $A$ explicitly (this should be the case for large $M \ge N$). $\endgroup$ – GoHokies Oct 15 '18 at 14:11
  • $\begingroup$ Thanks for this detailed answer. Now I got it and it seems to work. $\endgroup$ – vydesaster Oct 18 '18 at 12:03

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.