Automatic Algorithms Optimization via Fast Matrix Exponentiation

http://kukuruku.co/hub/algorithms/automatic-algorithms-optimization-via-fast-matrix-exponentiation.html

by roberta • 12 years ago

46 6 12 years ago

msandford• 12 years ago

This is very, very cool. Moving this kind of intelligence into the compiler and runtime is one of the things I desperately wanted to do in grad school. The academic machine ground that desire out of me in short order, but I still have a tremendous love of the work.

sridharvembu• 12 years ago

Are you working on compilers and runtimes? If you are interested in doing this, please shoot me an email svembu at zoho

jwmerrill• 12 years ago

This is great when your inner loop is calculating the nth Fibonacci number, but I'm skeptical that there are all that many practically occurring inner loops that are linear recurrences where the author of the code has not already recognized them as such.

dignati• 12 years ago

The language he describes is not Turing-complete, which limits the number of use cases. Still very interesting when you have such a situation.

gwern• 12 years ago

im3w1l• 12 years ago

Have you considered doing matrix decompositions for faster exponentiation? I guess the floating point handling would be hard to get right though.

Automatic Algorithms Optimization via Fast Matrix Exponentiation

Related Stories