Stéphane Breuils
email: breuils@nii.ac.jp

Vincent Nozick
email: vincent.nozick@univ-eiffel.fr

Akihiro Sugimoto
email: sugimoto@nii.ac.jp

Optimal Parenthesizing of Geometric Algebra Products

Manipulating objects using geometric algebra may involve several associative products in a single expression. For example, an object can be constructed by the outer product of multiple points. This number of products can be small for some conformal algebra and high for higher dimensional algebras such as quadric conformal geometric algebras. In these situations, the order of products (i.e. the choice of the parenthesis in the expression) should not change the final result but may change the overall computational cost, according to the grade of the intermediate multivectors. Indeed, the usual left to right way to evaluate the expression may not be most computationally efficient. Studies on the number of arithmetic operations of geometric algebra expressions have been limited to products of only two homogeneous multivectors. This paper shows that there exists an optimal order in the evaluation of an expression involving geometric and outer products, and presents a dynamic programming framework to find it.

Introduction

Geometric algebra products

Geometric algebra presents intuitive solutions for problems related to geometry. Its theory is more and more investigated in various research fields like physics, mathematics or computational geometry, see [START_REF] Kanatani | Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for Computer Vision and Graphics[END_REF][START_REF] Lasenby | Calculating the rotor between conformal objects[END_REF][START_REF] De Keninck | Geometric algebra levenberg-marquardt[END_REF] for some examples. In contrast, in the computer science field, the study of computational aspects of the geometric algebra operators is still limited. The pioneering work [START_REF] Fontijne | Efficient Implementation of Geometric Algebra[END_REF] gave some results about complexity of geometric algebra products in the worst case. The worst case here means that all the elements of a multivector with multiple grades are non-zero. This study was then extended by [START_REF] Breuils | Computational aspects of geometric algebra products of two homogeneous multivectors[END_REF] by investigating the number of arithmetic products required for the geometric product, the outer product, and the inner product of two full homogeneous multivectors, i.e., multivectors with non-zero components only for a single grade. The scope of [START_REF] Breuils | Computational aspects of geometric algebra products of two homogeneous multivectors[END_REF] is well suited for expressions involving two full multivectors like intersections of two geometric objects in conformal geometric algebras. However, the representation of geometric objects in quadric conformal geometric algebras [START_REF] Breuils | Quadric conformal geometric algebra of R 9,6[END_REF] includes more than two multivectors in operands, and the arguments of [START_REF] Breuils | Computational aspects of geometric algebra products of two homogeneous multivectors[END_REF] are not valid any more in such a case. The investigation on products of more than two multivectors is desired.

In this paper, we focus on products having the associative property. If the expression consists of only products that have the associative property, we only have to pay our attention to efficiently parenthesize operands in computation. The usual left to right way of computing the expression is not always the most computationally efficient. Moreover, we focus on full homogeneous multivectors since they are the representation of most geometric algebra objects. Note that in many applications, the geometric algebra entity representing any rigid transformations is also often represented as a sum of quasi full homogeneous multivectors.

Contributions

This paper focuses on products of more than two multivectors where all the products in the expression have the associative property. More specifically, this paper considers only products of more than two multivectors where the products are either outer products or geometric products. We then show that there exists an optimal parenthesizing order with respect to computational cost in the evaluation of an expression. Then, we describe a dynamic programming algorithm that yields the optimal product order. We remark that the inner product is not our interest in this paper because it is not associative.

Preliminaries

Notations

As commonly used in the state-of-the-arts ( [START_REF] Dorst | Geometric Algebra for Computer Science, An Object-Oriented Approach to Geometry[END_REF] and [START_REF] Perwass | Geometric algebra with applications in engineering[END_REF]), lower-case bold letters refer to vectors (vector a) and lower-case non-bold letters to multivector coordinates (coefficient a i ). Multivectors and k-vectors are denoted with upper-case non-bold letters (multivector A). The part of grade k of a multivector A is denoted by A k . The total number of basis blades is 2 d , where d is the dimension of the vector space, and in this case, the number of basis blades e i of grade 1.

By assumption, a multivector A is not necessarily homogeneous but is defined as the sum of homogeneous multivectors. Given the dimension d of the vector space, the set of possible grades for A is

K A where K A ⊆ {0, 1, • • • , d}. Then, A can be defined as A = k∈K A A k . (1)

Product of two multivectors

Following the notation of Equation (1), the product of two multivectors A and B is then

A B = k A ∈K A A k A k B ∈K B B k B , (2)
where can be either the outer product or the geometric product. The linearity of the products of geometric algebra yields

A B = k A ∈K A k B ∈K B A k A B k B . (3)
Theorems 2.1 and 4.1 of [START_REF] Breuils | Computational aspects of geometric algebra products of two homogeneous multivectors[END_REF] give the optimal number of arithmetic operations of the product between two homogeneous multivectors of respective grades k a and k b . As for the outer product ∧, this number of arithmetic operations is:

