# Solving linear system with matrix multiplication

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.

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

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.
• Does this really work if matrix $B$ is NxM and not NxN? The matrix multiplication shrinks the system from NxN to MxM. – vydesaster Oct 15 '18 at 5:52
• @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$). – GoHokies Oct 15 '18 at 14:11