Abstract

Gaussian Elimination: a case study in efficient genericity with MetaOCaml

 

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 parameterized 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.