Bayro-Corrochano E., Scheuermann G. Geometric Algebra Computing: in Engineering and Computer Science

Подождите немного. Документ загружается.

428 A. Patyk

Fig. 19 Comparison of recognition for GA, BSC, and HRR—(5a)see

obj

prove redundant for GA sentences having a lesser number of blades; nevertheless, it

is only fair to provide relatively the same data size for all compared models.

Figures 17, 18, 19 show comparison of performance for GA, BSC, and HRR, and

tested sentences range in meaningful-to-noisy blades ratio from 1:2 to 7:2. Clearly,

GA with the use of Hamming and Euclidean measure ensures quite a remarkable

recognition percentage for sentences of great complexity and therefore great noise,

Geometric Algebra Model of Distributed Representations 429

whereas the HRR model works better for statements of low complexity. There is

no signiﬁcant difference in performance of the BSC model as far as complexity of

tested sentences is concerned. BSC does remain the best model, provided that vector

lengths for BSC are sufﬁciently longer than that of GA. Under uniform length of

vectors and blades, GA recognizes sentences better than HRR or BSC, regardless of

their complexity.

7Conclusion

We have presented a new model of distributed representation that is based on the

way humans think, while models developed so far were designed to use arrays of

numbers mainly in order to be easily simulated by computers.

After a brief recollection of the main ideas behind the GA model, we inves-

tigated three types of sentence constructions, namely the Plate construction, the

agent–object construction, and the agent–object construction with odding blades.

Two methods of asking questions were also investigated. As a result, in face of

shortcomings of recognition based solely on the inner product, matrix representa-

tion has been employed as a recognition tool for the GA model. Using test results

computed on a toy model, we have shown that Hamming and Euclidean measures

of similarity perform very well under the agent–object construction with odding

blades.

We also studied the ways in which the number of potential answers is affected by

situations in which the system draws at random identical blades denoting different

atomic objects or in which identical sentence chunks are produced from different

blades. A formula estimating the number of potential counterparts of a noisy piece

of information has been derived. Finally, the performance of the GA model has been

compared with that of BSC and HRR models using sentences of various complexity.

Acknowledgements I would like to thank Rafał Abłamowicz and Ian Bell for many inspiring

conversations that took place during the AGACSE conference in Grimma in August 2008. Further-

more, my participation in that conference would not have been possible without the support from

Centrum Leo Apostel (CLEA) at the Vrije Universiteit in Brussels. I also acknowledge support

from the LFPPI network.

References

1. Aerts, D., Czachor, M., De Moor, B.: On geometric-algebra representation of binary spatter

codes. Preprint (2006). arXiv:cs/0610075 [cs.AI]

2. Aerts, D., Czachor, M.: Cartoon computation: Quantum-like algorithms without quantum me-

chanics. J. Phys. A 40, F259 (2007)

3. Aerts, D., Czachor, M.: Tensor-product vs. geometric-product coding. Phys. Rev. A 77,

012316 (2008). arXiv:0709.1268 [quant-ph]

4. Aerts, D., Czachor, M., De Moor, B.: Geometric analogue of holographic reduced representa-

tion. Preprint (2007). arXiv:0710.2611

430 A. Patyk

5. Bayro-Corrochano, E.: Handbook of Geometric Computing. Springer, Berlin (2005)

6. Czachor, M.: Elementary gates for cartoon computation. J. Phys. A 40, F753 (2007)

7. Dorst, L., Fontijne, D., Mann, S.: Geometric Algebra for Computer Science. Morgan-

Kauffman, San Mateo (2007)

8. Hestenes, D.: Space-Time Algebra. Gordon and Breach, New York (1966)

9. Hestenes, D., Sobczyk, G.: Clifford Algebra to Geometric Calculus: A Uniﬁed Language for

Mathematics and Physics. Reidel, Dordrecht (1984)

10. Kanerva, P.: Binary spatter codes of ordered k-tuples. In: von der Malsburg, C., et al. (eds.)

