Paper 25: Symbolic processing of Clifford Numbers in C++.

Dr John P. Fletcher, Chemical Engineering and Applied Chemistry, School of Engineering and Applied Science, Aston University, Aston Triangle, Birmingham B4 7 ET, U. K. Email: J.P.Fletcher@aston.ac.uk

Abstract

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.

1 Introduction

It is possible to use the computer language C++ to program symbolic algebra.  Tan and Steeb[1] and Tan et al [2] have described such a system and made it available for use.  The main components are a set of headers which define a system for symbolic algebra together with definitions including complex algebra, quaternions, vectors and matrices.  There is a capability for differentiation and some integration in Shi Steeb and Hardy[2].  The components are in the form of template classes giving great flexibility in the type of objects which can be defined.  The authors provide examples.  In this work these codes have been extended to include different algebras using the quaternion definition as a basis.  The examples shown here are Clifford(2), Clifford(3) and Clifford(2,2).  

The most demanding programming task is the multiplication table, which increases in complexity greatly as the dimension of the algebra increases.  As these tools have been developed they have proved of great use in exploring the symmetry of each algebra and its relation to the matrix representation.  Each exploration required frequent compilation and then accumulation of the results, usually in a text file.

A further development has been to link the C++ classes to an interpreted environment, Tcl[3], so that the algebra can be explored by the user without needing access to the compiler. This requires interface program code which has been generated automatically from a definition file by the SWIG program[4].  The results from Tcl programs can be stored into a free structured database as a series of nodes and links.  The contents of the database can be exported in text form using XML and it is intended to use an extension of MathML to encode the results in a portable form.

2 SymbolicC++

2.1 Operator and type definitions

The SymbolicC++ classes are written in standard C++ and have proved portable to different computer systems and compilers. The work reported here has been done with Symantec (now Digital Mars) C++ and Microsoft VC++ 6.0 when used with Tcl.  The SymbolicC++ template classes use a feature called operator overloading which permits the use of the familiar algebraic operator symbols so that a mathematical expression

can be coded as in a C++ program, once the variables have been given a consistent definition.  The basic definition of SymbolicC++ is to define a variable as symbolic by giving it a template type called Sum.  For example, the expression above could be coded as

 Sum<double> a(''a'',0),b(''b'',0),x(''x'',0);
 x = a + b;

defines a, b, and x as symbolic variables with the text symbols ''a'', ''b'' and ''x'' attached to each.   The expression associates the result ''a+b'' with the variable x in such a way that all subsequent use of x will carry that value.  The double implies that the variables can also be used to hold floating point numerical values.  Any built in types in the language can be used in the definition, and also types defined by the user.  These can be combined so that

 Complex<Sum<double> > > c(a,b);

defines a variable c to be complex with symbolic components a and b, and

 Sum<Complex<Sum<double> > > z(''z'',0);

defines a variable z to be a symbolic complex variable named ''z'', whose two components can be symbolic floating point variables or numerical values.  This means that the object as a whole can be manipulated and at the same time the real and imaginary parts can be symbolic expressions.  These component expressions can be extracted through functions provided in the definition.

 x = z.realPart();
 y = z.imagPart();

There is a limitation that the class templates cannot incorporate any knowledge of the type to which it is being applied.  For example, the template for the Complex class cannot have different processing for symbolic and numerical variables as its components.  These differences have to be handled in the Sum class template.

2.2 Type conversion

There is another problem which has had to be overcome to enable the user to combine of different types in expressions.  For example, for two complex numbers, one symbolic and the other numerical the definitions could be as follows.

 Complex<Sum<double> > a(''a'',0);
 Complex<double> d(1,2);

The action to set the numerical value to the symbolic, which may be required,

 a = d;

will give an error, because the two types are not compatiable as defined in SymbolicC++.  This cannot be remedied within the templates except by coding in advance for all the types necessary, which results in a loss of flexibility.  The solution to this problem is to define a converter class for the main type Complex which permits conversion between two different declared types, provided the underlying types can be converted.

 template < class T, class Ttype, class U >
 class ComplexConverter {
     public :
     ComplexConverter() { }
 // Conversion function between two Complex types
 // This will work only if the underlying
 // type of U can be converted to Ttype.
 static T convert(const U &u )
   {
    Ttype real = u.realPart();
    Ttype imag = u.imagPart();
    T temp(real,imag);
    return temp;
   }
 };

This converter can then be used for the combination which it is desired to convert, by providing a type definition such as

 typedef ComplexConverter< Complex<Sum<double> >,
 Sum<double>, Complex<double> > convCSdCd;

which defines the necessary converter function so that the conversion can be done as

 a = convCSdCd::convert(d);

