Applications of Geometric Algebra in Computer Science and Engineering

Geometric algebra provides the essential foundation for a new approach to symmetry groups. Each of the 32 lattice point groups and 230 space groups in three dimensions is generated from a set of three symmetry vectors. This greatly facilitates representation, analysis and application of the groups to molecular modeling and crystallography.

Making derived products out of the geometric product requires care in consistency. We show how a split based on outer product and scalar product necessitates a slightly different inner product than usual. We demonstrate the use and geometric significance of this contraction, and show how it simplifies treatment of meet and join. We also derive the sufficient condition for covariance of expressions involving outer and inner products.

This paper suggests that geometric algebra should be based on points instead of vectors and should be metric-free. Whitehead’s 1898 treatise on Grassmann ’s Ausdehnungslehre described just such a metricfree geometric algebra of points. However, Whitehead’s treatise spoiled the natural simplicity of the theory by a lopsided derivation based purely on points which gave rise to two different products (progressive and regressive). The current paper tidies up the theory by invoking the principle of duality to put points and hyperplanes on an equal footing and then shows that the theory has just a single antisymmetric product which evaluates to give the same results as Whitehead’s progressive and regressive products.

Projection operators are used to represent unoriented subspaces, thus providing a framework to potentially solve problems (such as the general meet and join) that do not have oriented solutions. The potential is made reality by using an additional derived product called the Delta product (which is the highest grade part of the geometric product of two blades) for Euclidean metrics. The results are even more applicable because a general translation technique (a LIFT to a different metric) is presented that makes solutions of some problems translatable from one metric to another. In particular this makes the meet and join computable regardless of incidence properties and even in degenerate metrics.

A Clifford algebra has three major multiplications: inner product, outer product and geometric product. Accordingly, the same Clifford algebra has three versions: Clifford vector algebra, which features inner products and outer products of multivectors; Clifford bracket algebra, which features pseudoscalars and inner products of vectors; Clifford geometric algebra, which features geometric products of vectors and multivectors.

Rotations in physical space E3 are commonly represented by 3 x 3 real orthogonal unimodular (determinant = 1) matrices of the group SO(3). These matrices operate by left multiplication onto real three-dimensional column vectors; the space of such vectors is the carrier space of the representation. Rotations in different planes do not generally commute, and a common problem considered in texts is how to express the product of given rotations as a single rotation; see, e.g., Altmann [1] or Jones [2]. In quantum physics, rotations are more often expressed in the universal covering group of SO(3), namely Spin (3) ≃ SU(2). The carrier spaces of irreducible representations of Spin (3) comprise complex two-component spinors. The spinors and their Hermitian conjugates carry two linearly independent irreducible representations, and the vectors of physical space can be expressed as linear combinations of their products.

We describe some of the applications of Finite Geometry to Clifford Algebras, and then look in more detail at some of the relations between geometrical and algebraic canonical forms. Much of this latter work has been investigated using computer algebra systems, and we include some details of this, along with some of the issues that arise.

It is a simple matter to compute the function of a Clifford number or any square matrix if the function is a polynomial. However difficulties arise for more complicated functions. In the course of dealing with square roots of Clifford numbers, Garret Sobczyk became acquainted with some of the literature [3] and [4] on the generalized spectral decompositions of a linear operator. This decomposition removes these difficulties. Since this approach is not well known, Sobczyk has published a sequence of elegant expository articles [5], [6], and [7] to popularize the application of this method. He has also introduced an improved algorithm in the appendix of [5] to deal with the case for which there are multiple roots in the minimal polynomical for the linear operator. In this paper we will carry this slightly further to obtain an explicit formula for the projection operators.

We consider the Clifford algebra Cl _n (F) where the field F is the real R or the complex numbers C. It is well known that an m-form x₁/\⋯/\ x _m can be represented by the mth compound matrix of the n-by-m matrix X := [x₁, ⋯, x _m ] ∈ Fn×m relative to the basis {θ₁, θ₂, ⋯, θ_2n } 2254; 1, e₁, ⋯, e₁Λ⋯Λe _n } of the underlying Grassmann algebra G _n (F). Since the Clifford product ● is related to the Grassmann product A via x ● y = x Λ y + xTy, x, y ∈ Fn, the question of a corresponding representation of the Clifford product x₁ ·⋯· x_m arises in a natural way. We will show that the Clifford product of an odd (even) number of vectors corresponds to a linear combination of forms of odd (even) grade where the coefficients of these linear combinations are Pfaffians of certain matrices which can be understood as the skew symmetric counterpart of the corresponding Gramians. Based on this representation we calculate the mth Clifford power $$ \underline x ^m :{\rm{ = }}\overbrace {x \bullet \cdots \bullet x}^m $$ of a vector x ∈ F _n which enables the extension of an analytical function f : F → F to their corresponding Clifford function f:Fn → Cl_n(F).

