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.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Not if you use an iterative method like conjugate gradients or (since your matrix is not symmetric) GMRES. $\endgroup$– Christian ClasonOct 13 '18 at 16:06
Add a comment
|
$\begingroup$
$\endgroup$
5
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.
answered Oct 14 '18 at 20:37
-
$\begingroup$ Does this really work if matrix $B$ is NxM and not NxN? The matrix multiplication shrinks the system from NxN to MxM. $\endgroup$ 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$ 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$ 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$– GoHokiesOct 15 '18 at 14:11
-
$\begingroup$ Thanks for this detailed answer. Now I got it and it seems to work. $\endgroup$ Oct 18 '18 at 12:03