Implement finite algebras

[sagetrac-johanbosman]

Implementation of finite algebras over fields. A finite algebra A is simply given by means of a basis and for each basis element e a matrix that describes (right) multiplication of A by e.

The basic set-up is for algebras that are not necessarily unitary, commutative, or associative. Only algebras that satisfy all these conditions are fully supported.

CC: @koffie

Component: algebra

Keywords: sd51

Author: Johan Bosman, Peter Bruin, Michiel Kosters, Travis Scrimshaw

Branch/Commit: b629254

Reviewer: Travis Scrimshaw, Peter Bruin

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

[sagetrac-johanbosman]

Changed keywords from none to sd35

[sagetrac-johanbosman]

comment:2

Attachment: 12141_basic_setup.patch.gz

Lots of things to do still:

• Properly put it in a Category.
• Implement ideals and morphisms.

[sagetrac-mkosters]

Attachment: 12141_2_basic_setup.patch.gz

Added an associativity check.

[sagetrac-johanbosman]

Attachment: 12141_improve_repr.patch.gz

[sagetrac-mkosters]

Many new functions

[sagetrac-johanbosman]

Attachment: 12141_4.patch.gz

[sagetrac-johanbosman]

comment:3

Attachment: 12141_improve_associativity.patch.gz

I've uploaded an improvement of the associativity check, but it does need further improvement.

[sagetrac-johanbosman]

Dependencies: #11068

[sagetrac-johanbosman]

comment:4

Attachment: 12141_fix_random_docstring.patch.gz

[sagetrac-johanbosman]

Don't apply this yet; it contains bugs, but I messed up my hg.

[sagetrac-johanbosman]

Attachment: 12141_ideal_bla.patch.gz

Attachment: 12141_ideal_blabla.patch.gz

Now both ideal patches can be applied, together with #11068

[sagetrac-johanbosman]

comment:5

Basic ideal stuff has also been uploaded now. Still to add: more doctests and support for sidedness in the non-commutative case.

[sagetrac-mkosters]

Adds some functionality. Apply 12141, improve_ass and fix_random...

[sagetrac-mkosters]

comment:6

Attachment: 12141_zero.patch.gz

In the new patch you can check if an element is a zero divisor, do a base change and check if an element is nilpotent (it also fixes the power function if there is no one etc).

@Johanbosman: Can you merge the files? Is my nilpotent check the easiest one?

[sagetrac-johanbosman]

Contains #11068 and all its dependencies, for convenience

[sagetrac-johanbosman]

Attachment: 11068_combined.patch.gz

Attachment: 12141.2.patch.gz

Replaces all previous patches on this ticket

[sagetrac-johanbosman]

comment:7

Replying to @sagetrac-mkosters:

In the new patch you can check if an element is a zero divisor, do a base change and check if an element is nilpotent (it also fixes the power function if there is no one etc).

@Johanbosman: Can you merge the files? Is my nilpotent check the easiest one?

I've uploaded a combined patch. A few remarks about documentation:

• Please be more precise: Is your inverse a left or right inverse? Same question about zero divisors, etc.
• In the first line of a docstring, put the verb in the imperative (not extremely important, but more direct and grammatically better than "Returns blabla" without a subject).
• Put a blank line between the double colon and the doctests (used for html generation of documentation).

[sagetrac-johanbosman]

Attachment: 12141.patch.gz

replaces all previous patches

[a-andre]

comment:8

Could you change

raise *Error, "..."

to

raise *Error("...")

so we don't have to do it when switching to Python 3.

[pjbruin]

based on 5.10.rc2; revised most of the code

[pjbruin]

Changed keywords from sd35 to none

[pjbruin]

Changed dependencies from #11068 to none

[pjbruin]

comment:9

Attachment: trac_12141_finite_algebras.patch.gz

To be done: morphisms, more things related to ideals

[pjbruin]

Author: Johan Bosman, Peter Bruin, Michiel Kosters

[pjbruin]

Commit: ac731d2

[pjbruin]

Branch: u/pbruin/12141-FiniteAlgebra

[tscrim]

comment:21

Okay, I've done a review and it looks good overall. However when running some of the test suites, I realized that the morphisms weren't setup like the others in Sage, so I've reworked them in my review. It's not perfect, but IMO morphisms in general need some work. Other than that, it's some documentation and minor code tweaks. If you're happy with my changes, then it's a positive review.

---

New commits:

baa9c86	Merge branch 'u/pbruin/12141-FiniteAlgebra' of trac.sagemath.org:sage into public/algebras/finite_algebra-12141
9052b7c	Partial work on refactoring morphisms.
809ab1a	Merge branch 'develop' into public/algebras/finite_algebra-12141
c089db1	Merge branch 'develop' of trac.sagemath.org:sage into public/algebras/finite_algebra-12141
71f53cf	Finished implementing homsets for finite algebras.

[tscrim]

Changed commit from ac731d2 to 71f53cf

[tscrim]

Changed branch from u/pbruin/12141-FiniteAlgebra to public/algebras/finite_algebras-12141

[jhpalmieri]