In this paper we outline several ideas of how to define analysis starting from the algebra of abstract vector variables.

We propose a combinatorial data structure for representing multivectors [2, 3] in an n-dimensional space. The data structure is organized around a collection of abstract K-dimensional cells, k = 0,1,...,n that are assembled into an oriented cellular structure called a starplex and shown in Figure 11.1. The starplex structure represents the combinatorial neighborhood (a star) of a 0-cell in any n-dimensional cell complex representing a typical coordinate control element (usually cubical or simplicial). The combinatorics of the starplex matches exactly the combinatorial structure of the multivector: every oriented k-cell in the starplex corresponds to some basis K-vector.

Systems of partial differential equations lie at the heart of physics. Despite this, the general theory of these systems has remained rather obscure in comparison to numerical approaches such as finite element models and various other discretisation schemes. There are, however, several theoretical approaches to systems of PDEs, including schemes based on differential algebra and geometric approaches including the theory of exterior differential systems [5] and the so-called “formal theory” [4] built on the jet bundle formalism. This paper is a brief introduction to jet bundles, focusing on the completion of systems to equivalent involutive systems for which power series solutions may be constructed order by order. We will not consider the mathematical underpinnings of involution (which lie in the theory of combinatorial decompositions of polynomial modules [2,3]) nor other applications of the theory of jet bundles such as the theory of symmetries of systems of PDEs [6] or discretisation schemes based on discrete approximations to jet bundles [1].

This paper first reviews how anti-symmetric matrices in two dimensions yield imaginary eigenvalues and complex eigenvectors. It is shown how this carries on to rotations by means of the Cayley transformation. Then a real geometric interpretation is given to the eigenvalues and eigenvectors by means of real geometric algebra. The eigenvectors are seen to be two component eigenspinors which can be further reduced to underlying vector duplets. The eigenvalues are interpreted as rotation operators, which rotate the underlying vector duplets. The second part of this paper extends and generalizes the treatment to three dimensions. Finally the four-dimensional problem is stated.

A computer program has been written which enables the algebraic processing of Clifford Algebras within programs written in C++. The program is an extension of the program SymbolicC++ by Tan and Steeb and follows their methods of supporting a class through template classes. Classes have been written and tested including Clifford(2), Clifford (3) and Clifford(2,2). The classes can also be accessed from within an interpreted language, Tcl, via an interface program.

The theory of Clifford Algebra includes a statement that each Clifford Algebra is isomorphic to a matrix representation. Several authors discuss this and in particular Ablamowicz [1] gives examples of derivation of the matrix representation. A matrix will itself satisfy the characteristic polynomial equation obeyed by its own eigenvalues. This relationship can be used to calculate the inverse of a matrix from powers of the matrix itself. It is demonstrated that the matrix basis of a Clifford number can be used to calculate the inverse of a Clifford number using the characteristic equation of the matrix and powers of the Clifford number. Examples are given for the algebras Clifford(2), Clifford(3) and Clifford(2,2).

Scheuermann et al used Geometric Algebra to demonstrate a new relationship between the topology of a 2D vector field and its analytic description. We have used the insights provided by this work to create a computer program that allows a user to design, modify and visualize a 2D vector field in real time. The vector field is polynomial over the complex field C, and is therefore more computationally efficient and stable than Polya’s rational version over C, which is the traditional approach for such work. Such “toy” vector fields are useful for instruction, understanding and topological simulation of many issues associated with all vector fields.

Two-dimensional quadratic transformations are considered in the terms of cross ratio. Using the language of geometric algebra the projective plane is reduced to the image plane. Thus, a quadratic transformation in the image plane is constructed.

It is well known that every Frobenius algebra is quasi-Frobenius, that is to say, if a finite dimensional algebra A over a field F has a nondegenerate bilinear form B such that B(xy, z) = B(x, yz) for all x, y, z ∊ A, then the maps L → Ann _r (L) and R → Ann _l (R) give inclusion preserving bijections between lattices of left and right ideals of A satisfying (a) Ann _r (L₁ + L₂) = Ann _r (L₁) ⋂ Ann _r (L₂), Ann _r (L₁ ⋂ L₂) = Ann _r (L₁) + Ann _r (L₂) (b) Ann _l (R₁ + R₂) = Ann _l (R₁) ⋂ Ann _l (R₂), Ann _l (R₁ ⋂ R₂) = Ann _l (R₁) + Ann _l (R₂) (c) Ann_l(Ann _r (L)) = LandAnn _r (Ann _l (R)) = R. (For example see [2].)