An equivalent converter is also needed in the Sum class, and as many different converters can be declared as are needed.

2.3 Output

The standard output of objects used in SymbolicC++ is the C++ output stream.  An output operator is defined in each template class, and the expression or number stored in each variable is output as a string of characters.  Any object defined using class Sum holds a representation in memory of the expression assigned to it, and the output operator for this class constructs all the relations among the different variables.  The string is not stored, but constructed when needed.

 Sum< double> x(''x'',0),y(''y'',0);
 Complex<Sum<double> > d(1,2);
 cout << ''z is '' << z << endl;

The output format of each type of object is determined within output operator in the template definition for that object class.  The format for the Complex type defined in SymbolicC++ gives the output

 z is (x,y i)

In this work, an alternative has been provided to define it in a symbolic way.  

 z is x+y*i

This choice can be made at compile time for a whole program and compiles an alternative definition of the output operator for class Complex.

2.4 Noncommutative Arithmetic

One feature provided in SymbolicC++ is particularly valuable.  It is possible to declare that for any class multiplication will be handled in a noncommutative way.  This is can be set separately for each class of objects, by calling the function Commutative for any object of the class.  For example

 double d;
 Commutative (d,0);

makes floating point arithmetic noncommutative.  This has been used for the consistent handling of Clifford objects as symbolic items.

2.5 Extending SymbolicC++

Several extensions to the SymbolicC++ provided by its authors [1][2] have already been described, including the converters of the previous section.  It can be also extended by including new definitions written as template classes.   The new templates must conform to certain assumptions made about them by the Sum template, for example that numerical results are going to be available when needed, or that comparisons such as ”greater than” and ”equality” are meaningful for all possible underlying types, and means must be found to satisfy these assumptions.  These issues have to be considered in designing templates for Clifford algebras.  In the course of the development of the new templates it has been necessary to make some changes to the Sum class to ensure the correct evaluation and output of the symbolic expressions.  It is beyond the scope of this paper to report on the details.

The combination of the original SymbolicC++ code [1] [2] with some extensions provides a framework within which Clifford algebras can be implemented.

3 Clifford Algebra Examples

3.1 Quaternion starting point

The Clifford algebra examples have been implemented using templates based upon the example of the quaternion objects given by Shi and Steeb[1].  This operator defines both the algebra of the quaternion and also a large number of interfaces and operators to enable its use.  This is an extended version of the Complex type.

 Sum<double > x(''x'',0), y(''y'',0), z(''z'',0), t(''t'',0);
 Quaternion<Sum<double> > Qtxyz(t,x,y,z);
 cout << ''Qtxyz = '' << Qtxyz << endl;

defines a symbolic Quaternion variable and outputs it.  The output is

 Qtxyz = (t,x,y,z)

3.2 Clifford (2)

In the case of the Clifford(2) algebra it is relatively straightforward to adapt the Quaternion code, because the multiplication table is the same size as for the quaternion algebra.  The member objects are named as

 Id e1 e2 I

where I is the bivector e1e2, for symbolic output operations.

The template structure has been adapted, adding new functions and deleting old ones.  The result is a definition which reflects the structure of the algebra.  A numerical variable can be assigned any numerical values in any of its components e.g.

 Clifford2< double > C1(3,4,5,6);

An algebraic version can be assigned any symbolic values and also numerical values, e.g.

 Sum<double>  v1(''v1'',0), v2(''v2'',0);
 Clifford2 <Sum< double > > CV(0,v1,v2,1);
 cout << CV << endl;
 cout << CV*CV << endl;

Symbolic output has been defined for this class using Id e1 e2 and I, so that the output for these examples gives

 v1*e1+v2*e2+I
 (v1^(2)+v2^(2)-1)*Id

where the designators of the different elements of the algebra are built into the definition and can be changed if desired. A fully symbolic variable can be also be declared, and assigned from a symbolic variable using a converter.

 typedef Clifford2 <Sum < double >  > C2SD;
 typedef SumConverter< SC2SD, C2SD, Sum <double> > SC2SDfromSD;
 Sum < Clifford2 < Sum < double > > > example(''name'',0);
 example = SC2SDfromSD::convert(a11);

In order to work as a symbol within the SymbolicC++ Sum class, each the Clifford class needs to meet certain interface requirements of the Sum class.  In particular for correct operation of the Sum class output operator, each Clifford class must have an operator which tests for the sign of the variable using an operator > which returns an answer.  In order to satisfy this requirement, the Clifford2 class has been given such an operator with the fixed answer false to ensure correct handling within the Sum class output operator, although the answer is not meaningful for other uses.

