Gaigen 2:: a geometric algebra implementation generator

ABSTRACT

Geometric Algebra (GA) is an algebra that encodes geometry much better than standard techniques, which are mainly based on linear algebra with various extensions. Compared to standard techniques, GA has clearer semantics and a richer, more consistent language. This expresses itself, among others, in a much greater genericity of functions over the algebra. Exploiting this genericity efficiently is a problem that can be solved through generative programming.This paper describes our Geometric Algebra Implementation Generator Gaigen 2. Gaigen 2 synthesizes highly efficient GA implementations from the specification of the algebra. Functions over such algebras can be defined in a high-level coordinate-free domain-specific language, and Gaigen 2 transforms these functions into low-level coordinate-based code. This code can be emitted in any target language through a custom back-end. Benchmarks of our implementation show that the combination of GA and Gaigen 2 can rival the performance of standard geometry techniques, despite the greater abstraction and genericity of GA.To obtain this high performance, Gaigen 2 must adapt the generated code to the program that links to it. This is done via a profiling feedback loop. While running, the generated code makes a connection to the code generator. The generated code sends information about functions that should be optimized. The code generator registers this information and sends back new type information. After the program terminates, the code is regenerated according to the recorded profile. This profiling feedback technique may also be useful to implement other types of algebras.

REFERENCES

• 1: L. Dorst and D. Fontijne. An Algebraic Foundation for Object-Oriented Euclidean Geometry. ITM 2003 proceedings, 2003.
• 2: L. Dorst and S. Mann. Geometric algebra: a computation framework for geometrical applications: Part I Computer Graphics and Applications, 2002, Volume 22, May June 2002, pp. 24--31.
• 3: C. Doran and A. Lasenby. Geometric Algebra for Physicists. Cambridge University Press, 2003.
• 4: Daniel Fontijne , Leo Dorst, Modeling 3D Euclidean Geometry, IEEE Computer Graphics and Applications, v.23 n.2, p.68-78, March 2003 [doi>10.1109/MCG.2003.1185582]
• 5: Stephen Mann , Alyn Rockwood, Computing singularities of 3D vector fields with Geometric Algebra, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 6: I. Bell. Ian Bell's pages on geometric algebra. http://www.iancgbell.clara.net/maths/geoalg1.htm
• 7: R. Clint Whaley and Antoine Petitet and Jack J. Dongarra. Automated Empirical Optimization of Software and the ATLAS Project. Parallel Computing, 2001, volume 27, issue 1-2, pp 3--35.
• 8: Markus Püschel et al. SPIRAL: Code Generation for DSP Transforms. Proceedings of the IEEE, volume 93, issue 2, pp 232--275.
• 9: T. Veldhuizen. Blitz++: Object-Oriented Scientific Computing. http://www.oonumerics.org/blitz
• 10: D. Hildenbrand and E. Bayro-Corrochano and J. Zamora-Esquivel. Advanced Geometric Approach for Graphics and Visual Guided Robot Object Manipulation. Proceedings of ICRA conference, April 2005, Barcelona, Spain.
• 11: D. Tolani and A. Goswami and N. Badler. Real-time inverse kinematics techniques for anthopomorphic limbs. University of Pennsylvania, 2000.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

General Terms:
Design, Languages, Performance

Keywords:
conformal model, geometric algebra, object-oriented, profiling program transformation, synthesis from specification