Geometric Algebra in Swift?

(the dot is indeed irrelevant. I needed to retype it here since it froze)

I guess the problem is not unique to GA. I also tried to put e* as computed property, so that I can do 1.e1, but alas, the type checker refuses to see it as anything but (1 as Int).e1 :disappointed:.

And the problem is just as you showed. Unless I break it at almost every operator, it won't work properly.

I could reupload it again as swift package by the end of the (my) day. Dumping PG directly is a bad idea.


Also, •⌋⌊∧ are valid Swift operators, so, yay! (though I don't know how to feel about using non-ascii text)

1 Like

More like Swift really needs fixing these.

2 Likes

No worries, it will be interesting to see what you come up with! (Just a gist would be fine with me.)

As previously mentioned I realized that I most probably don't have the time / current skills to attempt an implementation myself, as it would have to be as efficient as doing it "the regular way" to be worth it for my use case.

Hi,

I'm the author of the ganja.js library in the original post, and the lecturer of the Siggraph 2019 course linked.

Happy to discuss implementation challenges for swift, feel free to contact me if you're up to the challenge. On the points raised above, a few thoughts:

For people that have a strong background in linear algebra, there is a point in the GA learning curve where you start to get proficient at converting standard vector/matrix applications to their geometric algebra equivalents. At this point the risk is to conclude that yes indeed it is possible to do 'the same thing', and this other, more elegant, language ends up producing hopefully the same or similar machine code. And you might think... but I already knew how to do this ;). While being able to convert between these formalisms is an important milestone it is actually only the starting point of exploring what GA has to bring. Existing algorithms by definition do not count on things like the invertibility of (k-)vectors, a linearized motion manifold, availability of closed-form exponential and logarithm functions, etc... and it is truly an open research question which treasures are still hiding.

As for GA libraries, meeting the requirements of giving a coordinate-free high-level mathematical language to programmers, while simultaneously producing optimized and streamlined code is challenging. One option, as suggested above, is to pick a single algebra, work out its types and produce a single optimized library for it. The best example is Jeremy Ong's Klein library (for c++), an SSE 4.2 production-ready library implementing 3D PGA. The other path, a GA library that works for any dimensionality and metric will depend heavily on compile-time features (and I'm not familiar with what swift has to offer). As an example of what is possible with modern C++, take a look at Jeremy's other library (in pre-alpha) : GAL.

Looking forward to seeing what the Swift community comes up with :+1:

3 Likes

Thank you for your feedback, most appreciated and interesting!

Me to, it seems like a really exciting challenge!


Here's a list of the implementations/libraries mentioned in this thread so far.

ganja.js

Versor

A GA library written in the language Scopes

Klein

GAL


And a list of videos/talks/presentations.

Already mentioned upthread:

Siggraph2019 Geometric Algebra

Generic programming of Generic Spaces: Compile-Time Geometric Algebra with C++11

Not previously mentioned:

An interview with Joan Lasenby

A short presentation of The power of Geometric Algebra Computing for Mathematica.

Thanks for the feedback!

It doesn't help that I don't see/use a lot of them either :disappointed:. Though I think constexpr could be very helpful should Swift have one right now.

PS.
The code dump is updated. It is obviously not optimised (yet) and I have only basic part (which is already where it blows up). If anything I want to first explore the syntax that wouldn't be detrimental to compiler.

1 Like

@Jens My bad then I just totally misunderstood what you're trying to achieve.

For anyone, like me, with little to no actual intuition of a lot of things related to ...well math, the following is by far the best introduction to the subject of GA (and more) that I have seen:

Reading those articles made so many things click for me. I feel like I've finally actually understood a lot of stuff that I thought I had understood for decades. I wish my math education had been more like that (ie 20-30 years ago, perhaps it is nowadays?).

1 Like

I've implemented some geometric algebra in Swift (too ugly to share :-)), and I really liked it. But I didn't need it to be fast, so I could just use a naive implementation (and it was REALLY slow).