comment:22

I think that the phrase "finite algebra" is possibly ambiguous. For example, there is a book Structure of Finite Algebras by Hobby and McKenzie in which a finite algebra is actually finite as a set. Maybe "finite-dimensional algebra" would be better in your situation.

[sagetrac-git]

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

f5debe1	Merge branch 'develop' into public/algebras/finite_algebras-12141
42e2f4e	Changed finite algebras to finite dimensional algebras.

[sagetrac-git]

Changed commit from 71f53cf to 42e2f4e

[tscrim]

comment:24

Good point. Done.

[pjbruin]

comment:25

Hi Travis,

Okay, I've done a review and it looks good overall. However when running some of the test suites, I realized that the morphisms weren't setup like the others in Sage, so I've reworked them in my review. It's not perfect, but IMO morphisms in general need some work. Other than that, it's some documentation and minor code tweaks. If you're happy with my changes, then it's a positive review.

Thanks for looking at this. To me, changing "finite" to "finite-dimensional" is OK; in commutative algebra and algebraic geometry it is very common to say "finite A-algebra" for an algebra that is finitely generated as an A-module, but in a general setting like Sage, it is possibly ambiguous. Since the base ring is (at least currently) always a field, "finite-dimensional" is an acceptable way of clarifying this.

I haven't had the time to review your changes in detail, but here are a few things I noticed:

• you changed "EXAMPLE::" to "EXAMPLES::" in many places where there is only one example; do you have a reason for this?
• I think it should be "finite-dimensional algebra", not "finite dimensional algebra", since "finite-dimensional" is used as a single adjective.
• Are you sure that the inverse of an element should be cached? This looks like it could waste a lot of memory. My impression is that in general only properties of parents should be cached. If any inverse should be cached at all, why not just that of the underlying matrix?

[tscrim]

comment:26

Hey Peter,

Replying to @pjbruin:

I haven't had the time to review your changes in detail, but here are a few things I noticed:

• you changed "EXAMPLE::" to "EXAMPLES::" in many places where there is only one example; do you have a reason for this?

As I understand it, EXAMPLES:: (and TESTS::) is the standard idiom, not the singular version even if there is only one such example. Although I seem to have missed some that I should also change to be consistent, unless you feel that I should change them back (I don't hold a strong opinion on this).

• I think it should be "finite-dimensional algebra", not "finite dimensional algebra", since "finite-dimensional" is used as a single adjective.

Will change.

• Are you sure that the inverse of an element should be cached? This looks like it could waste a lot of memory. My impression is that in general only properties of parents should be cached. If any inverse should be cached at all, why not just that of the underlying matrix?

It depends. Things that are very memory/computationally intensive to compute but not to store are candidates for a cache, especially when it's likely to be a bottleneck.

Also it's not using much more memory by caching the element as opposed to the matrix (nor does it generate a memory leak). So let's say x^-1 = y, then x has y stored in its cache. So once you delete x, you also delete the cache containing y. Perhaps what we should do is have a @lazy_attribute called _inverse which will point to y, and then if we construct x^-1, we can set y._inverse = x.

The other option if you're worried about memory usage is to make it a @weak_cached_function, which allows it to be garbage collected if there is no strong reference to x^-1 and memory is needed elsewhere.

[sagetrac-git]

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

6dd9dd6

Changed inverses, doc, and arith return type.

[sagetrac-git]

Changed commit from 42e2f4e to 6dd9dd6

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:28

I've changed the inverses to use the @lazy_attribute and so y._inverse is automatically set when calling x._inverse. Everything is now EXAMPLES:: and "finite-dimensional".

[pjbruin]

comment:29

Replying to @tscrim:

I've changed the inverses to use the @lazy_attribute and so y._inverse is automatically set when calling x._inverse. Everything is now EXAMPLES:: and "finite-dimensional".

Actually I had forgotten that the inverse was already cached in the first place thanks to _inverse... Anyway, I do like your idea of using @lazy_attribute for this.

As for EXAMPLE[S] and TEST[S], it is true that the documentation only mentions the plural and this is used predominantly in the Sage library, but I don't see any reason for preferring the plural regardless of the actual number of examples/tests. I don't feel too strongly about it either, but in general I wouldn't recommend to a reviewer to make such changes when it comes to matters of taste. (Although this only applies here if EXAMPLE[S] is indeed a matter of taste.)

I will try to do a final check soon, unless someone else does it first.

[sagetrac-git]

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

b629254

Merge branch 'develop' into public/algebras/finite_algebras-12141

[sagetrac-git]

Changed commit from 6dd9dd6 to b629254

[pjbruin]

comment:31

OK, I'm happy with the state of this ticket. All test pass; I also ran some existing external code that uses this ticket and it still works fine after the various changes that were made here.

[pjbruin]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Peter Bruin

[pjbruin]

Changed author from Johan Bosman, Peter Bruin, Michiel Kosters to Johan Bosman, Peter Bruin, Michiel Kosters, Travis Scrimshaw

[vbraun]

Changed branch from public/algebras/finite_algebras-12141 to b629254