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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Are these matrices sparse? $\endgroup$
    – 56th
    May 24, 2017 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, 2017 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, 2017 at 7:26
  • $\begingroup$ I would need both computed explicitly. $\endgroup$
    – user23658
    May 24, 2017 at 16:41

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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, 2017 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, 2017 at 17:25
  • $\begingroup$ That is a very interesting point. Thank you for bringing that to my attention. $\endgroup$
    – user23658
    May 25, 2017 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.