Geometric algebra is used in an essential way to provide a coordinate-free approach to Euclidean geometry and rigid body mechanics that fully integrates rotational and translational dynamics. Euclidean points are given a homogeneous representation that avoids designating one of them as an origin of coordinates and enables direct computation of geometric relations. Finite displacements of rigid bodies are associated naturally with screw displacements generated by bivectors and represented by twistors that combine multiplicatively. Classical screw theory is incorporated in an invariant formulation that is less ambiguous, easier to interpret geometrically, and manifestly more efficient in symbolic computation. The potential energy of an arbitrary elastic coupling is given an invariant form that promises significant simplifications in practical applications.

When two or more subsystems of a quantum system interact with each other they can become entangled. In this case the individual subsystems can no longer be described as pure quantum states. For systems with only two subsystems this entanglement can be described using the Schmidt decomposition. This selects a preferred orthonormal basis for expressing the wavefunction and gives a measure of the degree of entanglement present in the system. The extension of this to the more general case of n subsystems is not yet known. We present a review of this process using the standard representation and apply this method in the geometric algebra setting, which has the advantage of suggesting a generalisation to n subsystems.

The multiparticle spacetime algebra (MSTA) is an extension of Dirac theory to a multiparticle setting, which was first studied by Doran, Gull and Lasenby. The geometric interpretation of this algebra, which it inherits from its one-particle factors, possesses a number of physically compelling features, including simple derivations of the Pauli exclusion principle and other nonlocal effects in quantum physics. Of particular importance here is the fact that all the operations needed in the quantum (statistical) mechanics of spin 1/2 particles can be carried out in the “even subalgebra” of the MSTA. This enables us to “lift” existing results in quantum information theory regarding entanglement, decoherence and the quantum / classical transition to spacetime. The full power of the MSTA and its geometric interpretation can then be used to obtain new insights into these foundational issues in quantum theory. A system of spin 1/2 particles located at fixed positions in space, and interacting with an external magnetic field and/or with one another via their intrinsic magnetic dipoles provides a simple paradigm for the study of these issues. This paradigm can further be easily realized and studied in the laboratory by nuclear magnetic resonance spectroscopy.

The designer of a stealthy military vehicle aims to make its metal surface retro-reflect the minimum possible radar energy. Well known retro-reflecting (RR) concave structures such as mutually orthogonal plates, involving two and three successive reflections (edge and corner reflectors) respectively, are avoided . They are examples of persistent features because their retro-reflection occurs over a wide range of directions.Geometrical Algebra (GA) is used to derive expressions for the two and three reflections of an entry ray vector x. The exit ray vectors are shown to be Rx~R and -Px~P respectively where R and P are rotors. Interpreting the expressions leads to quite fundamental laws of reflection from two and three flat reflectors from which new RR, structures are predicted. The GA expression for two and three successive reflections is easily generalized to (—l)mQxO, where Q is also a rotor, and m is an arbitrary number of reflections. All reflectors are assumed to be one-sided, i.e., the continuous reflecting surface encloses a volume inaccessible to radiation. In practice an exit ray is deemed retro-reflective if the “spread” angle, between the entry ray reversed (ERR) and the exit ray, is less than a small spread tolerance Ι _tol . The corresponding “entry” angle ɛ(Ι _tol ), the angle between the retro-reflective direction and the ERR, is suggested as a measure of the persistence of the multiple reflection. For example ɛ(Ι _tol ) is X _toz /2 for single plate reflection (least persistent) and π/2 (most persistent) for a corner reflector. Expressions for intermediate values for persistence are derived for the two and three reflecting configurations in general.

The elements of the reciprocal metric tensor, which appears in the exact (nonrelativistic) internal kinetic energy operators of polyatomic molecules, can, in principle, be written as the mass-weighted sum of the inner products of measuring vectors associated to the nuclei of the molecule. In the case of vibrational degrees of freedom, the measuring vectors are simply the gradients of the vibrational coordinates with respect to the position of the nucleus in question. They can be calculated either by the direct vectorial differentiation, or from the variation of the appropriate coordinate along the path of the particle. It is more difficult to find these vectors for the rotational degrees of freedom, because the components of the total angular momentum operator are not conjugated to any rotational coordinates. However, by the methods of geometric algebra, the rotational measuring vectors are easily calculated for any geometrically defined body-frame, without any restrictions to the number of particles in the system. The kinetic energy operators produced by the present approach are in perfect agreement with the previously published results. The methods of geometric algebra have been recently applied (with good success) to the description of the large amplitude inversion vibration of ammonia.