Artiﬁcial Neural Networks ICANN Proceedings. Lecture Notes in Computer Science, vol.

1112, pp. 869–873. Springer, Berlin (1996)

11. Kanerva, P.: Fully distributed representation. In: Proc. 1997 Real World Computing Sympo-

sium (RWC’97, Tokyo), Real World Computing Partnership, Tsukuba-City, Japan, pp. 358–

365 (1997)

12. Lounesto, P.: Clifford Algebras and Spinors, 2nd edn. Cambridge University Press, Cambridge

(2001)

13. Plate, T.: Holographic Reduced Representation: Distributed Representation for Cognitive

Structures. CSLI Publications, Stanford (2003)

14. Smolensky, P.: Tensor product variable binding and the representation of symbolic structures

in connectionist systems. Artif. Intell. 46, 159–216 (1990)

15. Smolensky, P., Dolan, C.: Tensor product production system: a modular architecture and rep-

resentation. Connect. Sci. 1(1), 53–68 (1989)

Computational Complexity Reductions Using

Clifford Algebras

René Schott and G. Stacey Staples

Abstract Given a computing architecture based on Clifford algebras, a natural con-

text for determining an algorithm’s time complexity is in terms of the number of

geometric (Clifford) operations required. In this paper the existence of such a pro-

cessor is assumed, and a number of graph-theoretical problems are considered. This

paper is an extension of previous work, in which the authors deﬁned the “nilpo-

tent adjacency matrix” associated with a ﬁnite graph and showed that a number of

graph problems of complexity class NP are polynomial in the number of Clifford

operations required. Previous results are recalled and illustrated with Mathematica

examples. New results are obtained, and old results are improved by the develop-

ment of new techniques. In particular, a matrix-free approach is developed to count

matchings, compute girth, and enumerate proper cycle covers of ﬁnite graphs. These

new results and techniques are also illustrated with Mathematica examples.

1 Introduction

This paper is an extension of earlier work (cf. [19]), in which the current au-

thors investigated complexity reductions for a number of combinatorial and graph-

theoretic problems. The graph-theoretic results of that paper were based primarily

on nilpotent adjacency matrix methods developed in a number of earlier publica-

tions [17, 18, 20–22].

Combinatorial properties of Clifford algebras provide the underlying context for

this work. All algebras used herein can be realized within Clifford algebras of ap-

propriate signature and grow with the size of the graph being considered. An ideal

architecture would be able to perform computations in Clifford algebras of arbitrary

dimension.

G.S. Staples (



)

Department of Mathematics and Statistics, Southern Illinois University Edwardsville,

Edwardsville, IL 62026-1653, USA

e-mail: sstaple@siue.edu

E. Bayro-Corrochano, G. Scheuermann (eds.), Geometric Algebra Computing,

DOI 10.1007/978-1-84996-108-0_20, © Springer-Verlag London Limited 2010

431

432 R. Schott and G.S. Staples

The previous graph results are recalled in summary in Sect. 3, where additional

examples are computed using Mathematica. In Sect. 4, new results are obtained,

and some previous results are improved by eliminating adjacency matrices, thereby

removing the consideration of matrix multiplication in determining computational

complexity.

Moreover, results on graph and vertex coverings by disjoint “proper” cycles are

obtained by introducing the “three-nil algebra” constructed within a Clifford algebra

of appropriate signature. The generators {ξ

}

1≤i≤n

of this algebra satisfy ξ

and ξ

=0for1≤i, j ≤n.

Given a computing architecture based on Clifford algebras, the natural context

for determining an algorithm’s time complexity is in terms of the number of geo-

metric (Clifford) operations required. This paper assumes the existence of such a

processor and examines the number of Clifford operations needed for a number of

combinatorial problems known to be of NP time complexity.

While Clifford algebra computations can be performed on general purpose

processors through the use of software libraries like CLU [14], GluCat [11],

GAIGEN [7], and the Maple package CLIFFORD [1], direct hardware implementa-

tions of data types and operators is the best way to exploit the computational power

