# Benefits of matrix multiply over inversion

I have two variations of an iterative algorithm. All the steps of both algorithms are equivalent except one. In this step:

Algorithm 1 needs to compute the matrix $ABA^T$ for matrices $A \in \mathbb{R}^{p \times p}$ and $B \in \mathbb{R}^{p \times p}$;

Algorithm 2 needs to invert the $p \times p$ matrix $C$.

My question is: assuming that these steps led to the exact same iterates of the algorithm (i.e., they do not change the convergence properties), would there be any benefit to using Algorithm 1? If so, what?

As far as I can tell, Algorithm 1 requires only matrix multiples which can be easily parallelized. However, it's not clear to me that Algorithm 1 would be more memory efficient since one must compute and store $AB$ to then multiply it by $A^T$.

Edit: Assume that in general, these matrices are non-sparse.

• Are these matrices sparse?
– 56th
Commented May 24, 2017 at 4:47
• @56th edited question to address this point (which I should have earlier, apologies). No, these matrices are not sparse. Commented May 24, 2017 at 5:03
• @user23658 Do you need to form the product and inverse explicitly or you just need to compute their action on a given vector? Commented May 24, 2017 at 7:26
• I would need both computed explicitly. Commented May 24, 2017 at 16:41

It really depends on a lot of factors. Not knowing the problem, my concerns are these:

• The magnitude of $p$ will dictate a lot about how fast things run. I would think 2 multiplies would be faster than an inversion, although for sufficiently large matrices the inversion and multiply algorithms can be tuned to be about the same.
• If $C$ becomes near singular, inversion will be very imprecise or impossible.
• If $C$ is orthogonal, computing the inverse would be much simpler.
• Regarding your first point -- couldn't the matrix multiply be parallelized more easily than the inversion? I would imagine that if $p$ were large, this may be helpful. Commented May 24, 2017 at 16:42