Hello there, I’m trying to wrap my head around PGA by doing my own stupid implementation. When I look at the Cayley table, there is a specific order given to the bases. e.g. for 3d PGA it is:
As I understand it, this ordering doesn’t really matter for defining multiplication. However, if I look at the C++ code where the Poincare duality operator is defined, then the ordering appears to be important - if I had decided to swap the order of e31 and e23 (or maybe if I chose to use e13 instead of e31?) then it seems like I would get different behaviour.
I’ve looked up the Poincare duality operator on wikipedia, and I would need to do significant reading to understand all the words in the first sentence (I understand “basic result”…).
If you are using bitfields, the lexicographic ordering (ascending indices) is certainly easier to work with. There is, however, an advantage to using the cyclic ordering if you aren’t using bitfields for your encoding. I found that when working on Klein (representation linked), the cyclic ordering eliminated many sign changes and made the computation much more efficient as a result. The lexicographic (aka “natural”) ordering creates certain asymmetries when performing operations that, in my case, would have cause different SIMD lanes to have different signs which would have required more instructions to correct. I suspect code relying on bitfields should likely prefer a cyclic ordering as well, but this requires a great deal of effort and you are already sacrificing some performance anyways when encoding this way.
As for the J map (Poincare dual map), there was a great discussion on here a while ago here. I’ve linked to the direct post where @cgunn3 makes an amendment to the J map defined from his thesis. Originally, the map takes an element to its right complement such that the product of the two elements is an even permutation of I. However, as pointed out in the linked post, the sign flip of the co-basis element isn’t possible when defined this way if the input of the map has grade n - 1.
The regressive product is actually next up on my list of things I need to implement in SSE so when that’s done I will circle back here to link the implementation.
It may be more helpful to think about the properties of the map more than the original definition. J is a bijection from the algebra to itself so all elements are mapped one-to-one and onto (aka, an “automorphism”). Also, J is grade-reversing, so in a sense, maps a “space” to its complement. A second application of J needs to produce the original element. An \vee operation (join), defined as the \wedge (meet) of the space complements is therefore a grade-increasing operation, as opposed to a grade-decreasing operation in projective space. The purpose of the map (in the context of PGA) is to provide such a grade-increasing regressive product as a sister operation without needing to change the underlying algebraic structure. That is, we didn’t have to redefine the geometric product, exterior product, or any of the basis elements to gain the capability to, say, join points together in a line.
If you are using bitfields, the lexicographic ordering (ascending indices) is certainly easier to work with. There is, however, an advantage to using the cyclic ordering if you aren’t using bitfields for your encoding.
That is a good start for me - I didn’t know even that the name of this ordering was “cyclic ordering”. Scanning through the wikipedia page, I’m still not entirely sure how to use it to come up with the table ordering of the basis vectors.
It may be more helpful to think about the properties of the map more than the original definition. J is a bijection from the algebra to itself so all elements are mapped one-to-one and onto (aka, an “automorphism”). Also, J is grade-reversing, so in a sense, maps a “space” to its complement. A second application of J needs to produce the original element.
So does any map that meets these criteria do the job?
e.g. For R(2,0,1), I need to swap my “1” with my “e012”, but I could chose:
e0 ↔ e12
e1 ↔ e02
e2 ↔ e01
And that would work just as well as chosing:
e0 ↔ e02
e1 ↔ e01
e2 ↔ e12
(assuming that I’m consistent)?
Ah right of course I forget to mention that the other property is that an element and its dual must have a product equal to \pm I (pseudoscalar) and that two applications of the dual map is the identity map. Elements in PGA are generally equivalent projectively up to a constant scale with the exception of cases where the weight matters (rotors, translators, motors).
Thanks again. So then if I’m reading this right, I could have:
1 <-> e012
e0 <-> e12
e1 <-> e02
e2 <-> e01
OR
1 <-> e012
e0 <-> e21 <<— this is the only difference - I’ve changed it from e12 to e21
e1 <-> e02
e2 <-> e01
Does that sound right?
Back on the ordering question. I looked at the ganja.js source code to see if I could figure out how this ordering is defined. Unfortunately this is what I found:
// Unless specified, generate a full set of Clifford basis names. We generate them as an array of strings by starting
// from numbers in binary representation and changing the set bits into their relative position.
// Basis names are ordered first per grade, then lexically (not cyclic!).
// For 10 or more dimensions all names will be double digits ! 1e01 instead of 1e1 ..
So I then wondered how this lined up when the ordering used in the output files is different, and I found:
// The basis used in the Siggraph course notes.
var basis = "1,e0,e1,e2,e3,e01,e02,e03,e12,e31,e23,e021,e013,e032,e123,e0123".split(",");
where s is based on signature. If you think that applying it twice is an identity map, you are incorrect.
As I explained many times, the best and most straight forward definition is the following: \star\omega = \tilde\omega I, which is simply the reverse element times the pseudoscalar with the geometric product.
OP is talking about PGA, and we can make a choice for J such that J^2 = id.
Yes and you get the same response in the context of PGA :). The dual you use is fine in many contexts, but not when you need a map that is metric-independent.
In your formula, \widetilde{\omega}I for \widetilde{\omega} = e_0 is exactly 0 given the choice of metric in PGA. You’re free to not use this metric for your own applications of course, but that is not the topic of discussion.
Even if you used the non-metric map, it is incorrect to say that applying it twice is an identity. The factor of (-1)^{k(n-k)} is metric independent, only depends on grade.
Thank you for clarifying. The coordinate map I’m referring to pertains specifically to the cyclic basis mentioned by OP for 3D projective geometry. I actually haven’t verified it in other dimensions but I can’t imagine it not to work (number of elements is a power of 2). The basis must be cyclic for it to work, but the coordinate “reversal” is a trivial automorphism with order 2. Is there something I’m missing?
Regardless of what basis ordering you use, the reversion will change the sign of the element (by reversing the indices). Also, reversal is actually an antiautomorphism.
OK I think we’re a little lost. When I say “coordinate reversal,” I’m not talking about the interchange of indices on the basis element (the reversion operator). I’m talking literally about mapping e_0 to e_{0123}, e_1 to e_{021}, e_2 to e_{013}, etc. This is the dual map that is trivially the identity after two applications and has all the properties needed to create the regressive product in the same algebra. Note that the parity term you referred to earlier is baked into the cyclic nature of the basis elements.
No, it’s not baked in there. It only takes care of the sign in one direction, you would get (-1)^k(-1)^k then instead of (-1)^k(-1)^{n-k}, and so you’d be off by a factor of (-1)^k(-1)^{n-k} either way. It doesn’t matter if you use a different ordering there, because you’ll still have grade reversal to deal with.
You aren’t using the correct definition, but if you don’t care about being mathematically correct, that’s fine.
We are talking past each other because you have assumed an incorrect proposition: you assume that the complement map is an involution, and this is false. Therefore, everything else based on that idea will not be fully compatible with e.g. discrete exterior calculus.
In PGA, mutliplication with the pseudo-scalar is non-invertible. So how can this definition be used for the duality ? The entire point of the J map is that it is a trivial isomorphism on the geometry in both algebras. (i.e. swapping a point in the algebra for the same point in the dual algebra, same for lines and planes). And so yes, the J map is indeed an involution. (the right complement is not.)
So when the J map is used - there is no complement at all.
Furthermore, if you use that as definition of duality, it is metric dependent (as it uses the geometric product) - the very definition of duality
a\wedge b = (a^* \wedge b^*)^{-*}
implies it is a non-metric operation. (the left side is the outer product, non metric, the thing in the middle is an equal sign).
You’ll either have to read that again, or explain it again - and just a small hint - when you find yourself explaining something twenty times … maybe you need another approach?
@enki it seems you are not really familiar with my arguments either: you can use a non-metric version of Hodge complement (I prefer the ! symbol instead of J). Nevertheless, the factor of (-1)^{k(n-k)} is unrelated to the metric of the algebra. Hence, whether you used the metric or non-metric version doesn’t change it. Also, changing basis ordering doesn’t affect that factor either.
You seem to be completely missing the point. There is no complement being used here whatsoever. The map we are after, which we use solely to define the regressive product, has only one (geometric, not algebraic) requirement :
it must map ‘points on a line’ to ‘lines through a point’ (in 2D)
The J map is the simpelest, trivial map that does that. It has no sign swaps anywhere and it uses no complements. It is an involution and is the most efficient way to define the regressive product.
Basis order and metric are completely irrelevant - you can add factors as much as you like, you’d only be correct if you take them back out in the very next instruction after the outer product.
(since we apply J, do one outer product and apply the inverse of J (which is J again, its an involution)) to define the regressive product:
a \vee b = J^{-1}(J(a) \wedge J(b))
Unrelated to the definition of the regressive product, you say
As I explained many times, the best and most straight forward definition is the following: \star\omega = \tilde\omega I, which is simply the reverse element times the pseudoscalar with the geometric product.
This clearly is wrong when there is a degenerate metric. i.e. that map clearly is not an anti-involution. For proof calculate, in \mathbb R_{2,0,1}, the double application of your map on e_{01} where e_0^2 = 0 and e_1^2 = 1 :
“simply the reverse times the pseudoscalar” : \tilde e_{01} e_{012} = e_{10} e_{012} = 0
This is why people keep ‘ignoring’ your definition in PGA. (Hope that helps cause I’m tired of hearing how many times you’ve explained it - when I’ve never seen you explain it).
Hi all, thanks for all your help. I’m afraid that most of what you are talking about is above my head.
My simple minded view is that I can implement “dual” by reversing the order of my coefficients, so the one which applied to “1” now applies to “e0123” and vice versa.
If I choose the wrong order of basis vectors, then this won’t work.
What isn’t clear to me is:
How is the order “1”,“e0”,“e1”,“e2”,“e3”,“e01”,“e02”,“e03”,“e12”,“e31”,“e23”,“e021”,“e013”,“e032”,“e123”,“e0123” determined?
(bonus credit, I think if I understand (1) then I’m happy enough): Are there other orderings which can work with the “reverse the coefficients for dual” approach?
Just trying to follow along with the discussion, can I check my assumptions? (hopefully this communicates my level of ignorance…):
The “pseudoscalar” in PGA3D is e0123
The “grade” of “1” is 0, the grade of “e0” is 1, the grade of “e01” is 2, the grade of “e012” is 3, and the grade of “1+e0+e01+e012” is also 3.
The “dual map” is the same as the “Poincare dual”
“Complement” is negating some subset of the coefficients (all but the one applying to “1”?)
@enki, your definition used is actually incorrect for defining the regressive product, there are several mistakes in your approach.
The one and true original definition from Hermann Grassmann is what I use, which is described in John Browne’s book and also discussed by Hodge, DeRahm, and used in differential geometry for deriving the chain co/homology theories… which you will all get incorrect with your definitions.
The extra factor included in the double application of the complement is not there by accident. It is deliberate and it has been used from the start by Grassmann, Hodge, and DeRahm, and many others.
You are basically ignoring the original definitions used by these people for differential geometry.
The correct definition for Grassmann algebra is the one I described, it is also used to define the regressive product, as explained in John Browne’s Grassmann algebra book. There is no need for me to elaborate on it further, since it is already well known in the literature and was used from the start.
If you keep assuming that this map needs to be an involution (to make things “simpler”), then you are actually disabling yourself from using it for differential geometry and Hodge-DeRahm co/homology.
There is a non-metric version of this definition which I associate to the symbol ! --yet you keep repeating the same thing… and you are literally ignoring the things I said, no wonder you don’t understand.
Anyway, the only difference between the ! and the J map is that a double application of ! will always give you that factor (-1)^{k(n-k)}, which is absolutely essential for differential geometry. If you don’t want to do differential geometry and do things incorrectly, that’s fine… I’m just worried that you will be teaching this and giving people definitions that aren’t compatible with OG (Original Grassmann).
Great question @thenewandy! The key is to think about “cycles,” hence the name “cyclic basis.” For the elements of grade 0 and grade 1, there is no reasonable “ordering” since they consist of either no indices or a single index. In space, the vectors e_0, e_1, e_2, and e_3 can be thought of as vectors that terminate at four points of a tetrahedron.
In this view, edges of this tetrahedron can be mapped to the bivector basis elements by considering the start and end vertex. This is also consistent with the viewpoint of bivectors as “oriented areas.” After all e_{12} should be opposite e_{21} in sign, and on this tetrahedron (which we are using as a representation of our basis elements), edges can be oriented as well.
Starting from vertex 0, there’s no reason to consider it as anything other than the “starting vertex,” so let’s start with 3 elements e_{01}, e_{02} and e_{03} emanating from e_0. Here’s a sketch I made of what this looks like so far:
Now, if we move to the next point at e_1, we see that we already have an edge from e_0 terminating here which is our now “official” basis element e_{01}. But now we have a choice. Should I connect e_1 to e_2 to make e_{12}? Should I connect it to e_{13}? Both? To decide best how to label it, I should explain the whole point of the tetrahedron in the first place. For each vertex of the tetrahedron, I can map it uniquely (and bijectively) to the opposite face of the tetrahedron. That face is associated with 3 vertices, which is… a trivector! To figure out the index order, we can start from any vertex of that opposite face, and list the other two indices in order by following the edges. Similarly, for each edge in the tetrahedron, there is a unique “opposite” edge that doesn’t share any vertices, which uniquely maps bivectors to bivectors, and all these maps are reversible. This tetrahedron IS the manifestation of a dual map with all the properties that we want.
OK, so knowing that, this is where we can be more clever with how we arrange things. One thing we “want” is to arrange it so that e_0 has e_{123} as its dual. Notice that e_{123} is equivalent to e_{312} and e_{231} (see the cycle yet?). This means we need to select the edge directions of the (123) face of the tetrahedron to preserve this order. Starting from e_1 then, we’ll move to 2, and then 3 to define e_{12}, e_{23} and e_{31} respectively. I’ve amended my picture to show this:
One magical thing happened here. All the edges have been determined, which means that all the tetrahedron areas have been determined too! Let’s look at e_3 for example. We can see that the opposite face with the 0, 1, and 2 vertices has an unfortunate property that it doesn’t create a cycle. That is, starting from 0, I can go to 1, and then 2, but the edge from 2 to 0 is reversed. The remedy is to introduce a “flip” so that we have a cycle in our mapping. Thus e_{021} (equivalent to -e_{012}) is part of our canonical basis. Note that it doesn’t matter if we try to traverse 0 \rightarrow 1 \rightarrow 2 and flip one edge, or traverse the opposite direction 0 \rightarrow 2 \rightarrow 1 and flip two edges. The result is the same since the latter traversal introduces two flips resulting in the same cycle (021). If we repeat this for the other faces, we get e_{013} and e_{032}.
What about the bivectors (edges)? It’s easy to verify that each one has a unique mapping to and from the opposite edge. For example, e_{02} there on the left has for its dual edge e_{31}. Similarly e_{31} maps back to e_{02}.
Now, we have a well-defined scheme that maps every basis element to its dual element and back. It is easy to see here that doing this map twice gets you to the same element, and because of the cyclic ordering, we need no sign changes to perform the mapping. There is some ambiguity in the “canonical” trivectors, but only because we are free, for a given trivector, to use instead a trivector with indices that are within an even permutation. Thus, we have the desired Poincare isomorphism we’ve been looking for.
Now, for your second question, are there alternative bases that could have worked (aside from swapping indices on the trivector)? My answer there is “yes.” Take all the edges above and swap the orientations. Done :). Alternatively, we can swap all the edges of the (123) face of the tetrahedron. You can see that in both cases, this tetrahedron still has all the properties of the map we need, and due to projective equivalence, all our computation will be unchanged. Other arrangements are possible of course!
I hope this helps (and I also hope that I didn’t make too many egregious errors in this somewhat rushed post).
