Geometric Algebra Fulcrum Library (GA-FuL for short) is a unified generic C# library for Geometric Algebra computations using any kind of scalars (floating point, rational, symbolic, etc.). GA-FuL can be used for prototyping geometric algorithms based on the powerful mathematics of geometric algebra. The GA-FuL code base can be used to perform numeric computations, symbolic manipulations, and optimized code generation.
Geometric Algebra (GA) is a powerful mathematical language that unifies many algebraic tools under the same framework of mathematical operations. Such tools include, for example, real vectors, complex numbers, quaternions, octonions, spinors, matrices, among others; along with their algebraic operations. The most important feature of GA is, however, that it unifies the geometric reasoning process among many seemingly diverse fields of application domains. Thus, Geometric Algebra acts as a Mathematical Fulcrum for geometric reasoning across scientific and engineering domains. We can use this Geometric Algebra Fulcrum to seamlessly balance the abstract ideal needs of geometric reasoning with the concrete tools of algebraic manipulation under a unifying mathematical framework.
On the other side, there is a need for software tools that act as a pivot point, i.e. a Fulcrum, for prototyping and implementing several kinds of computations on GA’s multivectors. Commonly required computations include numerical, symbolic, and code generation, among others. Writing and maintaining a separate code base for each kind is highly impractical. GA-FuL is intended to play the role of a Computational Fulcrum for prototyping algorithms and implementing software based on Geometric Algebra.
You can cite GA-FuL using this article:
@Article{Eid2024,
author = {Eid, Ahmad Hosny and Montoya, Francisco G.},
journal = {Mathematics},
title = {Developing GA-FuL: A Generic Wide-Purpose Library for Computing with Geometric Algebra},
year = {2024},
issn = {2227-7390},
month = jul,
number = {14},
pages = {2272},
volume = {12},
doi = {10.3390/math12142272},
publisher = {MDPI AG},
}The high-level design of GA-FuL targets a specific set of Core Design Intentions (CDIs). The set of CDIs is a direct result of the experience gained during the development of the predecessor system, GMac. An overview of the CDIs is as follows:
-
CDI-1: Abstracting multivector operations from concrete scalar representations. In practical computational applications, there are diversely useful representations for the mathematical concept of scalars, as classically introduced in abstract algebra. The most common representation for numerical applications is for real scalars using the IEEE 754 floating-point number format. For modern data-driven and machine learning applications, multi-dimensional arrays and tensors are the basic representations for scalar data. Another very useful representation for scalars, used in most Computer Algebra Systems (CAS), is an expression tree which represents a symbolic scalar expression for mathematical manipulation applications. The foundational requirement for GA-FuL design is to provide a unified generic implementation for storing and manipulating multivectors and performing common GA operations on any kind of useful scalar representation.
-
CDI-2: Reducing memory requirements for sparse multivectors. One major obstacle in the way of using GA for practical computations is the memory storage requirements imposed by the structure of multivectors. Storing a full multivector in a \(n\)-dimensional GA requires \(2^{n}\) scalars, while storing a full \(k\)-vector requires \(\binom{n}{k}\) scalars. For the simplest of numerical scalar representations, 32-bit floating point numbers, a single multivector in a 30-dimensional GA requires 8 GBytes of memory, while a full 15-vector one requires nearly 1.16 GBytes of memory; assuming the use of memory arrays to store the scalars. For most practical GA applications, however, there is rarely a need for storing full multivectors or full \(k\)-vectors, and only sparse multivectors are sufficient. One feature of GA is to enable the creation of linear models of nonlinear geometric objects by embedding the original space into a higher-dimension GA space. This typically results in multivectors representing geometric objects using a significantly reduced number of scalars, not a full-sized multivector or \(k\)-vector. For example, a sparse multivector in 5-dimensional conformal GA, containing only 5 out of 32 scalars, can represent points, planes, and spheres of 3-dimensional Euclidean space. As such, another important requirement for the GA-FuL design is to provide a set of generic, memory-efficient data structures for storing the scalars of sparse multivectors in high-dimensional GAs.
-
CDI-3: Providing metaprogramming capabilities. Generative programming in general and metaprogramming in particular incorporate the process of creating software systems that treat programs as data, enabling the transformation of existing programs or for the generation of new ones. This was the target of the predecessor system GMac for generating optimized computational numerical code from a series of GA expressions. This design goal is carried on to GA-FuL, which would enable code generation targeting high-performance platforms such as CUDA, in addition to classical general purpose programming languages such as C\C++, C#, Java, JavaScript, Python, MATLAB scripts, etc.
-
CDI-4: Introducing a layered system design for a wide spectrum of uses. The complexity imposed by the previous CDIs must be organized and managed through a layered design of the system. Each layer should specialize in one aspect of the system such as storage management, processing, algebraic and geometric abstractions, etc. In addition, a system of such capabilities would have a wide range of users and use cases. Typically, a user would use the system to create a numerical\symbolic prototype for some geometric modeling ideas, and then after some experimentation, would use metaprogramming system capabilities to generate optimized code for the final model targeting a specific programming language or environment. The design of GA-FuL attempts to realize this layered approach to allow users of different backgrounds to select the suitable level of coding they can handle. The coding level ranges from the very high level of coordinate-independent prototyping using abstract GA operations up to a fully controlled low-level direct manipulation of scalars and coordinates for high-performance computing purposes.
-
CDI-5: Providing a unified, generic, and extensible API for several classes of applications. The final design goal of GA-FuL is to expose the system functionality through a good Application Programming Interface (API). The API should have a unified public interface with uniform conventions to aid usability. Additionally, the API should be generic regarding the kinds of scalars and GAs it can handle, reflecting the capabilities of the underlying system. API extensibility is also important for future development of the system to aid in the addition of more features and widening system usage. Finally, the API should support the development of various classes of applications including, but not limited to, numerical prototyping computations, symbolic mathematical manipulations, signal processing, visualization, and metaprogramming.
During the initial design of GA-FuL, satisfying the set of CDIs using traditional Object-Oriented Programming (OOP) was found to be non-practical. This is mainly due to the tendency of classical OOP practices to increase the code-base complexity of large systems such as GA-FuL. In this context, complexity specifically means the deep coupling of data and behavior code typically imposed by classical OOP principles, especially encapsulation and inheritance. This typically results in complicated relations between system classes and complex inheritance hierarchies, leading to difficulties in understanding the design of large systems. If not properly mitigated, this can eventually result in reduced code understanding and difficulty in system maintenance and extensibility.
The solution found to be most useful was to use a newly emerging software design paradigm that while being compatible with OOP, also tends to produce a more readable, maintainable, and extensible code-base. The use of Data-Oriented Programming (DOP) principles, as the highest-level design paradigm, proved to be highly beneficial to many aspects of GA-FuL system design. The four core principles of DOP are follow:
-
DOP-1: Separating behavior code from data. This is a design tenet that advocates for a distinct division between behavior code and data. Following this DOP principle in OOP entails grouping the behavior code into methods for a static class. In GA-FuL, DOP-1 is implemented using thin wrapper classes around generic data structures holding the actual data. Extension methods in static utility classes operate on the thin-wrapper classes to perform the desired behaviors.
-
DOP-2: Representing data with generic data structures. DOP is not dogmatic about the programming constructs used to employ and organize the code. Arrays\lists and dictionaries\maps are the two most widely used generic data structures in prac- tice. However, one can also utilize other general data structures, such queues, trees, and sets. As for DOP-2 in GA-FuL, sparse algebraic objects, such as \(k\)-vectors and multivectors, are stored in dictionaries, while dense algebraic objects, such as matrices and multidimensional scalar arrays, are stored in classical array data structures.
-
DOP-3: Making data immutable. In DOP, due to isolation of representational data structures from behavior code, data mutation is not permitted. Instead, data modifica- tions are carried out by generating new data structure versions. A variable’s reference can be updated to point to a different version of the data, but the actual value of the data must never change. In GA-FuL, DOP-3 is accomplished through specialized classes called composers. A composer for a multivector, for example, performs a data transformation\construction transaction that, when completed properly, generates a valid dictionary containing valid data values that a multivector code wrapper class and extension methods can query and manipulate later.
-
DOP-4: Separating data representation from data schema. Now that data and code are decoupled and generic immutable data structures are employed to describe it, the challenge is to articulate the shape of the data. The intended shape in DOP is represented by a data schema that is stored apart from the actual data. The primary advantage of DOP-4 is that it gives developers the freedom to choose which data elements should have a schema and which ones should not. The DOP-4 principle is accomplished in GA-FuL through the use of generic interfaces and abstract base classes, where the wrapper classes and extension methods manipulate data with a given generic interface or abstract class regardless of the actual data structure implementing the interface\class at any moment during program execution.
As a specific example of how the DOP principles in GA-FuL are implemented, the interface IIndexSet is used as a data schema to represent all kinds of index sets for basis blades (according to DOP-4). For representing a GA basis blade \(e_{i_1,i_2,\ldots,i_k}\) , concrete class implementations of this interface internally use a sorted set of non-negative integers \(i_1,i_2,\ldots,i_k\) , completely independent of any specific GA metric. There are specialized immutable classes implementing the IIndexSet interface for the empty index set; a single-element index set, a more efficient index set with largest index less than 64 (internally using a 64-bit unsigned integer); a dense index set of arbitrary size (using an array of integers); and a sparse index set of arbitrary size (internally using a hash-set object for storing the indices) (according to DOP-2, DOP-3). The class XGaBasisBlade is a thin wrapper around an IIndexSet object with member and extension methods for performing basic operations on basis blades such as the geometric and other bilinear products, the reverse operation, etc (in accordance with DOP-1).
Another example is the generic interface IReadOnlyDictionary<IIndexSet, T> that is the main data schema (DOP-4) for storing a sparse list of (basis blade, scalar value) pairs for all kinds of multivectors in GA-FuL. There is a specialized immutable class (DOP-2, DOP-3) implementing this interface for zero multivectors, another for storing a single (basis blade, scalar value) pair, and one for an arbitrary sparse list of (basis blade, scalar value) pairs. The internal data of a new multivector can be constructed using the XGaMultivectorComposer<T> composer class (DOP-3) acting as a construction transaction management class (DOP-1). The composer class automatically selects the most efficient concrete data structure class implementing the IReadOnlyDictionary<IIndexSet, T> interface to be used as internal storage for the constructed multivector.
At the lowest level, the algebra layer is designed specifically to fulfill CDI-1 and CDI-2, in addition to the four DOP principles. Other layers in GA-FuL eventually utilize the functionalities provided by this layer. Components in the algebra layer mainly perform two functions:
Real scalar representations are considered external to this layer. A scalar can be represented using any desired class or structure, including numeric and symbolic representations provided by external packages. The generic IScalarProcessor<T> interface represents a processor to perform basic operations on scalars of arbitrary type T. This is one form of DOP-3 adherence in GA-FuL design where a scalar processor transforms scalar data to fulfill desired operations. Such operations include, among others, basic arithmetic (negation, addition, subtraction, multiplication, division, and power), transcendental functions (trigonometric, exponential, logarithms, etc.), and zero equality testing.
The derived interface INumericScalarProcessor<T> is useful for implementing concrete scalar processors on numerical types. In the current implementation, there are scalar processors for standard single\double precision floating-point real and complex numbers, arbitrary precision decimal\floating-point scalars, and arbitrary-precision rational numbers. In addition, there is a class implementing these operations on NumPy-like multi-dimensional arrays, and another for sampled signals for computational data-driven and signal processing applications.
A second derived interface, ISymbolicScalarProcessor<T>, is useful for handling symbolic scalars typically used in a CAS. This includes a class capable of processing Wolfram Mathematica symbolic scalars represented by the provided Expr class. New implementations can be added at later time to augment GA-FuL with the ability to interact with other symbolic processing systems such as Maple, the MATLAB symbolic toolbox, Python’s SymPy package, etc.
There is also a generic thin-wrapper class Scalar<T> composed over a scalar processor of type IScalarProcessor<T> and a scalar value of type T . This class is meant to make the GA-FuL API easier to use. Using this class, instead of the complicated scalar processor call w = scalarProcessor.Add(x, scalarProcessor.Times(y,z)), the user can simply write w = x + y * z. A similar DOP-adhering design is used for storing and manipulating most mathematical object representations in GA-FuL, including multivectors, the core GA mathematical object.
For representing GA multivector basis blades \(e_{i_1,i_2,\ldots,i_k}\) , this layer internally uses a sorted index set \(i_1,i_2,\ldots,i_k\) , completely independent of any specific GA metric. As illustrated in the previous section, the interface IIndexSet is used to represent such index sets.
Basic operations on individual and pairs of basis blades, such as the reverse operation or geometric products, for example, are performed at the lowest level through specialized integer manipulation subroutines. In the current implementation, blades with arbitrary dimensions can be represented using dynamic list-based index sets, while basis blades with dimensions less than 64 can be represented using fixed-length 64-bit integers, where a 1 indicates the presence of a basis vector in the index set of the basis blade, and a 0 indicates its absence. Additionally, GAs with 12 dimensions or less use various lookup tables to accelerate operations on lower-dimensional basis, blades. This structure enables more efficient processing of low-dimensional basis blades while allowing for the handling of arbitrary high-dimensional ones if the application requires.
On the processing side, the class XGaMetric is used for basic processing of basis blades with a specified metric signature such as directional, projective, conformal, etc. The signature is specified using two numbers \(q\), \(r\), the number of basis vectors that square to 1, 0 respectively. All remaining vectors in a basis blade are assumed to square to 1. In this way, no fixed dimension is predefined for any particular metric computation on basis blades. As in the case of scalars, the thin-wrapper class XGaSignedBasisBlade is composed over a IIndexSet member, a XGaMetric member, and an integer sign member that can only take values 1, 0, 1. In this way, operations on basis blades can be easily performed using simple member and static extension methods on the XGaSignedBasisBlade class, instead of more complicated calls to methods of an XGaMetric object.
The data of a \(k\)-vector are stored in an immutable dictionary of (index set, generic scalar) key-value pairs of type IReadOnlyDictionary<IIndexSet, T>; with keys of type IIndexSet and scalar of generic type T. The number of indices per index set for all keys in the dictionary is constant and equal to \(k\), the grade of the \(k\)-vector. The data of a multivector are stored in an immutable dictionary containing (grade k, k-vector) key-value pairs of type IReadOnlyDictionary<int, XGaKVector<T>>; where a key holds a unique grade \(k\), and the value is a \(k\)-vector part of the multivector. In this way, all linear and bilinear operations on multivectors are reduced to operations on \(k\)-vectors, which greatly simplifies the implementation. Additionally, this design enables a highly sparse and flexible representation of multivectors of all kinds in GA-FuL.
The generic XGaProcessor<T> class, derived from XGaMetric, is the root for all multivector processors in this layer. Most operations on multivectors are implemented using static extension methods taking a XGaProcessor<T> object as the main argument. The current version of GA-FuL allows for the representation and manipulation of GA spaces with any number of dimensions. All GA metrics are also possible based on this previous work. In addition, there are specialized processor classes for directional, conformal, and projective GAs. Additionally, a small hierarchy of thin-wrapper classes is implemented to simplify the GA-FuL API, as in the case for scalars and basis blades. This scheme allows for the memory-efficient storage of both dense low-dimensional and sparse high-dimensional multivectors.
One downside of this generic scheme is the computational performance for some applications. For this reason, there is a similar class hierarchy, rooted in the RGaFloat64Multivector class, optimized specifically for sparse multivectors of standard floating point scalars and GA spaces with fewer than 64 dimensions. For even higher-performance applications, the use of code generation is possible using the metaprogramming layer in GA-FuL described below. This flexible design gives the user a wide set of implementation options for various application domains within a single software framework. Up to the best of the authors' knowledge, no other single GA library provides a similar set of balanced choices simultaneously.
Additional classes for commonly useful GA transformations are also implemented. These include classes for general outermorphisms, general orthogonal operators (using versors in GA), general rotations (using GA rotors), and reflections\projections (using GA subspaces as reflection\projection operators).
In addition to real scalar algebra and geometric algebra, there are other kinds of algebraic representations implemented in the GA-FuL algebra layer. These include generic algebraic representations for complex numbers, quaternions, polynomials, linear algebra objects (planar angles, classical 2D\3D\4D\nD vectors, matrices, and general linear maps), and sampled signals for signal processing applications.
The modeling layer mainly targets the fulfillment of CDI-5. in this layer, there are mostly thin wrappers around classes from the algebra layer, with specific member and extension methods suitable for the intended functionality of each class. The calculus sub-layer, still in the design stage, is intended to perform geometric calculus operations on multivectors as described in the GA literature.
The visualization sub-layer is intended to visualize geometric objects using suitable 2D\3D computer graphics methods. Currently, it is possible to generate JavaScript code for the 3D visualization and animation engine Babylon.js based on static and animated geometric objects from the geometry layer. Additionally, more sophisticated videos can be generated by combining individual image frames using the Selenium browser automation project Chrome WebDrive for .NET. Some illustrative examples are included online under the GA-FuL code repository.
The geometry sub-layer contains the highest level of specialized classes for particular geometries utilizing GA, such as directional, projective, and conformal GAs. For example, the conformal GA for describing 3D geometric objects can be used, as in the following code:
// The pre-defined scalar processor for 64-bits floating point numbers
var scalarProcessor = ScalarProcessorOfFloat64.Instance;
// Create the CGA space object based on the selected kind of scalars
var cga = CGaGeometricSpace5D<double>.Create(scalarProcessor);
// Encode 4 points as CGA null vectors
var a = cga.EncodeIpnsRound.Point(3.5, 4.3, 2.6);
var b = cga.EncodeIpnsRound.Point(-2.1, 3.4, 5);
var c = cga.EncodeIpnsRound.Point(7.4, -1.5, -4.5);
var d = cga.EncodeIpnsRound.Point(3, -2, 5);
// Use the outer product to define the OPNS blade encoding a sphere passing through points a,b,c
var sphere = a.Op(b).Op(c).Op(d);
// Encode a line passing through a point parallel to a direction vector
var line = cga.EncodeOpnsFlat.Line(
scalarProcessor.Vector3D(3.5, 4.3, 2.6),
scalarProcessor.Vector3D(1, 1, 1)
);
// Project line on sphere to get a circle
var circle = line.ProjectOpnsOn(sphere);
// Decode the circle to separate its individual Euclidean geometric components
var circleComponents = circle.Decode.OpnsRound.Element();
// Center of circle:
var center = circleComponents.CenterToVector3D();
// Radius of circle:
var radius = circleComponents.RealRadius;
// Direction bivector of circle
var bivector = circleComponents.DirectionToBivector3D();
// Normal direction to circle
var normal = circleComponents.NormalDirectionToVector3D();
Console.WriteLine($"Center : {center}");
Console.WriteLine($"Radius : {radius}");
Console.WriteLine($"Bivector: {bivector}");
Console.WriteLine($"Normal : {normal}");
Console.WriteLine();As illustrated in the code, after defining a 5D-CGA space using an instance of the class XGaConformalSpace5D<T>, the user can perform the following tasks:
-
Encode a geometric object as a CGA blade\multivector. For example, the 5D CGA blades can represent the direction vectors, bivectors, points, point pairs, circles, spheres, lines, and planes of 3D Euclidean space. Additionally, CGA versors can encode all Euclidean and conformal maps such as rotations, translations, inversions, and reflections.
-
Perform basic GA multivector algebraic operations on the encoded multivectors in the CGA space.
-
Use simple member and extension methods to perform high-level geometric op- erations on the encoded multivectors. Examples include reflections, intersections, projections, translations, and rotations.
-
Decode a CGA blade\multivector into a set of simpler components. For example, a 5D CGA blade representing a circle can be decoded into the circle’s center, radius, direction bivector, and normal vector.
In the current implementation of GA-FuL, the base class XGaConformalSpace<T> and its two derived classes XGaConformalSpace4D<T> , XGaConformalSpace5D<T> are capable of handling not only CGA of any dimension but also PGA through the implementation of the powerful exposition in this paper. The main advantage of handling CGA and PGA within the same algebraic space is the ability to freely mix geometric object representations and their interactions within a single API.
The metaprogramming layer mainly targets CDI-3 and is the highest-level layer in GA-FuL. The main purpose of this layer is to generate optimized code in a selected Target Programming Language (TPL), given a sequence of operations on multivectors and other algebraic objects in GA-FuL. In essence, the components of this layer construct an optimizing compiler and code generator that takes an expression tree having scalar parameters and constant numbers as leafs and standard operations on scalars as internal nodes. The expression tree is automatically constructed using GA-FuL algebraic and geometric modeling components and is then optimized and transformed into TPL code through the optimizing compiler and code generator components.
This layer is useful for software engineers wanting to create specialized code, all or part of which is automatically generated from operations on algebraic objects, especially GA multivectors. The typical sequence for using the components of this layer consists of the following stages:
-
Initialize a Metaprogramming Context Object (MCO) by instancing the
MetaContextclass defined in the meta-context sub-layer. -
Use the MCO to define algebraic objects acting as input parameters to the computational block.
-
Use algebraic operations, provided by GA-FuL algebra and modeling layers, to describe the intended algebraic steps.
-
Select the expected output variables of the computational block from the algebraic objects computed.
-
Set the TPL names of the input, intermediate, and output scalar variables to be used in the final generated code.
-
Use the MCO to optimize the computational block.
-
Initialize the intended Code Composer Object (CCO) by instancing one of the classes defined in the code composers sub-layer.
-
Generate the final TPL optimized computational code using the CCO.
In the meta-context sub-layer, a special kind of scalar, called a *meta-expression scalar*, is used. Essentially, a meta-expression scalar, Figure 4, is an expression tree similar to the ones typically used in computer algebra systems but with additional functionality for metaprogramming tasks. A computational block is constructed step by step by the user’s code while being stored and optimized automatically inside the metaprogramming context object.
Conceptually, a computational block consists of a sequence of assignment statements to TPL variables defining the required computations at the lowest level of scalar components of the algebraic objects. The conversion from the high-level GA\algebraic operations used in step 3 into low-level scalar operations is performed automatically by the components of the meta context sub-layer and managed by the MCO itself. Some of the variables in the computational block can be assumed by the user as independent, externally defined input parameters, with no attached left-hand-side meta-expressions. Other scalar variables are mostly intermediate ones, except for a few that are selected by the user as output variables of the computational block. The MCO manages the entire computational code construction and optimization process. The MCO contains factory objects to add constant numbers and input parameters to the computational block. The MCO can perform the following optimizations on the computational code before the final code-generation step:
-
Propagation of constant values in metaexpressions on the right-hand side.
-
Extraction of common subexpressions in right-hand-side metaexpressions into intermediate variables for reuse.
-
Optional simplification of metaexpressions on the right hand side using an external computer algebra system\library.
-
Pruning of intermediate variables having constant values or repeated right-hand-side metaexpressions or those not being used for computing an output variable.
-
Optional reduction of the number of intermediate variables required.
-
Optional reduction of computational steps in the code through a genetic programming algorithm with a (4 + 1) evolutionary strategy.
The purpose of the CCO is to convert the computational block assignment statements stored in the MCO into TPL code. The low-level metaexpressions of the computational block can only contain standard operations on scalars, such as negation, addition, subtraction, multiplication, division, power, trigonometric functions, exponential, and logarithms. Thus, the code composers sub-layer can be extended to provide code generation capabilities for almost any target programming language that supports such operations. The code composers sub-layer contains abstract classes for additional advanced code generation tasks. The user can utilize classes of this sub-layer capable of template-based code generation for creating a wide range of general TPL code organizations, with or without using GA computations. These range from small text code with a single code file\module, to a large code library with complicated folder and code file structure.
The utilities layer provides low-level services to the components in the other GA-FuL layers. The basic data structure sub-layer contains a set of data structures to aid in data storage and exchange in the system. For example, several classes that implement the generic IReadOnlyDictionary<TKey, TValue> interface are part of this sub-layer. The text\ \(\LaTeX\) utilities sub-layer provides core services for formatted text generation and \(\LaTeX\) code composition extensively used by the system. The text-generation capabilities of this sub-layer are extensive. There are classes for composing formatted text, and parametric text templates and composers capable of creating full hierarchies of folders containing text files. The code generation utilities sub-layer performs various low-level code generation tasks used by the metaprogramming layer and other GA-FuL components. This includes components to represent and construct language-agnostic Abstract Syntax Trees (ASTs) and code generators that can compose code based on the ASTs. Finally, the web graphics utilities sub-layer is used by the visualization sub-layer for generating suitable web-based code for rendering desired graphics from algebraic specifications in GA-FuL.