1
$\begingroup$

On the Wikipedia article for galactic algorithm (an algorithm that only becomes efficient when the inputs are so large that the algorithm is not used in practice), one of the use cases is that

Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical.

What are some examples of this happening?

I'm looking specifically for impractical algorithms that became practical because problem sizes got larger or computers got faster, and not because of improvements to the algorithm itself that made it practical.

$\endgroup$
3
  • $\begingroup$ If the problem size becomes larger, not sure this could make the computation more feasible? It seems only computers going faster could help? $\endgroup$
    – Frank
    May 19, 2023 at 18:21
  • $\begingroup$ @Frank The point, I think, is that a problem may get to be large enough that the "Galactic" algorithm is actually faster than the traditional algorithm. Yes, faster computers will be necessary, but at some point the GA is faster than the TA and we still switch since there's no point in wasting cycles. $\endgroup$
    – Mark Olson
    May 19, 2023 at 21:54
  • $\begingroup$ @MarkOlson OK, I see. $\endgroup$
    – Frank
    May 19, 2023 at 22:17

1 Answer 1

2
$\begingroup$

One example would be Strassen’s matrix multiplication algorithm which can be more efficient than the conventional $O(n^{3})$ algorithm for large enough matrices. Unfortunately, there are numerical stability issues that can make it unsuitable in many applications.

$\endgroup$
2
  • 1
    $\begingroup$ Strassen’s algorithm can save time even for quite small matrices. I don't think it was used immediately on its publication in 1969, but it would have been obvious from the beginning that it could be useful in practice. It doesn't have the huge hidden constant factors that galactic algorithms typically do. $\endgroup$
    – benrg
    May 27, 2023 at 19:05
  • $\begingroup$ See also here: eprint.iacr.org/2013/107.pdf ; the number of arithmetical operations needed by Stassen algorithm is $7n^5-6n^2$, so it cannot be considered a galactic algorithm (where the hidden constant are in the order of the atoms of the Universe); moreover several efficient variant are proposed and the numerical stability is not an issue over a finite field. However, it is true that on current architectures, a highly optimized traditional multiplication can overcome Strassen method for matrices of order 512, see t.ly/lBP5 $\endgroup$
    – user6530
    May 28, 2023 at 15:46

Your Answer

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

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