Evaluate the feasibility to reimplement galgebra in Julia
utensil opened this issue · 23 comments
From the discussion in JuliaSymbolics/Symbolics.jl#59 (comment) , we need to re-evaluate the feasibility to reimplement galgebra in Julia, given the latest progress by https://github.com/JuliaSymbolics/Symbolics.jl .
@abrombo @eric-wieser comments welcome.
After initial investigation of the source of https://github.com/JuliaSymbolics/SymbolicUtils.jl and the matrix implementation in https://github.com/JuliaSymbolics/Symbolics.jl (matrix product is a typical non-commutative operation), it seems quite feasible, actually.
To confirm such an evaluation, simply
- For non-comutivity and expression manipulations
- read https://symbolics.juliasymbolics.org/dev/manual/expression_manipulation/
- read https://symbolicutils.juliasymbolics.org/#term_rewriting
- check https://github.com/JuliaSymbolics/SymbolicUtils.jl/blob/master/src/rule.jl
- search
@rule,@acrule,@ordered_acrule,promote_rulein both repos
- For calculus
- For LaTeX printing
- search @latexrecipe in the repos
- read https://korsbo.github.io/Latexify.jl/stable/tutorials/notebooks/
then it's natural to draw a similar conclusion.
I've always wanted galgebra to have two layers of symbolic manipulation:
- handles metric and basis in GA, so it can find an optimal simplified form for efficient code generation
- handles multivectors directly in a basis-agnostic way
I would like metric and basis to be just metadata attached to multivactors symbols, so by default simplify use ruleset 2 and only use rulset 1 when called like simplify(mv; expand_basis) (they're temporarily substituted to their fully expanded form expressed in basis ), and every rule in ruleset 2 has automatically generated test cases or compile-time validations to verify with ruleset 1 .
In my opinion, of course Grassmann.jl should be used for the multivector basis, as it already does efficient code generation. The only missing feature is the fully general metric, which is the focus of the next and final 0.9 release before the v1.0 release is declared.
Grassmann.jl is actually what I have been learning from, but to learn means to re-interpret with what had been learned, and in the process, new tool might be created as a side-product 😉
And one strength of Grassmann.jl is that it's interoperable with many other libraries via some bridges you build, I intend to do something similar, so I do expect interoperability with Grassmann.jl.
Actually, Grassmann.jl feels more like a product than a library to built upon, and I aim for basis-agnostic by design, so interoperability and cross-verification should be the appropriate way.
Not sure what you mean by Grassmann.jl feeling like a product instead of a library, since I'm the developer I don't think like that about it. Grassmann.jl is meant to provide most of the basic foundation you need for geometric algebra plus ways of making it interoperable with other things. It is definitely intended to be a foundational building block from which other things get build on top of it. For example, I was hoping people would build some sort of additional syntax layers on top of it for the type of geometric algebra stuff people like to do.
What is it you would re-interpret differently? I certainly have a few things I will be redesigning for v0.9, which is the final breaking change before v1.0, I have been saving the final redesign for the fully general metric tensor and there are a few things which I need to redesign and make better for that.
I don't think it's wise to have so many separate geometric algebra packages, I get that everyone gets inspired by Grassmann.jl and they want to be like me and try at recreating something like it, but it's not the right way.
No offense, but I highly doubt other people are going to do a much better job of implementing a foundation for geometric algebra, the amount of effort I have put into refining it is not gong to be easily replicated and improved upon.
To me it is disappointing that instead of just building on the foundation I provided, everybody wants to try to copy me and re-invent the foundations instead of building something on top of it. I'm the one who's been designing geometric algebra from the ground up in the Julia language, while you all were busy doing whatever else. Now people want to suddenly turn around and try do the same thing I've been doing for years already, and instead of building together, it's always everybody for himself.
Actually nowadays I don't have enough time to work on GA, and GAlgebra.jl is more like my homework, it was my attempt to better verify galgebra in a more math-like syntax, and is my new hope for reviving galgebra by re-implement its backbones in Julia because I have always wanted to maintain galgebra but have difficulty to work with the original codebase to fix issues and merge patches to implement new features with the time I have.
It's also my new hope for a general metric, basis-agnostic, self-verifiable GA library supporting Physics-oriented Geometric Calculus that I've always wanted at the first sight of galgebra.
I'm not aware of any other GA library in Julia that is anywhere near Grassmann.jl or what I want . Lean & GA also led to a deeper rabbit hole than I was expecting although it's so wonderful to see @eric-wieser 's work on it.
In retrospect and after reviewing some code in Grassmann.jl , it seems that it's highly unlikely I'll do anything different or better than Grassmann.jl or SymbolicGA.jl for ruleset 2, so it's likely that ruleset 2 could be optionally based on Grassmann.jl, SymbolicGA.jl and galgebra. And ruleset 1 is the focus.
@chakravala Can you name a few libraries that are built upon Grassmann.jl ?
It seems that we can actually start from scratch using only https://github.com/JuliaSymbolics/Metatheory.jl following https://github.com/overshiki/SymbolicCircuit.jl .
For the Python version, it would be better to use the lately improved version of egg: egglog. It has a high-level Python binding https://github.com/metadsl/egglog-python and a higher DSL https://github.com/metadsl/metadsl . Just read their paper.
So there's no need to let the Python version to depend on the Julia version, as someone questioned why GAlgebra.jl depends on slow Python and suggested the other way around.
My evaluation of your ideas is that building on top of all these symbolic or whatever Julia packages as a foundation, you're going to end up building a not very efficient library because it uses a lot of dependencies. Part of the elegance of Grassmann.jl is that it is entirely self contained and doesn't depend on any outside things, which makes the package load extremely fast and light. It might be interesting to play around with all these other Julia packages, but using them as a foundation will probably be sluggish.
I know it's not going to be very efficient due to the fact it would rely on a rewrite system based on e-graph, its performance is not going to match natively curated symbolic simplification via meta-programming and such. But it's going to outperform GAlgebra for certain, and that's kind of the purpose here. GAlgebra has performance issue even for some small algebras like Spacetime, PGA2D, PGA3D, CGA2D, CGA3D, see the test cases marked slow in https://github.com/pygae/GAlgebra.jl/blob/master/test/runtests.jl
I've got a few more computer algebra surprises up my sleeve for Grassmann v0.9 and v1.0
People are welcome to contribute their thoughts here chakravala/Grassmann.jl#102
I think people who have looked have found one of the real slow downs in galgebra was scalar simplifications in sympy.
Also, realizing a multivector as a linear combination of non-commuting sympy symbols with scalar sympy symbolic coefficients is also not very efficient.
Yes, and I've been looking for a lightweight replacement of sympy to do the heavy lifting for ages, from MatchPy to egglog-python. I believe this would simplify the part involving metric and basis greatly, we can run the rewrites as much as possible and finally resort to sympy only for complicated materialization.
Additional areas cry out for parallelization which should be much easier in Julia.
If we're considering using MetaTheory.jl, it's worth noting that a lot of performance optimization is planned but not done yet, including parallelization: JuliaSymbolics/Metatheory.jl#7 except for JuliaSymbolics/Metatheory.jl#6 .
If it's acceptable to introduce a non-python dependency, egglog-python (the python binding to its rust core) can be considered, but it seems that no parallelization optimization is considered yet. I'll ask them about it.
So, it's theoretically very possible to do parallelization for symbolic manipulation and it should be easier to do so in Julia than Python, it seems there's not much of reference implementations yet.
I also failed to find it in Grassmann.jl, @chakravala , am I missing something?
I think the best part of galgebra was the user interface and the interface with LaTeX.
Yes, personally I love these parts very much. One of the kind.
I also found https://github.com/connorferster/handcalcs to be very interesting, it works with sympy, so it might also work with GAlgebra, it would be interesting to test the interplay between them. But I worry the hacks in GAlgebra would interfere somehow.
I also failed to find it in Grassmann.jl, @chakravala , am I missing something?
Do you mean you failed to figure out how to use parallelization with Grassmann.jl? With Grassmann.jl, I currently don't parallelize individual multivector algebraic operations, instead you would parallelize by working on several multivectors at once. For example, you could parallelize the computation of a bunch of geometric products using CUDA by just using a CUDA array of multivectors. Each individual multivector computation would not be parallelized, but you would compute several multivectors in parallel. So if you want to do parallelization, you need to think in terms of writing your own function that parallelizes things, because the basic algebraic operations are all single threaded, so that you can parallelize your own algorithm with those building blocks.
So currently, I don't necessarily think I'd want to be parallelizing a single multivector operation, but rather parallelize over several single threaded algebraic operations. Nobody has complained about it yet, until now.
So currently, I don't necessarily think I'd want to be parallelizing a single multivector operation, but rather parallelize over several single threaded algebraic operations. Nobody has complained about it yet, until now.
It's a valid use case if you think about a transformer implemented in GA, that has the size of n where n is the token context window like 100k, then this use case is as valid as the parallelization for a matrix.
But of course, in the context of this discussion, bromb needs it only because the symbolic manipulation is slow, even for a low dimensional GA with non-trivial metric. He's been wandering the possibility since a few years ago.
It may be possible for me to add a parallelization code generation option which gets triggered by particular symbolic operations when used in Grassmann, so I will keep that possibility in mind.
Is there a specific list of operations which are known to suffer from lack of parallelization in the past?
Also, I'm experimenting with developing my symbolic FieldAlgebra.jl structures, currently a Ring algebra, but have more plans
julia> using FieldAlgebra; @ring xyz x y z
julia> x*y^2
xy²
julia> ans/x
y²
julia> x+y^2
x + y²Let me know what you think about this ... it's intended to be lightweight symbolic algebra, probably not going to be fancy in terms of expression rewriting, but very lightweight and minimal for fast code generation. For the foundation of Grassmann I need a minimalist symbolic capability which isn't too feature heavy. You can still use other more advanced symbolic packages combined with Grassmann after it's been compiled, this basic symbolic algebra is for internal purposes, although it is general purpose.
FieldAlgebra can support simple arithmetic but as for GAlgebra, we need arbitrarily complicated expression in the metric, such as in https://nbviewer.org/github/pygae/galgebra/blob/master/examples/ipython/colored_christoffel_symbols.ipynb .
So the idea in this issue is to first use high-level GA rewrite rules, then use basis rewrite rules, and finally resort to SymPy or other full-fledged CAS to handle non-trivial metric . So that we could have maximum performance and minimal overhead.
FieldAlgebra will certainly be capable of more arbitrary expressions which use Field algebra, I am not done implementing it, so I'm not worried about that. However, FieldAlgebra will be much more minimal than the other symbolic packages mentioned, handling expressions like sin and tan are part of the plan of course, but again, it will be more minimal and lightweight.
Just noticed https://github.com/tBuLi/kingdon , a GA library with both numeric and symbolic support inspired by GAmphetamine.js . Geometric Algebra only, no Geometric Calculus. A potential efficient backend.
Maybe it's possible to do something similar to http://blog.ezyang.com/2020/09/lets-talk-about-the-pytorch-dispatcher/ for incorporating different backends.
If we're considering using MetaTheory.jl, it's worth noting that a lot of performance optimization is planned but not done yet, including parallelization: JuliaSymbolics/Metatheory.jl#7 except for JuliaSymbolics/Metatheory.jl#6 .
I'm currently working on improving Metatheory.jl performance. I have set up you can see that on this branch it's max 2.5 times faster than master. Please open any issue if you have any ideas and are still considering using it. Also, there's some developments and active discussion in TermInterface.jl