Automatic Algorithms Optimization via Fast Matrix Exponentiation (2015)
So, compilers can do this, and do do this, depending on the language and it&#x27;s guarantees.<p>GCC and LLVM use a chain of recurrence algebra and form for symbolic analysis that could easily represent this (or be extended to).
But they probably won&#x27;t bother any time soon.<p>To understand why requires a little more detail first:<p>The statement &quot;However, compilers do not replace the computational algorithm, written by a human, by a more asymptotically efficient one.&quot;<p>is mostly wrong.<p>They generally do where they are allowed. They just aren&#x27;t often allowed, or it&#x27;s not worth it.<p>There are languages that are playing with this even more heavily.<p>But whether it&#x27;s a good idea, eh.<p>In numerics in particular, people often pick their algorithms very carefully for stability&#x2F;etc reasons.<p>For more generic things like sorts, a lot of this gets hidden in standard libraries anyway.<p>For things nobody could really complain about, the compilers do idiom recognition of things like memcpys, string compares, etc and replace them.<p>In any case, the problem is not recognizing and replacing the algorithm or idiom. The problem is deciding when doing so actually serves your users well.<p>Going back up, when we first implemented scalar evolutions in GCC, we supported everything you can think of - closed form polynomial functions, matrices, mixers.<p>In the end though, we were spending a lot of time handling cases that were very rare, mostly optimal as written anyway (so not useful for the optimizer), but still required exponential time solving&#x2F;etc to do anything with.<p>So a lot of that code was removed.<p>Could you handle matrix exponentiation because it&#x27;s fast? Sure.<p>But it&#x27;s unlikely to be worth it.