Spawn, Tigerspike's generic multithreading library developed for Orthohack and other cool stuff yet to come, is generic enough that we thought it should have its own project page. So here it is. (The code is a bit more advanced than was used in the latest Orthohack release, which had it built in.)
Sunday, February 24, 2013
Saturday, December 1, 2012
A Universal Transform Generator
Source code for 32-bit and 64-bit Linux is here on Github.
If you just want to see a demo, see the video entitled "Orthohack in Action". (This is for impatient people who heard about it from a friend and think it can't possibly work. But if you really want to understand how it works, then please watch the videos in sequence below.)
If you're interested in optimizing or analyzing any sort of fixed-size real-valued orthobasis transform in any number of dimensions and with floating-point or fixed-point, then Orthohack is for you: Fourier, wavelet, curvelet, noiselet, brushlet, countourlet, ridgelet, or any other "let" for that matter! Even nonorthogonal transforms are allowed. Complex numbers or quaternions could be added with some modest code changes.
Imagine that you had a machine which would create a very precise (errors often smaller than 1 part in 10^14 with 64-bit floating-point) and performant transform algorithm, given only a database of the orthobasis vectors themselves, pregenerated to a sufficiently high resolution. Imagine, furthermore, that the resulting transform was available in floating-point and fixed-point varieties, with formal verification available for the latter. And finally, it could produce a listing of every numerical constant, add, and multiply used in the transform, so that you might export it for further analysis. That, in a nutshell, is Orthohack.
In 1999, Matteo Frigo published "A Fast Fourier Transform Compiler". In it, he described a novel method for discovering faster Fourier transforms by automating the optimization of operation trees of various algorithms of human origin. His optimized FFT "codelets" are now a cornerstone of the Fastest Fourier Transform in the West. For its part, Orthohack is targeted at the more complicated transforms discovered more recently, some of which listed above.
In August of 2012, it occurred to me that a similar line of reasoning could apply to any basis transform (Fourier or otherwise, orthogonal or not) in the absence of any preexisting algorithm whatsoever: one could, given sufficiently precise representations of a set of basis vectors, create a usefully performant (as in, many times faster than brute force) transform algorithm whose precision was theoretically unlimited, given sufficient storage and computer power.
Almost 4 months later, thanks to the pioneering vision of Tigerspike under the auspices of CEO Luke Janssen and my friend Dr. Stuart Christmas, Head of Future Technologies, Orthohack has been produced for public benefit under very generous licensing terms which are free of royalties (see file "COPYING"). It could definitely benefit from a slick user interface, but at least the performance appears to be solid.
This is a dynamic project. I'm currently in the process of completely reengineering the transform generator in order to produce more efficient transforms. This might take a few months. In the meantime, play around with it and see what you can do...
Videos
Click the links below in series. Each video has a link to the next one in the YouTube description. (I was previously embedding them in this page, but the load latency was too high.)
1. A Universal Transform Generator
2. Modules
3. Denoising of Ratios and Samples
4. Hierarchical Ratio Analysis: Binomial Discovery
5. Hierarchical Ratio Analysis: Binomial Prioritization & Nesting
6. Universal Transform Engine
7. Other Uses
8. Orthohack in Action
9. Basis Vector Database Construction with GNU Octave
10. The Preprocessor
11. The Postprocessor
12. The Verifier
13. The Literalizer
14. Customizing the Demo
15. A Simple Floating-Point Transform
16. A Parallelizable Floating-Point Transform
If you just want to see a demo, see the video entitled "Orthohack in Action". (This is for impatient people who heard about it from a friend and think it can't possibly work. But if you really want to understand how it works, then please watch the videos in sequence below.)
If you're interested in optimizing or analyzing any sort of fixed-size real-valued orthobasis transform in any number of dimensions and with floating-point or fixed-point, then Orthohack is for you: Fourier, wavelet, curvelet, noiselet, brushlet, countourlet, ridgelet, or any other "let" for that matter! Even nonorthogonal transforms are allowed. Complex numbers or quaternions could be added with some modest code changes.
Imagine that you had a machine which would create a very precise (errors often smaller than 1 part in 10^14 with 64-bit floating-point) and performant transform algorithm, given only a database of the orthobasis vectors themselves, pregenerated to a sufficiently high resolution. Imagine, furthermore, that the resulting transform was available in floating-point and fixed-point varieties, with formal verification available for the latter. And finally, it could produce a listing of every numerical constant, add, and multiply used in the transform, so that you might export it for further analysis. That, in a nutshell, is Orthohack.
In 1999, Matteo Frigo published "A Fast Fourier Transform Compiler". In it, he described a novel method for discovering faster Fourier transforms by automating the optimization of operation trees of various algorithms of human origin. His optimized FFT "codelets" are now a cornerstone of the Fastest Fourier Transform in the West. For its part, Orthohack is targeted at the more complicated transforms discovered more recently, some of which listed above.
In August of 2012, it occurred to me that a similar line of reasoning could apply to any basis transform (Fourier or otherwise, orthogonal or not) in the absence of any preexisting algorithm whatsoever: one could, given sufficiently precise representations of a set of basis vectors, create a usefully performant (as in, many times faster than brute force) transform algorithm whose precision was theoretically unlimited, given sufficient storage and computer power.
Almost 4 months later, thanks to the pioneering vision of Tigerspike under the auspices of CEO Luke Janssen and my friend Dr. Stuart Christmas, Head of Future Technologies, Orthohack has been produced for public benefit under very generous licensing terms which are free of royalties (see file "COPYING"). It could definitely benefit from a slick user interface, but at least the performance appears to be solid.
This is a dynamic project. I'm currently in the process of completely reengineering the transform generator in order to produce more efficient transforms. This might take a few months. In the meantime, play around with it and see what you can do...
Videos
Click the links below in series. Each video has a link to the next one in the YouTube description. (I was previously embedding them in this page, but the load latency was too high.)
1. A Universal Transform Generator
2. Modules
3. Denoising of Ratios and Samples
4. Hierarchical Ratio Analysis: Binomial Discovery
5. Hierarchical Ratio Analysis: Binomial Prioritization & Nesting
6. Universal Transform Engine
7. Other Uses
8. Orthohack in Action
9. Basis Vector Database Construction with GNU Octave
10. The Preprocessor
11. The Postprocessor
12. The Verifier
13. The Literalizer
14. Customizing the Demo
15. A Simple Floating-Point Transform
16. A Parallelizable Floating-Point Transform
Subscribe to:
Posts (Atom)