Opened 8 years ago

Closed 6 years ago

#12141 closed enhancement (fixed)

Implement finite algebras

Reported by: johanbosman Owned by: AlexGhitza
Priority: major Milestone: sage-6.2
Component: algebra Keywords: sd51
Cc: mderickx Merged in:
Authors: Johan Bosman, Peter Bruin, Michiel Kosters, Travis Scrimshaw Reviewers: Travis Scrimshaw, Peter Bruin
Report Upstream: N/A Work issues:
Branch: b629254 (Commits) Commit: b629254871ad4c6240c2531266f5afd4451a85e7
Dependencies: Stopgaps:

Description (last modified by pbruin)

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.

Attachments (15)

12141_basic_setup.patch (20.9 KB) - added by johanbosman 8 years ago.
12141_2_basic_setup.patch (3.8 KB) - added by mkosters 8 years ago.
Added an associativity check.
12141_improve_repr.patch (6.0 KB) - added by johanbosman 8 years ago.
12141_4.patch (9.7 KB) - added by mkosters 8 years ago.
Many new functions
12141_improve_associativity.patch (1.1 KB) - added by johanbosman 8 years ago.
12141_fix_random_docstring.patch (1.9 KB) - added by johanbosman 8 years ago.
12141_ideal_bla.patch (8.5 KB) - added by johanbosman 8 years ago.
Don't apply this yet; it contains bugs, but I messed up my hg.
12141_ideal_blabla.patch (2.8 KB) - added by johanbosman 8 years ago.
Now both ideal patches can be applied, together with #11068
12141_zero.patch (5.9 KB) - added by mkosters 8 years ago.
Adds some functionality. Apply 12141, improve_ass and fix_random…
11068_combined.patch (451.4 KB) - added by johanbosman 8 years ago.
Contains #11068 and all its dependencies, for convenience
12141.2.patch (37.0 KB) - added by johanbosman 8 years ago.
Replaces all previous patches on this ticket
12141.patch (37.0 KB) - added by johanbosman 8 years ago.
replaces all previous patches
trac_12141_finite_algebras.patch (39.0 KB) - added by pbruin 6 years ago.
based on 5.10.rc2; revised most of the code
trac_12141_categorify.patch (27.0 KB) - added by pbruin 6 years ago.
morphisms, categorification, doctests
trac_12141-FiniteAlgebra.patch (56.8 KB) - added by pbruin 6 years ago.
based on 5.11.beta3

Download all attachments as: .zip

Change History (47)

comment:1 Changed 8 years ago by johanbosman

  • Cc pbruin added
  • Keywords sd35 added

Changed 8 years ago by johanbosman

comment:2 Changed 8 years ago by johanbosman

Lots of things to do still:

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

Changed 8 years ago by mkosters

Added an associativity check.

Changed 8 years ago by johanbosman

Changed 8 years ago by mkosters

Many new functions

Changed 8 years ago by johanbosman

comment:3 Changed 8 years ago by johanbosman

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

Changed 8 years ago by johanbosman

comment:4 Changed 8 years ago by johanbosman

  • Dependencies set to #11068

Changed 8 years ago by johanbosman

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

Changed 8 years ago by johanbosman

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

comment:5 Changed 8 years ago by johanbosman

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

Changed 8 years ago by mkosters

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

comment:6 Changed 8 years ago by 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?

Changed 8 years ago by johanbosman

Contains #11068 and all its dependencies, for convenience

Changed 8 years ago by johanbosman

Replaces all previous patches on this ticket

comment:7 Changed 8 years ago by johanbosman

Replying to 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).

Changed 8 years ago by johanbosman

replaces all previous patches

comment:8 Changed 8 years ago by aapitzsch

Could you change

raise *Error, "..."

to

raise *Error("...")

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

Changed 6 years ago by pbruin

based on 5.10.rc2; revised most of the code

comment:9 Changed 6 years ago by pbruin

  • Authors set to Johan Bosman, Peter Bruin, Michiel Kosters
  • Dependencies #11068 deleted
  • Description modified (diff)
  • Keywords sd35 removed

To be done: morphisms, more things related to ideals

comment:10 Changed 6 years ago by mderickx

  • Cc mderickx added

Changed 6 years ago by pbruin

morphisms, categorification, doctests

comment:11 Changed 6 years ago by pbruin

  • Description modified (diff)
  • Status changed from new to needs_review

I added the class FiniteAlgebraMorphism? and functionality for primary decomposition, mostly written by Johan Bosman. FiniteAlgebras? over a field k are now members of the (existing) category FiniteDimensionalAlgebrasWithBasis?(k). The code is fully doctest-covered.