In the end I think what is needed is a DSL for GA, and Swift is getting better at doing DSLs. The DSL would generate an intermediate format (in a very generic way this could be done with something similar to my FirstOrderDeepEmbedding package. From there optimised code for Accelerate and or Metal could be generated.

As for resources for GA, I found the book Linear and Geometric Algebra great for an elementary treatment of GA. Ideally you would read this after having been exposed to the wow-factor of GA somewhere else.

3 Likes

Just read through that blog post. There is a bit of, uh…hyperbole, and some of the author's philosophical musings mixed in, but it does explain some genuinely subtle points and interpretations in accessible language, so that's pretty cool. :slightly_smiling_face:

This video series from Alan Macdonald (author of the Linear and Geometric Algebra book mentioned above) is another resource worth checking out.

2 Likes

Agreed :slight_smile: I can also recommend:
Geometric Algebra for Computer Graphics SIGGRAPH 2019

I wonder if Swift's type system is powerful enough to be (mis)used in order to implement for example the 2D projective geometric algebra R*(2,0,1) (with e02 = 0 and e12 = e22 = 1) so that there are types

  • Scalar
  • E0, E1, E2
  • E01, E02, E12
  • E012
    (These could be typealiases for some recursive generic type constructs.)

and that eg the product of

  • an E0 and an E0 is of type Scalar  (e0*e0 = 0)
  • an E1 and an E1 is of type Scalar  (e1*e1 = 1)
  • an E2 and an E2 is of type Scalar  (e2*e2 = 1)
  • an E0 and an E2 is of type E02  (e0*e2 = e02)
  • an E1 and an E0 is of type E01  (e1*e0 = -e0*e1 = -e01)
  • an E2, E0 and an E1 is of type E012  (e2*e0*e1 = -e0*e2*e1 = e0*e1*e2 = e012)
  • an E2 and an E02 is of type E0  (e2*e02 = e2*e0*e2 = -e2*e2*e0 = -(1)*e0 = -e0)

That is, is it possible to encode the rules of the algebra at the type level, without resorting to hard coding everything / code generation?

I guess it might be intentionally impossible in Swift / require the type system to be Turing complete or something?

I've been trying in that direction. The problem I have currently is the lack of type-level condition. That is, you can't do this:

struct Vector<A> {
#if A.Next != Never
  var Vector<A.Next>
#endif
}

It is quite a problem constructing appropriate recursive formula since I need to terminate the recursion somehow.

In the end, I settled with multiple types:

protocol Bases {
  associatedtype Storage
}
struct Vector<Bases> {
  var value: Bases.Storage
}

enum Bases1<...>: Bases {
  typealias Storage = Void
}
enum Bases2<...>: Bases {
  typealias Storage = Vector<Base1>
}
...

Maybe I need to practice more type-fu. :face_with_monocle:

1 Like

Looks like you folks are trying to re-invent C++ templates and meta-programming via the type system.

No need for Turing completeness, dependent types would be enough I think :wink:

3 Likes

More-or-less. If Swift has anything of sort, it'd be much easier, but I think going all the way to Turing Complete like C++ would be overkill (not exactly sure, haven't deeply thought about it yet).

It doesn't help with the fact the encoding k-vector is most compact by tracking 2 variables. So now I have n^2 types...

There's a danger here that with Turing completeness you can express recursion and infinite loops, which is exactly what you'd like to avoid in a type-system (at least if you don't want running into infinite loops while type-checking). I think it would make more sense to prototype this algebra in languages like Agda or Idris and then translate that into Swift, which would directly point to type system features that Swift lacks. At least type classes in Idris can be mapped to Swift protocols more easily than C++ templates. It could also make it more clear how dependent types could be implemented in Swift (or on top of Swift in a separate meta-language maybe?), while keeping them practical enough for general use.

2 Likes

@enkimute (or anyone else who can answer this):
In bivector.net/tools, if we set:
positive: 2
negative: 0
zero: 1

I noticed that the Cayley table says e20 instead of e02. Is there a reason for this or is it a bug?

Hi Jens,

There is a reason. First off both e02 and e20 are valid choices (whose coefficients would have opposite signs).

For 2D and 3D PGA one picks these specific sets of basis vectors to unlock some additional benefits .. better alignment with existing conventions (like Plucker coordinates) is one advantage, another is the simplification of the dualization procedure.

In 2DPGA, picking e20 over e02 means taking the dual becomes a simple reversal of coefficients. If you pick e02 instead you have an extra sign-swap to perform when dualizing. (you can tell in the Cayley table because all of the elements on the anti-diagonal have the same sign).

Hope that helps.

2 Likes

I have done some naive implementation of Geometric Algebra recently. Based on the video lectures presented Geometric Algebra, First Course, in STEMCstudio - YouTube

Here is my current implementation.

https://github.com/Santhosh-KS/GeometricAlgebra/blob/main/LibGeometricAlgebra/GeometricVector.swift

Planning to redo the same with Functional programming approach, by choosing a different data type.

1 Like