Under mild conditions the experimentally accessible Hamiltonians in ensembles of N coupled, nondegenerate spins-½ are shown to generate the entire Lie group SU(2 _N ). This is the case e.g., in nuclear magnetic resonance (NMR) spectroscopy [1], where quantum computing gates [2] are implemented by unitary propagators, viz the ‘rf-pulse sequences’.The maximum achievable coherence transfer amplitude under unitary Hamiltonian dynamics of ensembles translates into a minimum Euclidean distance: the minimal distance between the unitary orbit of some given initial state represented by a density operator (or its signal-relevant components collected in a matrix A) and a given final state or observable (or its components C_†). This distance relates to the C-numerical range of A, WC(A) := {tr(UAU-1C)|U ∈ SU(2N)}, and its largest absolute value, the C-numerical radius of A, $$ r_C \left( A \right) : = \mathop {{\rm{max}}}\limits_U |tr\left\{ {U AU^{ - 1} C} \right\}|\left[ {\rm{3}} \right] $$ [3]. The geometry of the C-numerical range includes as limiting cases the notions of ensembles comprising entangled as well as classically mixed components. In the latter, entropy and relative entropy relate to Euclidean distances.Given two arbitrary matrices A,C ∈ Mat _n (C), the first gradient-flow-based computer algorithm [4-6] for minimising the Euclidean distance between the unitary orbit of A and C_† (or rather C) in the general case is presented.

The main goal of the paper is to show that quantum Clifford algebras can be used to solve pattern recognition in multispectral environment in a natural and effective manner.

Hestenes spacetime algebra is used as a formalism for Light Polarization. A plane-like wave solution to the Maxwell equation in free space is studied. Its energy-momentum density is structurally related to the Poincaré sphere equation, Stoke’s parameters, and coherency matrices; while its energy momentum is that of light-like particles. The wave is leftcircularly polarized while its spatial inverse is right-circularly polarized. It is conjectured that other polarization states may be obtained by superposing left- and right-ircularly polarized states through Fourier Analysis.

This presentation focuses on the close link of Clifford algebras with quaternions which seems to have been neglected in recent developments [1-3]. A multivector calculus is presented within a Clifford algebra isomorphic to a tensor product of two quaternion algebras and thus differing from the corresponding complexified algebra used in the spacetime algebra approach. Major symmetry groups of physics: the Lorentz group, the conformal group, SU(4) and the symplectic group are expressed within this Clifford algebra (taken over ℝ or C). Physical applications such as the special theory of relativity, classical electromagnetism, Einstein’s field equations and Dirac’s equation are discussed.

In image processing it is common practice to find Euclidean differential invariants of the “image surface” in “image space” (that is the picture plane times intensity space). Many well-known algorithms are based on this usage. Yet this makes no sense since these invariants are with respect to Euclidean isometries, e.g., rotations. But clearly you can’t rotate the image surface to see its other side, or the intensity to a spatial direction. Thus the angle measure cannot be periodic in planes other than the picture plane. One needs to set up the proper transformation group to arrive at a set of invariants that makes sense. This yields a novel, generic geometrical framework for image processing. Most of the well-known global image transformations are movements, similarities or conformal transformations in this geometry. The differential geometry yields novel definitions for many features such as ruts and ridges.

It appears that the human visual system does not project the RGB image into separate processing channels. In this sense, our approach uses the compact representation of rotors (quaternions) to process color images. In the experimental part, we compare the rotor color edge detector with standard edge detectors, this shows that our detector behaves as an holistic filter which discriminates edges produced by shadows. We believe that our approach may encourage the design of powerful algorithms for compact color image processing.

This paper has two main parts. In the first part we discuss multivector null spaces with respect to the geometric product. In the second part we apply this analysis to the numerical evaluation of versors in conformal space. The main result of this paper is an algorithm that attempts to evaluate the best transformation between two sets of 3D-points. This transformation may be pure translation or rotation, or any combination of them. This is, of course, also possible using matrix methods. However, constraining the resultant transformation matrix to a particular transformation is not always easy. Using Clifford algebra it is straightforward to stay within the space of the transformation we are looking for.