p ∧ ka,k b = 2 d k a + k b k a + k b k a , (4)
where n k is the binomial coefficient. On the other hand, the number of arithmetic operations for the geometric product * is:

p * ka,k b = 2 kc∈I d k c k c k a -k b + k c 2 d -k c k a + k b -k c 2 , ( 5
)
where

I = {|g a -g b |, |g a -g b | + 2, . . . , g a + g b }.
In the more general situation where the two multivectors may not be homogeneous, the product distributivity mentioned in Equation ( 3) leads to a double loop over the respective grades of the two multivectors. Thus, the number of required operations is the sum of all per-grade contributions, as described in Algorithm 1.

k A ∈K A k B ∈K B kc∈I d kc kc ka -k b + kc 2 d -kc ka + k b -kc 2
The resulting multivector usually has a different grade from the two operands used for its computation. For the outer product of homogeneous multivectors C = A ∧ B, the grade of C will just be the sum of the grades of A and B. For general multivectors, we again have to follow Equation 3 to compute the set of resulting grades. The geometric product is a bit more complex and can generate a non-homogeneous multivector even from two homogeneous multivectors. The resulting grades of a product between two general multivectors is summarised in Algorithm 2. For more details about these results, the reader can refer to [START_REF] Breuils | Computational aspects of geometric algebra products of two homogeneous multivectors[END_REF]. Note that K ∧ or K * can return an empty set of grades (e.g. the wedge of d + 1 vectors in a d-dimensional vector space), then the computational cost is 0 since the resulting product is also 0.

Algorithm 2: Computation of the set of grades resulting to the product of two multivectors.

11 foreach kc ∈ {|ka -k b |, |ka -k b | + 2, • • • , ka + k b } do 12 if kc ≤ d then 13 KC = KC ∪ kc

Optimal parenthesising of products

We show that the choice of the order of the product in an expression can affect the complexity of the product. Consider, for example, the following expression A 1 ∧ A 2 ∧ A 3 in a 10-dimensional space, where the grade of each multivector is grade(A 1 ) = 4, grade(A 2 ) = 3, grade(A 3 ) = 2.

There are in that case two possible parenthesings, the left to right way as

(A 1 ∧ A 2 ) ∧ A 3 , (6)
and the right to left way:

A 1 ∧ (A 2 ∧ A 3 ). (7)
In the first case, the product A 1 ∧ A 2 of Equation ( 6) generates a multivector of grade 7, that is finally wedged to A 3 . According to Equation ( 4), the number of operations for A 1 ∧ A 2 is 8400 and then 720 for the second outer product, leading to a total of 9120 arithmetic operations. On the other hand, the first product A 2 ∧ A 3 of Equation ( 7) generates a multivector of grade 5, that is wedged to A 1 . The overall computational cost of this product is 5040 for the first product and 2520 for the second, resulting in 7560 arithmetic operations in total. Thus, in this case, choosing the second way of parenthesising brings a 1.5 times gain in terms of numerical operations. Obviously, the gain can be much higher for longer expressions.

Expressions

Throughout this paper, we consider an expression as the products of n multivectors:

A 1 * A 2 * • • • * A n , n ∈ N (8)
or

A 1 ∧ A 2 ∧ • • • ∧ A n , n ∈ N. (9)
Since the outer product and the geometric product are binary operators, i.e. operators between two operands, this overall computation involves the computation of intermediate results. Let A 1,n be the chain of multivectors defined by the expression to compute, and A i,j (0 < i < j ≤ n) a sub-chain resulting from the computation of the product from the multivector A i to the multivector A j . The number of arithmetic operations resulting from the product of two successive multivector chains A i,j and A j+1,k is denoted by P i,j,k . where can be either ∧ or * .

Problem formulation

Let C i,j be the minimum number of arithmetic operations of the computation (the cost to minimise) of the product between the i th multivector up to the j th multivector. In the final result, we seek for the computation of C 1n related to the full expression. For i < j, this is equivalent to seek for

C i,j = min s∈[i,j-1] C i,s + C s+1,j + P i,s,j . (10)
This optimal cost C i,j will be used to define the optimal parenthesising indices 2D table S of size n × n, where S i,j = s (i < j) means that the expression

A i A i+1 • • • A j should be parenthesised as (A i • • • A s ) (A s+1 • • • A j ). (11)

Minimisation

An easy way to achieve this minimisation is to use a recursive method. However, such an approach will lead to multiple travels over the same recursive sub-trees, resulting in an exponential complexity. This kind of problems was already addressed for the matrix chain product, for example in [START_REF] Aho | The design and analysis of computer algorithms[END_REF], by using dynamic programming. The problem is the computation of the same sub-problems for different depth of recursion. The proposed approach to solve it consists in memorising the solution to sub-problems in a bottom-up scheme. Each sub-problem is uniquely identified by the two bounding indices (i, j), in the computation of C i,j , S i,j and K i,j as 2D tables. These tables can be iteratively filled with a bottom up approach.