of Clifford algebras. To this end, a number of hardware implementations have been

developed.

To our knowledge, the ﬁrst such hardware implementation was a Clifford copro-

cessor design developed by Perwass, Gebken, and Sommer [15]. Another was the

color edge detection hardware developed by Mishra and Wilson [12, 13], whose

work focused on the introduction of a hardware architecture for applications involv-

ing image processing.

More recently, Gentile, Segreto, Sorbello, Vassallo, Vitabile, and Vullo have de-

veloped a parallel embedded coprocessing core that directly supports Clifford alge-

bra operators (cf. [8–10]). The prototype was implemented on a Field Programmable

Gate Array, and initial tests showed a 4× speedup for Clifford products over the

analogous operations in GAIGEN.

Also of interest is the work of Aerts and Czachor [2], who have shown that

quantum-like computations can be performed within Clifford algebras without the

associated problem of noise and need for error correction.

2 Preliminaries

Deﬁnition 1 (Clifford algebra of signature (p, q)) For ﬁxed n ≥ 1, the 2

dimensional algebra C

p,q

(p +q =n) is deﬁned as the associative algebra gener-

ated by the collection {e

} (1 ≤i ≤n) along with the unit scalar e

= e

∅

= 1 ∈R,

subject to the following multiplication rules:

=−e

for i =j, (1)



1, 1 ≤i ≤p,

−1,p+1 ≤i ≤n.

(2)

Computational Complexity Reductions Using Clifford Algebras 433

Products are multi-indexed by subsets of [n]={1,...,n} (in canonical order)

according to



ι∈i

, (3)

where i

is an element of the power set 2

[n]

Deﬁne f

= (e

2n+i

) ∈ C

2n,2n

for each 1 ≤ i ≤2n. Then by deﬁning ζ

2j−1

for each 1 ≤j ≤n, the following useful algebra is obtained.

Deﬁnition 2 Let C

nil

denote the real Abelian algebra generated by the collection

{ζ

} (1 ≤i ≤n) along with the scalar 1 = ζ

subject to the following multiplication

rules:

= ζ

for i =j, and (4)

= 0for1≤i ≤n. (5)

It is evident that a general element u ∈C

nil

can be expanded as

u =



i∈2

[n]

, (6)

where i

∈ 2

[n]

is a subset of [n]={1, 2,...,n} used as a multi-index, u

∈ R, and



ι∈i

Given u ∈C

nil

, deﬁne the grade-k part of u by

u



|i|=k

, (7)

where |i

| denotes the cardinality of the multi-index i.

Recalling the Clifford algebra C

p,q,r

deﬁned by Porteous [16], in which e

for p +q +1 ≤i ≤p +q +r, one could simply deﬁne ζ

2i−1

for 1 ≤i ≤n

in the Clifford algebra C

0,0,2n

. Equivalently, one could use disjoint bivectors of the

Grassmann algebra.

Note that deﬁning ξ

=ζ

2i−1

+ζ

∈C

nil

for 1 ≤i ≤n gives ξ

=0 and ξ

. This construction leads to another useful commutative algebra.

Deﬁnition 3 Let n>0 be an integer, and let the collection {ξ

,...,ξ

} satisfy the

following: ξ

= 0 if and only if k ≥ 3 for each 1 ≤ i ≤ n and ξ

= ξ

for

1 ≤i, j ≤n.Thethree-nil algebra is the 3

-dimensional algebra generated by the

collection {ξ

} along with the unit scalar and is denoted by C

3nil

434 R. Schott and G.S. Staples

Note that elements of the three-nil algebra have canonical expansion of the fol-

lowing form:

u =



v∈Z

···ξ

. (8)

Given vector v ∈Z

, let diag(v) denote the n ×n diagonal matrix whose main

diagonal is v.Givenu ∈C

3nil

, deﬁne the grade-k part of u by

u



v∈Z

rank(diag(v))=k

···ξ

. (9)

In other words, the grade-k part of u is the expansion over terms with k distinct

generators. This deﬁnition extends naturally to the grade-(j, k) part of an element

