×

Fixed-size quadruples for a new, hardware-oriented representation of the 4D Clifford algebra. (English) Zbl 1251.15028

Summary: The Clifford algebra (geometric algebra) offers a natural and intuitive way to model geometry in fields as robotics, machine vision and computer graphics. This paper proposes a new representation based on fixed-size elements \((quadruples)\) of 4D Clifford algebra and demonstrates that this choice leads to an algorithmic simplification which in turn leads to a simpler and more compact hardware implementation of the algebraic operations. In order to prove the advantages of the new, quadruple-based representation over the classical representation based on homogeneous elements, a coprocessing core supporting the new fixed-size Clifford operands, namely Quad-CliffoSor (Quadruple-based Clifford coprocesSor) was designed and prototyped on an FPGA board. Test results show the potential to achieve a \(23\times\) speedup for Clifford products and a \(33\times\) speedup for Clifford sums and differences compared to the same operations executed by a software library running on a general-purpose processor.

MSC:

15A66 Clifford algebras, spinors
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Mann, N. Litke, T. DeRose, A Coordinate-Free Geometry adt. Technical Report CS-97-15, University of Waterloo, 1997.
[2] W. K. Clifford, On the classification of geometric algebras. In Mathematical Papers (1882), Tucker R., (Ed.), Macmillian, London, pp. 397-401.
[3] Daniel Fontijne, Efficient implementation of geometric algebra. Ph.D. Thesis, University of Amsterdam, 2007.
[4] Silvia Franchini, Giorgio Vassallo, Filippo Sorbello, A brief introduction to Clifford algebra. Technical Report N. 2/2010, Dipartimento di Ingegneria Informatica, Universitá degli Studi di Palermo, 2010, http://www.dinfo.unipa.it/\(\sim\)franchini/CliffTechRep.pdf . · Zbl 1251.15028
[5] L. Dorst, D. Fontijne, and S. Mann, Geometric Algebra for Computer Science: An Object Oriented Approach to Geometry. Morgan Kaufmann, 2007.
[6] L. Dorst, S. Mann, Geometric Algebra: a computational framework for geometrical applications (part 1: algebra). IEEE Computer Graphics and Applications, Volume 22 Issue 4 July-August 2002, pp. 58 - 67.
[7] L. Dorst, S. Mann, Geometric Algebra: a computational framework for geometrical applications (part 2: applications). IEEE Computer Graphics and Applications, Volume 22 Issue 3 May-June 2002, pp. 24 - 31.
[8] D. Fontijne, L. Dorst, Modeling 3D Euclidean geometry. In IEEE Computer Graphics and Applications, Volume 23 Issue 2 Mar/Apr 2003, pp. 68 - 78.
[9] L. Dorst, Honing geometric algebra for its use in the computer sciences. In: Geometric Computing with Clifford Algebra, G. Sommer, editor, Springer ISBN 3-540-41198-4, 2001. · Zbl 1073.68846
[10] J. Suter, Geometric Algebra Primer. http://www.jaapsuter.com/paper/ga_primer.pdf , March 2003.
[11] Hestenes D.: New Foundations For Classical Mechanics. Kluwer Academic Publishing, Dordrecht (1986) · Zbl 0612.70001
[12] Hestenes D., Sobczyk G.: Clifford Algebra to Geometric Calculus: A Unified Language for Mathematics and Physics. Kluwer Academic Publishing, Dordrecht (1987) · Zbl 0541.53059
[13] Silvia Franchini, Antonio Gentile, Filippo Sorbello, Giorgio Vassallo, Salvatore Vitabile, An Embedded, FPGA-based Computer Graphics Coprocessor with Native Geometric Algebra Support. Integration, The VLSI Journal, Vol. 42 No. 3 pp. 346-355, ISSN: 0167-9260, doi: 10.1016/j.vlsi.2008.09.010 , 2009. · Zbl 1251.15028
[14] D. Fontijne, Gaigen 2: a geometric algebra implementation generator. In Proceedings of GPCE ’06, 2006.
[15] C. Perwass, CLU: Clifford algebra library and utilities. The CLU Project web page. http://www.perwass.de/cbup/clu.html .
[16] P. Lounesto, The CLICAL Home Page. http://www.helsinki.fi/\(\sim\)lounesto/CLICAL.htm .
[17] R. Ablamowicz, Clifford algebra computations with Maple. Proceedings of the CAP Summer School in Theoretical Physics, Geometric (Clifford) Algebras in Physics, Banff, Alberta, Canada as CLIFFORD (GEOMETRIC) ALGEBRAS with applications in Physics, Mathematics, and Engineering, William E. Baylis, Editor, Birkhauser, Boston, 1996, pp. 463 - 502.
[18] R. Ablamowicz and B. Fauser, The homepage of the package cliffordlib, http://math.tntech.edu/rafal/cliff9/ , 2005. · Zbl 1099.65520
[19] P. Leopardi, The GluCat Home Page, http://glucat.sourceforge.net/ .
[20] Daniel Fontijne, Tim Bouma, Leo Dorst, GAIGEN: a Geometric Algebra Implementation Generator. University of Amsterdam, NL, July 2002, http://www.science.uva.nl/ga/gaigen/ .
[21] S. Franchini, A. Gentile, M. Grimaudo, C.A. Hung, S. Impastato, F. Sorbello, G. Vassallo, S. Vitabile, A Sliced Coprocessor for Native Clifford Algebra Operations. Proceedings of the 10th IEEE Euromicro Conference on Digital System Design - Architectures, Methods and Tools (DSD 2007), L”ubeck, Germany, August 2007, pp. 436 - 439, ISBN/ISSN: 0-7695-2978-X, doi: 10.1109/DSD.2007.4341505 , IEEE Computer Society Press.
[22] C. Perwass, C. Gebken, G. Sommer, Implementation of a Clifford Algebra Co-Processor Design on a Field-Programmable Gate Array. In: Clifford Algebras - Applications to Mathematics, Physics, and Engineering, Series: Progress in Mathematical Physics , Vol. 34, Ablamowicz, Rafal (Ed.), 2004. · Zbl 1070.68514
[23] Dietmar Hildenbrand, Andreas Koch, Gaalop - High Performance Computing based on Conformal Geometric Algebra. In Proceedings of AGACSE 2008, 3rd International Conference on Applications of Geometric Algebras in Computer Science and Engineering, Leipzig, Germany, 2008. · Zbl 1214.68434
[24] A. Gentile, S. Segreto, F. Sorbello, G. Vassallo, S. Vitabile, V. Vullo, CliffoSor: a Parallel Embedded Architecture for Geometric Algebra and Computer Graphics. Proceedings of the IEEE International Workshop on Computer Architecture for Machine Perception (CAMP 2005), pp. 90 - 95, IEEE Computer Society Press.
[25] A. Gentile, S. Segreto, F. Sorbello, G. Vassallo, S. Vitabile, V. Vullo, CliffoSor, an innovative FPGA-based architecture for geometric algebra. Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms, ERSA 2005, pp. 211 - 217.
[26] S. Franchini, A. Gentile, F. Sorbello, G. Vassallo, S. Vitabile, An FPGA Implementation of a Quadruple-Based Multiplier for 4D Clifford Algebra. Proceedings of the 11th IEEE Euromicro Conference on Digital System Design - Architectures, Methods and Tools (DSD 2008), Parma, Italy, September 3-5, 2008, pp. 743-751, ISBN: 978-0-7695-3277-6, doi: 10.1109/DSD.2008.91 , IEEE Computer Society Press.
[27] D. Shreiner, M. Woo, J. Neider, T. Davis, and OpenGL Architecture Review Board, OpenGL Programming Guide: The Official Guide to Learning OpenGL. Version 1.4, Fourth Edition, Addison-Wesley Pub Co, 2003.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.