0
$\begingroup$

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.

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

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.
  • Tradeoffs between memory efficiency and speed depend on your application.

All in all, I would choose multiplication.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user23658 May 24 '17 at 16:42
  • $\begingroup$ Interesting note: en.wikipedia.org/wiki/… "Because of the possibility of blockwise inverting a matrix... it can be shown that a divide and conquer algorithm that uses blockwise inversion to invert a matrix runs with the same time complexity as the matrix multiplication algorithm that is used internally.". Matrix multiplies may be able to be more parallelized, but Amdahl's Law comes into play with the overhead of setting it up. It might make sense if the matrices are large enough, but you can also get a speed increase if you use SSE. $\endgroup$ – CADJunkie May 24 '17 at 17:25
  • $\begingroup$ That is a very interesting point. Thank you for bringing that to my attention. $\endgroup$ – user23658 May 25 '17 at 0:16
2
$\begingroup$

There could be some benefits, but without knowing more details on the algorithm it is impossible to answer. For instance, the stability properties of the two algorithms could be completely different.

$\endgroup$

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.