Noncomutative algebra can be implemented as follows.

 Sum < Clifford2 < Sum < double > > > a(''a'',0),b(''b'',0);
 Clifford2 < Sum < double > > c;
 Commutative(c,0); // Sets noncommutative multiplication
 cout << a*b - b*a << endl;

gives the output

 a*b-b*a

If the variables a and b are assigned symbolic values, first a and then b,

 SumDouble a0(''a0'',0),a1(''a1'',0),a2(''a2'',0),a3(''a3'',0),
           b0(''b0'',0),b1(''b1'',0),b2(''b2'',0),b3(''b3'',0);
 Clifford2 < Sum < double > > aa(a0,a1,a2,a3),
                              bb(b0,b1,b2,b3);
 a = aa;
 cout << a*b - b*a << endl;
 b = bb;
 cout << a*b - b*a << endl;

the output is now

 (a0*Id+a1*e1+a2*e2+a3*I)*b-b*(a0*Id+a1*e1+a2*e2+a3*I)
 (-2*a2*b3+2*a3*b2)*e1+(-2*a3*b1+2*a1*b3)*e2+(2*a1*b2-2*a2*b1)*I

showing two stages of symbolic replacement. In the first line the noncommutative setting in SymbolicC++ preserves the order of the terms and in the second line the Clifford(2) multiplication table resolves the terms in the correct way.

The Clifford2 class has been given a function for calculation of the inverse, which implements the algebra discussed in [5]. For example

 cout << aa.inverse() << endl;

gives an output which simplifies to

 (a0^(2)-a1^(2)-a2^(2)+a3^(2))^(-1)*(a0*Id-a1*e1-a2*e2-a3*I)

3.3 Clifford (3)

The implementation of a class for the Clifford (3) algebra follows the same model as for Clifford (2).  The main design issue is the choice of the names and the ordering of the members within a Clifford (3) object.  These have been chosen as follows.

 Id e1 e2 e3 e1e2 e2e3 e3e1 e1e2e3

This choice differs from some other authors, for example Ablamowicz[6] who uses

 Id e1 e2 e3 e1e2 e1e3 e2e3 e1e2e3

The advantage of the ordering used here is that it is symmetrical to any change of identity among e1 e2 and e3.  This means that the multiplication table can be symmetrical in design.  With the increased likelihood of objects with few nonzero members, multiplication has been implemented to take advantage of sparsity, reducing the number of unnecessary multiplications, as compared with the method used in the Clifford2 class.

The inverse function has been programmed using the analysis given in [5], including the two special cases identified there.

3.4 Clifford (2,2)

The implementation of a class for the Clifford (2,2) algebra is a further expansion compared to model used for Clifford (2).  The member objects have been given the names and ordering

 Id e1 e2 f1 f2 e1e2 e1f1 e1f2 f1e2 e2f2 f1f2
 e1f1e2 e1e2f2 e1f1f2 f1e2f2 e1f1e2f2

which is chosen to reflect both symmetry and also to keep together the pairs e1f1 and e2f2 wherever they occur.  Here e1 and e2 are the basis members squaring to +1 and f1 and f2 square to -1.  In this case it is essential to use the sparsity of each object in design of the multiplication table.  

The numerical inverse discussed in [5] has been implemented.

4 Interactive Interface to Tcl using SWIG

The usefulness of the system described so far is limited by the need to recompile the program whenever different calculations are required.  This needs access to the compiler and also a knowledge of programming in C++.  To overcome these limitations the SymbolicC++ code has been interfaced to the interpreted language Tool Control Language (Tcl)[3]. This has been done using C++ code generated automatically using Software Wrapper and Interface Generator(SWIG)[4] which takes as input an interface generator file and the headers for the classes being used.  SWIG does not support template classes directly, but can interface any particular implementation of a template class which is given a type definition.  The interface file can also have macro definitions which make it easy to reuse interface definitions.  When run the system builds a dynamic library which can be called directly by a program written in the Tcl interpretive language.  Tcl includes a graphical user interface, Tk, so that an interactive program can be built which contains access to the functions provided in C++ and wrapped by SWIG. This is an example of the interface code, in this case to set up the class Sum with many functions removed.

 %title ''The Symbol DLL''
 %module Symbol
 %{
 #include ''mysymbol.h'' // Get Template definition
 #define TYPEDEFSUM(a,b) typedef Sum<##a##> Sum##b
 %}
 #define SUM(a,b) \
 %{ \
 TYPEDEFSUM(a,b); \
 %} \
 class Sum##b { public : \
 %readonly \
  SumEnum state; \
 %readwrite \
  Sum##b (char *, int); \
 ~Sum##b##(); \
  Sum##b add (const Sum##b &c); \
  char *stream(); }
 SUM(double,Double);

