Jacques Carette
The Gaussian Elimination algorithm is in fact an algorithm family - common implementations contain at least 6 (mostly independent) ``design choices''. A generic implementation can easily be parametrized by all these design choices, but this usually leads to slow and bloated code. Using MetaOCaml's staging facilities, we show how we can produce a natural and type-safe implementation of Gaussian Elimination which exposes its design choices at code-generation time, so that these choices can effectively be specialized away, and where the resulting code is quite efficient.
The final MetaOCaml code as well as a plain text version can also be downloaded. Furthermore, the output from the two specializations in that code can be see here.
The output is also available, and shows the different code produced.
Also available are three examples of Maple code. The code from figure 1 in the text (also as text), a generic version from the Domains package using fraction-free elimination (also as text), and a modular version working over finite fields (also as text).