# 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 May 24 '17 at 4:47
• @56th edited question to address this point (which I should have earlier, apologies). No, these matrices are not sparse. – user23658 May 24 '17 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? – GoHokies May 24 '17 at 7:26
• I would need both computed explicitly. – user23658 May 24 '17 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. – user23658 May 24 '17 at 16:42