Re: Automatic algorithm optimisation via fast matrix exponentiation

"Nuno Lopes" <nuno.lopes@ist.utl.pt>
Sun, 11 Jan 2015 19:22:03 -0000

          From comp.compilers
Related articles
Automatic algorithm optimisation via fast matrix exponentiation willvarfar@gmail.com (2015-01-11)
Re: Automatic algorithm optimisation via fast matrix exponentiation nuno.lopes@ist.utl.pt (Nuno Lopes) (2015-01-11)
| List of all articles for this month |
From: "Nuno Lopes" <nuno.lopes@ist.utl.pt>
Newsgroups: comp.compilers
Date: Sun, 11 Jan 2015 19:22:03 -0000
Organization: Compilers Central
References: 15-01-010
Keywords: optimize
Posted-Date: 11 Jan 2015 21:35:34 EST

> Lovely article:
>
> http://kukuruku.co/hub/algorithms/automatic-algorithms-optimization-via-fast-matrix-exponentiation
>
> Do any compilers do this kind of thing?


Partially, yes.


For example, LLVM has a quadratic recurrence solver (named SCEV --
scalar evolution). For this purpose, matrix exponentiation is pretty
much equivalent to recurrence solving. So, if LLVM manages to rewrite
an induction variable as a recurrence, and if it manages to compute
its closed-form, then LLVM may replace a loop with straight-line code.


I believe GCC and MSVC can do similar things, since it's a somehow required
piece of technology for automatic vectorization, which all compilers can do
to some extent these days..


Nuno


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.