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

[trevorkarn]

Dependencies: # 33989

[trevorkarn]

Changed dependencies from # 33989 to #33989

[trevorkarn]

Commit: 3fd9f51

[trevorkarn]

Changed keywords from none to gsoc2022 exterior algebra index integer

[trevorkarn]

Branch: u/tkarn/32369-exterior-rewrite

[trevorkarn]

Author: Trevor K. Karn

[sagetrac-git]

Changed commit from 3fd9f51 to a64948c

[sagetrac-git]

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

a64948c

Rewrite multiplication to use bit-indexed sets

[trevorkarn]

Changed commit from a64948c to 5df9054

[trevorkarn]

New commits:

d4f3d86	Add FrozenBitset.__reversed__
353d588	Initial commit/minimal change
8b0bd3c	Fix .one_basis()
5df9054	Remove accidental print statement

[trevorkarn]

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

[trevorkarn]

Changed dependencies from #33989 to #34035

[sagetrac-git]

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

0ca83ab

Add _basis_index_function as a method, fix some doctests, and fix some type issues (tuple -> FrozenBitset)

[sagetrac-git]

Changed commit from 5df9054 to 0ca83ab

[sagetrac-git]

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

be97491

Fix multiplication

[sagetrac-git]

Changed commit from 0ca83ab to be97491

[sagetrac-git]

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

b1eca07	Fix repr sorting issue and add some small tests
62a4f39	First draft of basis iterator
120eb30	Second attempt at iterating

[sagetrac-git]

Changed commit from be97491 to 120eb30

[sagetrac-git]

Changed commit from 120eb30 to b462c27

[sagetrac-git]

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

b462c27

Add index class and first draft of exterior __mul__

[sagetrac-git]

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

6368c47

Fix some bugs and rewrite exterior multplication algorithm

[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

[sagetrac-git]

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.

[sagetrac-git]

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?

[sagetrac-git]

Changed commit from 8b777a0 to 2637750

[sagetrac-git]

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