comment:12 follow-up: Changed 6 years ago by johanbosman

  • Status changed from needs_review to needs_work

I haven't tested any of this yet, but in the code there seem to be a few things that could be improved:

  • Checking associativity is time-consuming. Since most algebras we'll be applying this to are associative anyway, it may be wise to be able to set a flag indicating the algebra is associative without explicit verification.
  • Validity check for homomorphisms seems not very fast either. Code that constructs homomorphisms, like quotient_map, can probably be sped up by putting check=False in there.
  • Does primary decomposition depend on assumptions like associativity and commutativity? Perhaps an error should be raised if these conditions aren't met. Also check this for other functions.

comment:13 in reply to: ↑ 12 Changed 6 years ago by pbruin

Replying to johanbosman:

I haven't tested any of this yet, but in the code there seem to be a few things that could be improved:

Thanks for your suggestions. I should probably have let you look at it before asking for a review. :-)

I thought about including some of these things, but decided that having a usable framework was the first priority. But you are certainly right that these improvements should be made. They shouldn't take a lot of work.

Changed 6 years ago by pbruin

based on 5.11.beta3

comment:14 Changed 6 years ago by pbruin

  • Cc pbruin removed
  • Description modified (diff)
  • Status changed from needs_work to needs_review

The above things should be fixed now. Everything is in trac_12141-FiniteAlgebra.patch.

comment:15 Changed 6 years ago by mderickx

  • Keywords sd51 added

comment:16 Changed 6 years ago by pbruin

For patchbot:

Apply trac_12141-FiniteAlgebra?.patch

Last edited 6 years ago by pbruin (previous) (diff)

comment:17 Changed 6 years ago by pbruin

Apply trac_12141-FiniteAlgebra.patch 

comment:18 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:19 Changed 6 years ago by pbruin

  • Branch set to u/pbruin/12141-FiniteAlgebra
  • Commit set to ac731d2558e25e322bc0e68c5e146ec71b7a8dad
  • Description modified (diff)

No actual changes, just converted the patch to a Git branch.

comment:20 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:21 follow-up: Changed 6 years ago by tscrim

  • Branch changed from u/pbruin/12141-FiniteAlgebra to public/algebras/finite_algebras-12141
  • Commit changed from ac731d2558e25e322bc0e68c5e146ec71b7a8dad to 71f53cffc4943f5a4849bb4d051f0d6d31e2fa57

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:

baa9c86Merge branch 'u/pbruin/12141-FiniteAlgebra' of trac.sagemath.org:sage into public/algebras/finite_algebra-12141
9052b7cPartial work on refactoring morphisms.
809ab1aMerge branch 'develop' into public/algebras/finite_algebra-12141
c089db1Merge branch 'develop' of trac.sagemath.org:sage into public/algebras/finite_algebra-12141
71f53cfFinished implementing homsets for finite algebras.

comment:22 Changed 6 years ago by jhpalmieri

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.

comment:23 Changed 6 years ago by git

  • Commit changed from 71f53cffc4943f5a4849bb4d051f0d6d31e2fa57 to 42e2f4ef1a2a86864c0e5f08e7c247763842a553

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

f5debe1Merge branch 'develop' into public/algebras/finite_algebras-12141
42e2f4eChanged finite algebras to finite dimensional algebras.

comment:24 Changed 6 years ago by tscrim

Good point. Done.

comment:25 in reply to: ↑ 21 ; follow-up: Changed 6 years ago by pbruin

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?

comment:26 in reply to: ↑ 25 Changed 6 years ago by tscrim

Hey Peter,

Replying to pbruin:

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.

comment:27 Changed 6 years ago by git

  • Commit changed from 42e2f4ef1a2a86864c0e5f08e7c247763842a553 to 6dd9dd6c0c36a474642abc3952b46f98a5ceaad5

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

6dd9dd6Changed inverses, doc, and arith return type.

comment:28 follow-up: Changed 6 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

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".

comment:29 in reply to: ↑ 28 Changed 6 years ago by pbruin

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.

comment:30 Changed 6 years ago by git

  • Commit changed from 6dd9dd6c0c36a474642abc3952b46f98a5ceaad5 to b629254871ad4c6240c2531266f5afd4451a85e7

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

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

comment:31 Changed 6 years ago by pbruin

  • Authors changed from Johan Bosman, Peter Bruin, Michiel Kosters to Johan Bosman, Peter Bruin, Michiel Kosters, Travis Scrimshaw
  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Peter Bruin
  • Status changed from needs_review to positive_review

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.

comment:32 Changed 6 years ago by vbraun

  • Branch changed from public/algebras/finite_algebras-12141 to b629254871ad4c6240c2531266f5afd4451a85e7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.