We achieve our minimisation using the dynamic programming framework. Our proposed method first considers the sub-chains of length one. They correspond to single multivectors and thus take a cost C i,i = 0, meaning no optimal parenthesising index. The sub-chains of length two can also be directly computed from Algorithms 1 and 2, where C i,i+1 = P i,i,i+1 = P (K Ai , K Ai+1 ). Obviously, S i,i+1 = i and K i,i+1 = K (K Ai , K Ai+1 ). Then, the sub-chains of length 3 can be computed from the sub-chains of length 2 using Equation [START_REF] Lasenby | Calculating the rotor between conformal objects[END_REF], and so on. The resulting algorithm that computes the optimal parenthesising for each sub-expressions is shown in Algorithm 3.

Once 2D table S is computed, the product can be optimally computed by a recursive travel starting from S 1,n , as shown in Algorithm 4. In case of a code optimisation, a similar recursive scheme can be adopted to add the optimal parenthesising on the code.

We remark that the complexity of this algorithm is not exponential but polynomial in O(n 3 ), see [START_REF] Aho | The design and analysis of computer algorithms[END_REF]. Note that in the matrix chain product context, there exist some faster methods in O(n × log n), like [START_REF] Hu | Computation of matrix chain products. part i[END_REF] however, these methods are complex to setup. Moreover, in geometric algebra, n is usually not high enough to see a significant difference.

Discussion and applications

It is not difficult to modify Algorithm 3 so that it computes the worst parenthesis instead of the best, which in turn results in the maximum number of arithmetic operations. We merely have to replace the sign '<' by '>' in line 19 of Algorithm 3 and to change the initialisation of C i,j to 0 in line 16.

From these two algorithms, we can also extract the gain of the optimal parenthesis. The results we have, show that the maximum gain increases as n (the number of multivectors) increases. Moreover, the gain also increases as the dimension increases. For a fixed number of multivectors in the expression, the gain becomes highest when the sum of the grades of the operands is near the dimension for expressions where the outer product appears.

Furthermore, a practical usage of these kinds of algorithms is in code generators and optimizers. For example, the code developed from the expression c = Ci,s + Cs+1,j+ P (Ki,s, Ks+1,j) // if the cost is better than before, update of Equation ( 6) in the code generator Gaalop [START_REF] Charrier | Geometric algebra enhanced precompiler for C++, OpenCL and Mathematica's OpenCLLink[END_REF] results in more arithmetic operations than in the code generated from Equation (7) arithmetic operations. Note that we consider full multivectors for the three multivectors that appear in the expression.

Algorithm 4: Evaluation of the product A 1 A 2 • • • A n using the optimal parenthesising.

1 Function ComputeProduct Input: A1, • • • , An: chain of general multivectors, S: optimal 2D parenthesising index table i, j: resp. indices of the start and end of the sub-expression : the considered associative product Output: result of the product.

Conclusion

In this paper, we focused on products of more than two multivectors and addressed that there exists an optimal order in the evaluation of an expression. Then, we gave a dynamic programming algorithm that yields the optimal product order in polynomial time. The benefits of this approach arise from the product of three multivectors.

Algorithm 1 : 2 k

 12 Number of arithmetic operations required for outer product and geometric product of two general multivectors 1 Function P ∧ (KA, KB) Input: KA: set of grades for the multivector A KB: set of grades for the multivector B Output: total number of arithmetic operations resulting from A ∧ B 2 return A ∈K A k B ∈K B d ka + k b ka + k b ka 3 Function P * (KA, KB) Input: KA: set of grades for the multivector A KB: set of grades for the multivector B Output: total number of arithmetic operations resulting from A * B 4 return 2

1 2 KC = ∅ 3 foreach ka ∈ KA do 4 foreach k b ∈ KB do 5 if ka + k b ≤ d then 6 KC 8 KC = ∅ 9 foreach

 2345689 Function K ∧ (KA, KB) Input: KA: set of grades for the multivector A KB: set of grades for the multivector B Output: set of grades KC of the result of A ∧ B = KC ∪ (ka + k b ) 7 Function K * (KA, KB) Input: KA: set of grades for the multivector A KB: set of grades for the multivector B Output: set of grades KC of the result of A * B ka ∈ KA do 10 foreach k b ∈ KB do

23

  First call: S =OptimalParenthesising( A1, • • • , An, )

2 if i=j then 3 return 4 s 5 A 6 B

 3456 Ai = Si,j // left side recursive call = ComputeProduct(A1, • • • , An, S, i, s, ) // right side recursive call = ComputeProduct(A1, • • • , An, S, s + 1, j, ) // do the product 7 return A B 8 First call: Result = ComputeProduct(A1, • • • , An, S, 1, n, )

Algorithm 3: Computation of the optimal parenthesising of a geometric algebra associative product.

1 Function OptimalParenthesising Input: A1, • • • , An: chain of general multivectors. : the considered associative product. Output: Si,j: 2D optimal parenthesising index table. // define a 2D cost table