Úlfar Erlingsson, Erich Kaltofen and David Musser. Generic Gram-Schmidt Orthogonalization by Exact Division. Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation (Zurich, Switzerland), July 1996.
Also available as an RPI tech report:
Úlfar Erlingsson, Erich Kaltofen and David Musser.
Generic Gram-Schmidt Orthogonalization by Exact Division.
Technical Report 96-02,
Department of Computer Science, Rensselaer Polytechnic Institute,
Troy, NY, 1996.
(compressed
PostScript)
Also see the online sources.
Given a vector space basis with integral domain coefficients, a variant of the Gram-Schmidt process produces an orthogonal basis using exact divisions, so that all arithmetic is within the integral domain. Zero-division is avoided by the assumption that in the domain a sum of squares of nonzero elements is always nonzero. In this paper we fully develop this method and use it to illustrate and compare a variety of means for implementing generic algorithms. Previous generic programming methods have been limited to one of compile-time, link-time, or run-time instantiation of type parameters, such as the integral domain of this algorithm, but we show how to express generic algorithms in C++ so that all three possibilities are available using a single source code. Finally, we take advantage of the genericness to test and time the algorithm using different arithmetics, including three huge-integer arithmetic packages.