in C

3nil

⊗C

nil

Remark 1 Letting ε

(1 + e

n+i

) ∈ C

n,n

for each 1 ≤ i ≤ n gives another

useful commutative algebra whose generators are idempotent, i.e., elements of

{ε

}

1≤i≤n

satisfy the following multiplication rules:

= ε

for i =j, and (10)

= ε

for 1 ≤i ≤n. (11)

Combinatorial properties of this algebra make it applicable to graph theory as

well [17, 19].

Letting u denote an arbitrary element of C

nil

,thescalar sum of coefﬁcients will

be denoted by

u =



i∈2

[n]

u, ζ

=



i∈2

[n]

. (12)

The deﬁnitions of scalar sum and grade-k part extend naturally to C

3nil

A number of norms can be deﬁned on C

nil

. One that will be used later is the

inﬁnity norm deﬁned by





i∈2

[n]



∞

= max

i∈2

[n]

|. (13)

An algorithm’s time complexity is typically determined by counting the number

of operations required to process a data set of size n in worst-, average-, and best-

case scenarios. The operation of multiplying two integers is typical. Multiplying a

pair of integers in classical computing is assumed to require a constant interval of

time, independent of the integers. The architecture of a classical computer makes

this assumption natural.

Computational Complexity Reductions Using Clifford Algebras 435

The existence of a processor whose registers accommodate storage and manipu-

lation of elements of C

♦

is assumed through the remainder of this paper.

The C complexity of an algorithm will be determined by the required number

of C

♦

operations or Cops required by the algorithm. In other words, multiplying

(or adding) a pair of elements u, v ∈C

♦

will require one Cop in C

♦

, where ♦

can be replaced by either “nil” or “3nil”.

Evaluation of the inﬁnity norm is another matter. In one possible model of such

an evaluation, the scalar coefﬁcients in the expansion of u ∈ C

♦

are ﬁrst paired

off, and all pairs are then compared in parallel. In this way, evaluation of the inﬁnity

norm has complexity O(log2

) =O(n) (cf. [19]).

2.1 Graph Preliminaries

The reader is referred to [24] for graph theory beyond the essential notation and

terminology found here. A graph G =(V , E) is a collection of vertices V and a set

E of unordered pairs of vertices called edges. Two vertices v

∈V are adjacent

if there exists an edge e

={v

}∈E. In this case, the vertices v

and v

are said

to be incident with e

The number of edges incident with a vertex is referred to as the degree of the

vertex. A graph is said to be regular if all its vertices are of equal degree. A graph

is ﬁnite if V and E are ﬁnite sets, that is, if |V | and |E| are ﬁnite numbers.

A k-walk {v

,...,v

} inagraphG is a sequence of vertices in G with initial

vertex v

and terminal vertex v

such that there exists an edge (v

j+1

) ∈ E for

each 0 ≤j ≤ k −1. A k-walk contains k edges. A k-path is a k-walk in which no

vertex appears more than once. A closed k-walk is a k-walk whose initial vertex is

also its terminal vertex. A k-cycle is a closed k-path with v

For convenience, two-cycles (which have a repeated edge) will be allowed in the

current work. The term proper cycle will refer to any cycle of length three or greater.

A Hamiltonian cycle is an n-cycle in a graph on n vertices, i.e., it contains V.

Given a graph G,thecircumference and girth of G are deﬁned as the lengths of the

longest and shortest cycles in G, respectively.

Given a graph G = (V , E) on n vertices, a cycle cover of G is a collection of

cycles {C

,...,C

} contained as subgraphs of G such that each vertex of G is con-

tained in exactly one of the cycles.

A graph G is said to be connected if for every pair of vertices v

, v

in G, there

exists a k-walk on G with initial vertex v

and terminal vertex v

for some positive

integer k.

A connected component of a graph G is a connected subgraph G



of maximal

size. In other words, V(G



) ⊆ V(G), E(G



) ⊆ E(G), and there is no connected

subgraph G



