Opened 8 years ago
Closed 6 years ago
#12141 closed enhancement (fixed)
Implement finite algebras
Reported by:  johanbosman  Owned by:  AlexGhitza 

Priority:  major  Milestone:  sage6.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 )
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 setup is for algebras that are not necessarily unitary, commutative, or associative. Only algebras that satisfy all these conditions are fully supported.
Attachments (15)
Change History (47)
comment:1 Changed 8 years ago by
 Cc pbruin added
 Keywords sd35 added
Changed 8 years ago by
comment:2 Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
comment:3 Changed 8 years ago by
I've uploaded an improvement of the associativity check, but it does need further improvement.
Changed 8 years ago by
comment:4 Changed 8 years ago by
 Dependencies set to #11068
comment:5 Changed 8 years ago by
Basic ideal stuff has also been uploaded now. Still to add: more doctests and support for sidedness in the noncommutative case.
comment:6 Changed 8 years ago by
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?
comment:7 Changed 8 years ago by
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).
comment:8 Changed 8 years ago by
Could you change
raise *Error, "..."
to
raise *Error("...")
so we don't have to do it when switching to Python 3.
comment:9 Changed 6 years ago by
 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
 Cc mderickx added
comment:11 Changed 6 years ago by
 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 doctestcovered.
comment:12 followup: ↓ 13 Changed 6 years ago by
 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 timeconsuming. 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 puttingcheck=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
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.
comment:14 Changed 6 years ago by
 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_12141FiniteAlgebra.patch.
comment:15 Changed 6 years ago by
 Keywords sd51 added
comment:16 Changed 6 years ago by
For patchbot:
Apply trac_12141FiniteAlgebra?.patch
comment:17 Changed 6 years ago by
Apply trac_12141FiniteAlgebra.patch
comment:18 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:19 Changed 6 years ago by
 Branch set to u/pbruin/12141FiniteAlgebra
 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
 Milestone changed from sage6.1 to sage6.2
comment:21 followup: ↓ 25 Changed 6 years ago by
 Branch changed from u/pbruin/12141FiniteAlgebra to public/algebras/finite_algebras12141
 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:
baa9c86  Merge branch 'u/pbruin/12141FiniteAlgebra' of trac.sagemath.org:sage into public/algebras/finite_algebra12141

9052b7c  Partial work on refactoring morphisms.

809ab1a  Merge branch 'develop' into public/algebras/finite_algebra12141

c089db1  Merge branch 'develop' of trac.sagemath.org:sage into public/algebras/finite_algebra12141

71f53cf  Finished implementing homsets for finite algebras.

comment:22 Changed 6 years ago by
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 "finitedimensional algebra" would be better in your situation.
comment:23 Changed 6 years ago by
 Commit changed from 71f53cffc4943f5a4849bb4d051f0d6d31e2fa57 to 42e2f4ef1a2a86864c0e5f08e7c247763842a553
comment:24 Changed 6 years ago by
Good point. Done.
comment:25 in reply to: ↑ 21 ; followup: ↓ 26 Changed 6 years ago by
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 "finitedimensional" is OK; in commutative algebra and algebraic geometry it is very common to say "finite Aalgebra" for an algebra that is finitely generated as an Amodule, but in a general setting like Sage, it is possibly ambiguous. Since the base ring is (at least currently) always a field, "finitedimensional" 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 "finitedimensional algebra", not "finite dimensional algebra", since "finitedimensional" 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
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 "finitedimensional algebra", not "finite dimensional algebra", since "finitedimensional" 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
 Commit changed from 42e2f4ef1a2a86864c0e5f08e7c247763842a553 to 6dd9dd6c0c36a474642abc3952b46f98a5ceaad5
Branch pushed to git repo; I updated commit sha1. New commits:
6dd9dd6  Changed inverses, doc, and arith return type.

comment:28 followup: ↓ 29 Changed 6 years ago by
 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 "finitedimensional".
comment:29 in reply to: ↑ 28 Changed 6 years ago by
Replying to tscrim:
I've changed the inverses to use the
@lazy_attribute
and soy._inverse
is automatically set when callingx._inverse
. Everything is nowEXAMPLES::
and "finitedimensional".
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
 Commit changed from 6dd9dd6c0c36a474642abc3952b46f98a5ceaad5 to b629254871ad4c6240c2531266f5afd4451a85e7
Branch pushed to git repo; I updated commit sha1. New commits:
b629254  Merge branch 'develop' into public/algebras/finite_algebras12141

comment:31 Changed 6 years ago by
 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
 Branch changed from public/algebras/finite_algebras12141 to b629254871ad4c6240c2531266f5afd4451a85e7
 Resolution set to fixed
 Status changed from positive_review to closed
Lots of things to do still: