Rewrite Clifford and exterior algebras to have a basis indexed by integers

[tscrim]

Integers are a more compact way of representing subsets with their bits. This should both decrease the memory usage to store elements and the speed due to using bit operations and nearly trivial hashing.

Depends on #34035 Depends on #34084

CC: @tscrim @trevorkarn

Component: algebra

Keywords: gsoc2022 exterior algebra index integer

Author: Trevor K. Karn

Branch/Commit: 2637750

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/32369

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 847738b to 6dcb98e

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

2b75b2a	Fix bug with lifted bilinear form, a bug with zeros in module morphisms, and make a check more intuitive
f12b70c	Fix sign error
153ba07	Fix coboundary on basis
929f55b	Clean up code a bit
e70115a	Add doctest
328897d	All tests pass
8f34ece	Add doctest
326f72a	Fix merge error
296edb8	Add tests for index class
6dcb98e	PEP8 compliance

[trevorkarn]

comment:34

Merge issue seems to be fixed -- all tests pass.

[tscrim]

comment:36

This is faster for hashing and equality testing, which are two of the big things I wanted to speed up since the element implementation is using dicts:

sage: t = (1,3,6,7,9,13)
sage: X = FrozenBitset(t)
sage: X
01010011010001
sage: %timeit hash(t)
61.4 ns ± 1.09 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
sage: %timeit hash(X)
33.6 ns ± 0.354 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

sage: s = tuple(list(t))
sage: Y = FrozenBitset(s)
sage: s is t
False
sage: Y is X
False
sage: %timeit s == t
28.3 ns ± 0.381 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
sage: %timeit X == Y
20.2 ns ± 0.215 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

I made a number of small reviewer changes. If they are good with you, then this is a positive review.

---

New commits:

b6174b4	Merge branch 'u/tkarn/32369-exterior-rewrite-v2' of https://github.com/sagemath/sagetrac-mirror into public/algebras/exterior_algebra_index_set-32369
a325339	Doing some reviewer changes.

[tscrim]

Changed branch from u/tkarn/32369-exterior-rewrite-v2 to public/algebras/exterior_algebra_index_set-32369

[tscrim]

Changed commit from 6dcb98e to a325339

[tscrim]

Reviewer: Travis Scrimshaw

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

c01586d	Revert with_basis/morphism.py.
8b777a0	Fixing up doctests and some other compatibility issues.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a325339 to 8b777a0

[tscrim]

comment:38

This should now pass all the doctests. The indexing set should be a UniqueRepresentation, which fixes an issue with comparisons. I had to make a few tweaks to how elements were being constructed. I also made the E.basis().keys().an_element() behave as before.

Some simple timings for multiplication:

sage: E.<a,b,c,d> = ExteriorAlgebra(QQ)
sage: r = E.an_element(); r
b*c + 2*a + 3*b + 1
sage: %timeit r * r
10.9 µs ± 46.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: r = sum(E.basis())
sage: %timeit r * r
99 µs ± 438 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

sage: E = ExteriorAlgebra(QQ, 'x', 10)
sage: r = sum(E.basis())
sage: %timeit r * r
179 ms ± 939 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

versus before

11.1 µs ± 42.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops 
139 µs ± 271 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

931 ms ± 5.76 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

So we are seeing substantial gains when multiplying larger elements. With the Cythonization of #34138, this then becomes

8.05 µs ± 91.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
73.4 µs ± 631 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

129 ms ± 1.04 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Is it easy to run timings for these computations in M2?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8b777a0 to 2637750

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

2637750

Small doc tweak.

[trevorkarn]

comment:40

Replying to @tscrim:

Is it easy to run timings for these computations in M2?

Here you go:

i1 : E = QQ[a..d, SkewCommutative=>true]

o1 = E

o1 : PolynomialRing, 4 skew commutative variables

i2 : r = b*c + 2*a + 3*b + 1;

i3 : time r*r;
     -- used 0.000222222 seconds

i4 : r = sum(flatten(entries(basis E)));

i5 : r

o5 = a*b*c*d + a*b*c + a*b*d + a*c*d + b*c*d + a*b + a*c + b*c + a*d + b*d + c*d + a + b + c + d + 1

o5 : E

i6 : time r*r;
     -- used 0.00095186 seconds

i7 : E = QQ[x_1..x_10, SkewCommutative=>true]

o7 = E

o7 : PolynomialRing, 10 skew commutative variables

i8 : r = sum(flatten(entries(basis E)));

i9 : time r*r;
     -- used 0.315753 seconds

[trevorkarn]

comment:41

Your machine is better than mine, so I'm including the same timings on my machine so the comparison to M2 is more apples-to-apples.

sage: E.<a,b,c,d> = ExteriorAlgebra(QQ)
sage: r = E.an_element(); r
b*c + 2*a + 3*b + 1
sage: %timeit r * r
32.2 µs ± 2.49 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: r = sum(E.basis())
sage: %timeit r * r
274 µs ± 9.02 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

sage: E = ExteriorAlgebra(QQ, 'x', 10)
sage: r = sum(E.basis())
sage: %timeit r * r
514 ms ± 8.92 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

[tscrim]

comment:42

Interesting...Sage is faster on small examples but slower (almost 2x) on larger examples. I would have expected something far more uniform.

[tscrim]

comment:43

Patchbot is (morally) green. So if my review changes are good, then I think we are at a positive review.

[trevorkarn]

comment:44

Changes look good to me!

Replying to @tscrim:

Patchbot is (morally) green. So if my review changes are good, then I think we are at a positive review.

[vbraun]

Changed branch from public/algebras/exterior_algebra_index_set-32369 to 2637750