Bayro-Corrochano E., Scheuermann G. Geometric Algebra Computing: in Engineering and Computer Science
Подождите немного. Документ загружается.
448 R. Schott and G.S. Staples
Computational Complexity Reductions Using Clifford Algebras 449
Definition 6 Given ψ ∈ C
3nil
n
⊗ C
nil
|E|
,thegrade-balanced exponential of ψ is
defined by
exp
gb
(u) =
∞
k=0
ψ
k
k!
(k,k)
. (35)
Proposition 7 Let G be a graph on n vertices with Ξ ∈ C
3nil
n
⊗C
nil
|E|
as defined
in (27). Let Girth(G) denote the length of the smallest nontrivial cycle in G. Then,
450 R. Schott and G.S. Staples
as a polynomial in C
3nil
n
⊗C
nil
|E|
⊗R[t],
deg
t
t
n
exp
gb
Ξ
t
−1
=n −Girth(G). (36)
Proof Note first that t
n
exp
gb
(
Ξ
t
) is a polynomial in t of degree at most n. The de-
gree of the polynomial is equal to the smallest exponent k appearing among nonzero
terms in the expansion
exp
gb
Ξ
t
−1 =
n
k=1
Ξ
k
k!t
k
(k,k)
. (37)
By Proposition 6, nonzero terms in the expansion of Ξ
k
(k,k)
represent disjoint
cycle covers of k-vertex subgraphs in G. The smallest positive integer k
0
for which
such a cover exists must correspond to k
0
-cycles in G, i.e., k
0
= Girth(G). Then
t
n
t
k
0
=t
n−Girth(G)
, from which the result is obtained.
Corollary 14 Computing the girth of a graph with n vertices and |E|edges requires
O(nlog n) Cops in C
3nil
n
⊗C
nil
|E|
.
Proof Computing exp
gb
(
Ξ
t
) requires computing
Ξ
k
k!t
k
(k,k)
for 0 ≤ k ≤n.
Proposition 8 Let G be a graph on n vertices with Ξ ∈ C
3nil
n
⊗C
nil
|E|
as defined
in (27). Let Z denote the number of proper cycle covers of G. Then,
dim
Ξ
n
(n,n)
=Z. (38)
Proof Note that Ξ
n
represents n-edge subsets taken from the graph G. Recalling
that any collection of n edges incident with n vertices in a connected graph is a cycle
if and only of every vertex has degree 2. By construction of the three-nil algebra,
the terms of Ξ
n
represent subgraphs in which the maximum vertex degree is two
and the minimum vertex degree is one.
All that remains is to show no vertex of this subgraph can have degree one. By
the Handshaking Lemma (Lemma 3), since the subgraph G
contains n vertices and
n edges, we have
v∈V
G
deg(v) =2n. (39)
Since the maximum vertex degree is two, this sum can be written in the form
v∈V
G
deg(v) =
v∈V
G
deg(v)=1
deg(v) +
v∈V
G
deg(v)=2
deg(v)
=
v ∈V
G
:deg(v) =1
+2
v ∈V
G
:deg(v) =2
Computational Complexity Reductions Using Clifford Algebras 451
=
n −
v ∈V
G
:deg(v) =2
+2
v ∈V
G
:deg(v) =2
= n +
v ∈V
G
:deg(v) =2
=2n. (40)
Hence, |{v ∈ V
G
: deg(v) = 2}| = n. It follows that G
is a graph whose con-
nected components are nontrivial cycles.
Corollary 15 Computing the number of proper cycle covers of a graph on n vertices
and |E| edges requires O(log n) Cops in C
3nil
n
⊗C
nil
|E|
.
5Conclusion
The advantages of a computer architecture capable of dealing naturally with geomet-
ric objects are numerous. If one assumes the existence of such a machine, a natural
measure of algorithmic complexity is the number of Clifford operations (Cops)
required by the algorithm.
In terms of numbers of Cops required, a number of problems of complexity
class NP are of polynomial complexity. We assert that a Clifford computer would
have natural advantages for solving an assortment of combinatorial and graph-
theoretic problems.
Using currently available technology and techniques, the computations per-
formed are not truly geometric operations. Multiplying two multivectors still re-
quires keeping track of nonzero coefficients of blades of all grades. In fact, handling
homogeneous grade-k multivectors requires keeping track of up to
n
k
coefficients
Fig. 8 Time (in secs) required for product of random multivectors in C
nil
n
452 R. Schott and G.S. Staples
using the methods employed here. It is worth noting however that this might be dra-
matically improved by using a multiplicative representation of k-blades such as that
found in the work of Fontijne [6].
Examples were computed on a 2.4 GHz MacBook Pro with 4 GB of 667 MHz
DDR2 SDRAM running Mathematica 6 for MAC OS X with the packages Cliff-
math08 and CliffSymNil08 available online at www.siue.edu~sstaple. Multivector
products in C
nil
n
are computed combinatorially. The times of computing products
of arbitrary randomly generated multivectors in C
nil
n
appear in Fig. 8.
The true power of a geometric computing architecture is yet to be realized. In an
ideal architecture, multiplying two multivectors would require one operation and an
appropriate measurement (projection) to recover the relevant information. However,
an architecture in which the multivector product is of polynomial complexity would
be sufficient for dramatic reductions in complexity.
Acknowledgement The authors thank the referees for a number of helpful comments.
References
1. Abłamowicz, R., Fauser, B.: CLIFFORD—a Maple package for Clifford algebra computa-
tions. http://math.tntech.edu/rafal/
2. Aerts, D., Czachor, M.: Cartoon computation: quantum-like computing without quantum me-
chanics. J. Phys. A: Math. Theor. 40, F259–F263 (2007)
3. Ben-Dor, A., Halevi, S.: Zero-one permanent is P-complete, a simpler proof. In: Proceedings
of the 2nd Israel Symposium on the Theory and Computing Systems, pp. 108–117 (1993)
4. Chien, S., Rasmussen, L., Sinclair, A.: Clifford algebras and approximating the permanent.
J. Comp. Syst. Sci. 67, 263–290 (2003)
5. Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb.
Comput. 9, 251–280 (1990)
6. Fontijne, D.: Efficient implementation of geometric algebra. Ph.D. thesis, University of Ams-
terdam (2007)
7. Fontijne, D., Bouma, T., Dorst, L.: GAIGEN: a geometric algebra implementation generator,
University of Amsterdam, NL, July 2002. http://www.science.uva.nl/ga/gaigen
8. Franchini, S., Gentile, A., Grimaudo, M., Hung, C.A., Impastato, S., Sorbello, F., Vassallo, G.,
Vitabile, S.: A sliced coprocessor for native Clifford algebra operations. In: Proceedings of
the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools
(DSD 2007), pp. 436–439 (2007)
9. Gentile, A., Segreto, S., Sorbello, F., Vassallo, G., Vitabile, S., Vuollo, V.: CliffoSor, an innova-
tive FPGA-based architecture for geometric algebra. In: Proceedings of the International Con-
ference on Engineering of Reconfigurable Systems and Algorithms (ERSA 2005), pp. 211–
217
10. Gentile, A., Segreto, S., Sorbello, F., Vassallo, G., Vitabile, S., Vuollo, V.: CliffoSor: a par-
allel embedded architecture for geometric algebra and computer graphics. In: Proceedings of
the IEEE International Workshop on Computer Architecture for Machine Perception (CAMP
2005), pp. 90–95. IEEE Comput. Soc., Los Alamitos (2005)
11. Leopardi, P.: The GluCat home page, http://glucat.sourceforge.net/
12. Mishra, B., Wilson, P.: Color edge detection hardware based on geometric algebra.
http://eprints.ecs.soton.ac.uk/13188/
13. Mishra, B., Wilson, P.: Hardware implementation of a geometric algebra processor core. In:
Proceedings of ACA 2005, IMACS, Int. Conf. on Advancement of Computer Algebra, Nara,
Japan (2005). http://eprints.ecs.soton.ac.uk/10957/
Computational Complexity Reductions Using Clifford Algebras 453
14. Perwass, C.: The CLU Project web page, http://www.perwass.de/cbup/clu.html
15. Perwass, C., Gebken, C., Sommer, G.: Implementation of a Clifford algebra co-processor de-
sign on a field programmable gate array. In: Clifford Algebras Applications to Mathemat-
ics, Physics, and Engineering. Progress in Mathematical Physics, vol. 34. Birkhäuser, Basel
(2004)
16. Porteous, I.: Lecture 2: Mathematical structure of Clifford algebras. In: Abłamowicz, R.,
Sobczyk, G. (eds.) Lectures on Clifford (Geometric) Algebras and Applications. Birkhäuser,
Basel (2003)
17. Schott, R., Staples, G.S.: Nilpotent adjacency matrices and random graphs. Ars Comb. (2010,
to appear)
18. Schott, R., Staples, G.S.: Nilpotent adjacency matrices, random graphs, and quantum random
variables. J. Phys. A: Math. Theor. 41, 155205 (2008)
19. Schott, R., Staples, G.S.: Reductions in computational complexity using Clifford algebras.
Adv. Appl. Clifford Algebr. (2010, to appear)
20. Staples, G.S.: Clifford-algebraic random walks on the hypercube. Adv. Appl. Clifford Algebr.
15, 213–232 (2005)
21. Staples, G.S.: Graph-theoretic approach to stochastic integrals with Clifford algebras. J. Theor.
Probab. 20, 257–274 (2007)
22. Staples, G.S.: Norms and generating functions in Clifford algebras. Adv. Appl. Clifford Al-
gebr. 18, 75–92 (2008)
23. Valiant, L.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189–201
(1979)
24. West, D.: Introduction to Graph Theory, 2nd edn. Prentice Hall, New York (2001)
Part VII
Efficient Computing with Clifford
(Geometric) Algebra
Efficient Algorithms for Factorization and Join
of Blades
Daniel Fontijne and Leo Dorst
Abstract Subspaces are powerful tools for modeling geometry. In geometric al-
gebra, they are represented using blades and constructed using the outer product.
Producing the actual geometrical intersection (
meet) and union (join) of subspaces,
rather than the simplified linearizations often used in Grassmann–Cayley algebra,
requires efficient algorithms when blades are represented as a sum of basis blades.
We present an efficient blade factorization algorithm and use it to produce imple-
mentations of the
join that are approximately 10 times faster than earlier algorithms.
1 Introduction
Blades, defined as outer products of vectors, are used in geometric algebra to rep-
resent geometric objects such as directions, points, planes, and circles. In imple-
mentations of geometric algebra [9, 11, 12], blades are commonly represented as
weighted sums of orthogonal basis blades, which we call the additive representa-
tion [10]. A basis blade is the outer product of basis vectors. 2
n
basis blades are
required to form a basis for an n-dimensional geometric algebra (2
n
is the size of
the set of all combinations of up to n basis vectors). This basis of blades allows for
straightforward and efficient implementation of many bilinear products such as the
outer product, at least for n<10.
However, the additive representation makes the implementation of the true sub-
space union (
join) and intersection (meet) substantially more involved and expensive
than bilinear products, because they are nonlinear products [6]. To implement the
join of blades in additive representation, one of the input blades must be (partially)
factored in terms of the outer product.
Unfortunately, the terms
meet and join have historically been used to denote sim-
plified linearizations of the true subspace intersection and union. For example, [8]
D. Fontijne (
)
University of Amsterdam, Kruislaan 403, 1098 SJ, Amsterdam, The Netherlands
e-mail: fontijne@science.uva.nl
E. Bayro-Corrochano, G. Scheuermann (eds.), Geometric Algebra Computing,
DOI 10.1007/978-1-84996-108-0_21, © Springer-Verlag London Limited 2010
457