Second-order dynamic systems described by the equation $$ Kx + C\dot x + M\ddot x = F $$ (where the dots indicate differentiation with respect to time) are of immense importance in engineering. The system matrices, K, C, M, are real (N × N) matrices and the vectors of displacement and force x, F each contain N functions of time. For many of the analyses performed on these systems, a generalised eigenvalue problem involving two (2N × 2N) matrices is set up and solved. It is common that most or all of the resulting eigenvalue-eigenvector pairs are complex. The numerical methods currently used for solving this generalised eigenvalue problem (GEP) do not take full advantage of its very particular structure. In particular, they do not provide any way to capitalise on the symmetry very often present in K, C, M [1]. Moreover, the structure in this problem results in constraints on the eigensolutions which make it possible to store those solutions more compactly but these constraints are generally ignored. There is compelling evidence that a more natural approach is possible. The role of Clifford Algebra in this more natural approach is examined.

This paper presents the algebra of incidence using the framework of the n-dimensional afflne plane. In contrast to former approaches we show that in this framework we can carry out computations involving 3D rigid motions and incidence algebra operations. Interesting applications of kinematics computations, reaching and configuration checking are presented.

In this paper conformal geometric algebra is used to formalize an algebraic embedding for the problem of monocular pose estimation of kinematic chains. The problem is modeled on a base of several geometric constraint equations. In conformal geometric algebra the resulting equations are compact and clear. To solve the equations we linearize and iterate the equations to approximate the pose and the kinematic chain parameters.

The advance of automation in car manufacturing industries imposes new demands on the field of robotics. An example of a challenging problem is sealing of car bodies or other fabrications by industrial robots. For pose estimation of rigid bodies required in this context, modern robotics makes more and more use of methods of digital image processing. A major advantages of image processing is that complex positioning systems become superfluous, and that tasks demanding high precision, as is the case for sealing, now become treatable by robots.

Given the three-dimensional positions of points on an articulated body in general motion, we often need to estimate the dynamical quantities of the body. It would be useful to have a general methodology to achieve this under different constraints of the models. Starting from the actual marker positions, we would like simple algorithms to calculate both kinematic and dynamic quantities. Such quantities are rotations, angular velocities, accelerations and rate of change of angular momentum. In this paper we formulate a simple recipe to achieve this using Geometric Algebra.

A Jacobian matrix of a general inline planar platform is studied. An inline planar platform is a manipulator with three legs, each with RPR joints, such that the revolute joints are free and align on each platform and the prismatic joints are powered. The configurations that cause the Jacobian matrix to become singular form a singularity surface that must be avoided for controllability. The Jacobian matrix is developed in the even Clifford algebra Cl+(P2) of the projective space P2 and its singularity surface is studied. A redundant planar platform manipulator is shown to have a block Jacobian matrix. A composite of singularity sets is developed for a redundant planar platform. A three-dimensional multi-platform manipulator is discussed.

We study the Fourier harmonic analysis of functions on discrete Heisenberg-Weyl groups and develop fast quantum Fourier-Heisenberg-Weyl transforms on these groups.

The structure multivector is an operator for analysing the local structure of an image. It combines ideas from the structure tensor, steerable filters, and quadrature filters where the advantages of all three approaches are brought into a single method by means of geometric algebra. The proposed operator is efficient to implement and linear up to a final steering operation. In this paper we derive the structure multivector from the Laplace equation, which also introduces a new viewpoint on scale space. A phase approach for intrinsically 2D structures is derived and applications are presented which make use of the 2D part of the new operator.

In a mixture of chemical compounds, the significant variable is often the proportion of molecules, normally expressed as a mole fraction in a particular sample. The fractions are constrained to sum to one, so any change such as the addition of more of any chemical component causes all of the mole fractions to change in a nonlinear way. Lasenby et al [1] have applied Clifford Algebra to the problem of projection and shown that problems can be made linear and results obtained. In this paper a similar approach is used to show that some nonlinear problems, such as conversion between molar and mass basis, become linear when projected into a space of increased dimension. When this is done using the V product defined by Miralles et al. [2] this can be done using a Clifford algebra with all positive signature. Examples are given of the results of the formulation.

Global IFS seem to be suited best for compressed encoding of natural objects which are in most cases self-affine even if not always exactly. Since affine maps — the IFS-Codes — resp. the union of all their orbits, generate an object (an IFS-Attractor), the detection of a nonminimal set of these orbits solves the inverse IFS-Problem by calculating a superset of IFS-Codes which has to be minimized. Here an algorithm is presented to calculate these boundary orbits. On the basis of a generalized convex hull — the —Hull — the log spirals (curves formed by the orbits) circumscribing the object can be calculated. From object points on these log spirals the generating affine maps are derived. Then these affine maps are classified to calculate the IFS-Codes of a minimal IFS. Finally, orbits contained in parts inside the object are set in relation to the found orbits to solve the problem for the entire object.

Fast classical and quantum algorithms are introduced for a wide class of nonseparable nD discrete unitary K-transforms (DKT) $$ {\cal K}_{N^n } $$.