Using this method it has been possible to interface the Clifford (2) class to Tcl.  Unfortunately, the Tcl language does not support the overloading of operators as in C++, so that the programming use of this is not as easy as would be wished.  Some extra member functions have to be added to the classes.   Access to the C++ output operator has been maintained by a function called stream.  The Clifford (2) system is enabled at the Tcl console by loading the precompiled library called symbol.

 load symbol

Then Tcl programs can be loaded, or commands typed at the console.  The following example defines a Clifford (2) object with numerical values and then outputs its value.  All the template types are now used through type definitions established using macros in the SWIG interface.

 % Clifford2Double x 1 2 3 4
 % Clifford2Double -this [ set x [ x cget -this ] ]
 % $x stream
 Id+2*e1+3*e2+4*I

A symbolic variable can also be defined once symbolic constants have been defined for its members.

 % SumDouble r a0 0
 % SumDouble -this [set r  [ r  cget -this ] ]

and similar definitions for the other symbolic basis vector coefficients.

 % Clifford2SumDouble CSD $r $e1 $e2 $I
 % Clifford2SumDouble -this [ set CSD [ CSD cget -this ] ]
 % $CSD stream
 a0*Id+a1*e1+a2*e2+a3*I

In each case the output response is generated by the library code.  Operations are done using keywords with the objects as arguments.

 % Clifford2SumDouble -this [ set CSD2 [ $CSD add $CSD ] ]
 % $CSD2 stream
 2*a0*Id+2*a1*e1+2*a2*e2+2*a3*I

This example defines a fully symbolic variable and equates it to the previous variable.

 % SumClifford2SumDouble SCSD SCSD 0
 % SCSD equalsT $CSD
 % SCSD stream
 a0*Id+a1*e1+a2*e2+a3*I

Further development is needed of a user interface in Tcl and Tk to hide the rather ugly programming which is needed.

5 Storing Algebra using XML and E4Graph

Most of the usefulness of a system such as described here is in the algebraic results and understanding which are gained.  An investigation has been made of ways in which algebraic results could be stored in a computer data base.  The need is for a flexible system storing not only the results but associated information in both numerica and text, e.g. author and date.  The data needs to be persistent and also recoverable and transferrable.  Use has been made of the E4Graph[6] program and the persistent database it uses, Metakit[7].  Both of these programs, written in C++, are already interfaced to Tcl. E4Graph uses a node and link structure which is completely flexible.  It also has import and export functions for Extensible Markup Language (XML)[8] which provides the means of exporting the content of a database in a reusable text format.  There is a definition in XML of a markup language for mathematics called MathML[9] which can be used for the description of mathematics.  MathML contains two definitions, display MathML, for use in presentation, and content MathML, for use in storing the meaning of mathematical expressions.  It is the latter which it is intended to use to store the results of Clifford algebra calculations in a reusable form.

6 Conclusions

This paper has demonstrated that it is possible to do symbolic calculations in C++ using as a basis the SymbolicC++ program of Tan et al [1,2].  The examples include implementations of the inverse calculations described in [5].  A method is shown to provide an interactive interface using Tcl and SWIG. It is possible to store the results using E4Graph and transfer them using the MathML definitions within XML.

7 References

[1] Tan K.S., W-H. Steeb ”SymbolicC++: An Introduction to Computer Algebra Using Object Oriented Programming”, Springer, 1997

[2] Tan K.S., W-H. Steeb and Y. Hardy ”SymbolicC++: An Introduction to Computer Algebra Using Object Oriented Programming”,second edition, Springer, 2000

[3] J.K Ousterhout, Tcl: An Embeddable Command Language, Proceedings of the USENIX Association Winter Conference, 1990. p. 133-146.

[4] D.M. Beazley, ”SWIG: An Easy to Use Tool for Integrating Scripting Languages with C and C++”, in Proceedings of the 4th USENIX Tcl/Tk Workshop, July 1996. p. 129-139.

[5] J.P. Fletcher, ”Clifford Numbers and their inverses calculated using the matrix representation”, Paper 24, AGACSE 2001.

[6] http://e4graph.sourceforge.net/, J.Levy.

[7] http://www.equi4.com/metakit/wiki.cgi/, J-C Wippler

[8] http://www.w3.org/XML/ or see B. Marchal, ”XML by Example”, QUE, 1999

[9] http://www.w3.org/Math/mathml-faq.html or see S. St Laurent and R. Biggar, ”Inside XML DTDs”, McGrawHill, 1999

John Fletcher May 2001, updated March 2003.