with the property V(G



)  V(G



A tree is a connected graph that contains no cycles.

Given a graph G = (V , E),amatching of G is a subset E

⊂ E of the edges

of G having the property that no pair of edges in E

shares a common vertex. The

436 R. Schott and G.S. Staples

largest possible matching on a graph with n vertices consists of n/2 edges, and such

a matching is called a perfect matching.

The following graph-theoretic results will be useful in later sections.

Lemma 1 Let G be a connected graph on n ≥ 2 vertices. Then G is a tree if and

only if G contains n −1 edges.

Proof Proof is by induction on the number of vertices n. When n = 2, the graph

G contains one edge and is a tree by deﬁnition. Assuming the lemma is true for

some positive integer n ≥ 2, let G be a connected graph on n vertices, and let the

graph H be constructed by appending one vertex v to G. In other words, V(H)=

V(G)∪{v}. In order to make H connected, one edge must be appended, joining v

to some existing vertex u of G.NowH is a connected graph on n +1 vertices and

is a tree, since v is incident with only one edge.

It remains to be seen that appending two edges incident with v prevents H from

being a tree. Suppose a second edge incident with v is appended to H . This edge

is incident with some vertex w = u of G. Since G is connected, there exists a walk

in G having initial vertex u and terminal vertex w. Appending vertex v and

its two

incident edges to G yields a cycle in H . Thus, H cannot be a tree.

Hence, at most one edge can be appended to G in constructing H .The(n +1)-

vertex connected graph H consists of n edges, and the proof is complete. 

Lemma 2 Let G be a connected graph on n ≥ 3 vertices. Then G is a cycle if and

only if G is regular of degree 2.

Proof Proof is by induction on the number of vertices n. Note that when n = 3,

the only connected graph on three vertices of degree 2 is the 3-cycle. Assume that

the lemma is true for some n ≥ 3 and let G be a connected graph on n vertices

containing n edges.

Let H be a connected graph constructed from G by appending one vertex v and

an edge incident with v. The edge incident with v must also be incident with a

vertex u of G, which is now of degree 3. To correct this, one edge incident with u

and another vertex w must be removed, lowering the degree of w to 1. In order to

make H regular of degree 2, a new edge incident with v and w is appended. This

makes H a cycle on n +1 vertices. 

Lemma 3 (Handshaking Lemma) If G is any graph of e edg

es, then



v∈V

deg(v) =2e. (14)

Proof Since each edge is incident with exactly two vertices, summing degrees over

all vertices counts each edge exactly twice. 

Computational Complexity Reductions Using Clifford Algebras 437

3 Complexity Reduction for Graph Problems: Nilpotent

Adjacency Matrix Approach

In this section, methods and results of the initial work [19] are recalled, and a num-

ber of Mathematica examples are presented. In the subsequent section, new methods

are developed, some results are improved, and some new results are obtained.

Deﬁnition 4 Let G be a graph on n vertices, and let {ζ

},1≤i ≤n denote the null-

square generators of C

nil

. Deﬁne the nilpotent adjacency matrix associated with G



if (v

) ∈E(G),

0 otherwise.

(15)

Thus, Λ deﬁned over C

nil

implies that Λ

is an n ×n zero matrix for all k>n.

Theorem 1 Let Λ be the nilpotent adjacency matrix of an n-vertex graph G. For

any m>1 and 1 ≤i ≤n, summing the coefﬁcients of (Λ

)

yields the number of

m-cycles based at v

occurring in G.

Proof Proof is by induction on m. Entries of (Λ

)

are sums of products of ζ

with each product representing the vertices contained in a closed walk of length

m based at the ith vertex. Because ζ

= 0 for each j , terms involving revisited

vertices reduce to zero. 

Example 1 To count the 7-cycles in the 16-vertex graph of Fig. 1, the nilpotent ad-

jacency matrix is constructed over C

nil

. Computations are performed with Mathe-

matica procedures available online at http://www.siue.edu/~sstaple.

Fig. 1 Randomly generated

graph on 16 vertices