#27045 closed enhancement (fixed)
Compute (degree bounded) minimal model of cdga's
Reported by:  mmarco  Owned by:  

Priority:  major  Milestone:  sage8.8 
Component:  algebra  Keywords:  
Cc:  jhpalmieri, tscrim  Merged in:  
Authors:  Miguel Marco, Victor Manero  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  612cfb3 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket compute the iminimal model of a cdgalgebra.
It also implements the cohomology algebra up to a given degree.
Change History (51)
comment:1 Changed 3 years ago by
 Branch set to u/mmarco/compute__degree_bounded__minimal_model_of_cdga_s
comment:2 Changed 3 years ago by
 Commit set to 81cb6d5a06fbf901b52505456a32986e5b78af93
 Type changed from PLEASE CHANGE to enhancement
comment:3 Changed 3 years ago by
 Milestone changed from sage8.6 to sage8.7
Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sagepending or sagewishlist.
comment:4 Changed 3 years ago by
 Commit changed from 81cb6d5a06fbf901b52505456a32986e5b78af93 to bbab0bab4dd2e345200359487f9f356592c8dcc8
Branch pushed to git repo; I updated commit sha1. New commits:
bbab0ba  Simplify variable names

comment:5 Changed 3 years ago by
 Cc jhpalmieri added
comment:6 Changed 3 years ago by
I don't know how close this is to review, but this version of cohomology_generators
is much slower than the old one.
Old one:
sage: A3.<a,x,y> = GradedCommutativeAlgebra(GF(3), degrees=(1,2,2)) sage: B3 = A3.cdg_algebra(differential={y: a*x}) sage: %timeit B3.cohomology_generators(30) 1 loop, best of 3: 187 ms per loop sage: A.<a,x,y> = GradedCommutativeAlgebra(QQ, degrees=(1,2,2)) sage: B = A.cdg_algebra(differential={y: a*x}) sage: %timeit B.cohomology_generators(40) 1 loop, best of 3: 553 ms per loop
New one:
sage: A3.<a,x,y> = GradedCommutativeAlgebra(GF(3), degrees=(1,2,2)) sage: B3 = A3.cdg_algebra(differential={y: a*x}) sage: %timeit B3.cohomology_generators(30) 1 loop, best of 3: 2.3 s per loop sage: A.<a,x,y> = GradedCommutativeAlgebra(QQ, degrees=(1,2,2)) sage: B = A.cdg_algebra(differential={y: a*x}) sage: %timeit B.cohomology_generators(40) 1 loop, best of 3: 6.32 s per loop
comment:7 Changed 3 years ago by
I am still working on it (I plan to add too the computation of the cohomology algebra, and maybe a test for formality, although I have to consider if that should go on the same ticket or not).
I didn't notice such a big difference in the timimgs, but maybe that is because I only tested up to relitvely low degrees. Anyways, I don't think it would make sense to keep the old implementation since it doesn't grant to give the right answer (in the sense of not giving a minimal set of generators). I will try to think of another aproach that still grants to give a minimal set of generators, but doesn't get so slow.
BTW, if you would like to review this, I could try to get it to the "needs review" point today or tomorrow, and leave the rest of the work for other tickets.
comment:8 Changed 3 years ago by
If the new version gives different answers from the old one, you should add some doctests to demonstrate this, and in particular the advantages of the new one.
Don't hurry this on my account; it is not always predictable when I will have time to review a ticket.
comment:9 Changed 3 years ago by
Another option (and my preference) would be to have an algorithm
option since they give different results (with different speeds).
I can try to review this when it is ready.
comment:10 Changed 3 years ago by
My point is that the previous method gave an answer that is "wrong", in the sense of giving a generating system that has redundant elements. If one wants just a generating system, one can use all the cohomology classes up to the given degree. So it only makes sense to provide a specific method to compute a reduced system if it is indeed minimal. Hence the change.
I will add a doctest with an example where the given answer is different from the previous method.
comment:11 Changed 3 years ago by
In particular, with the old method:
sage: A.<e1,e2,e3,e4> = GradedCommutativeAlgebra(QQ) sage: d = A.differential({e1:e4*e3,e2:e4*e3}) sage: B = A.cdg_algebra(d) sage: B.cohomology_generators(10) {1: [e4, e3, e1 + e2], 2: [e2*e4, e2*e3, e1*e4, e1*e3]}
whereas with the new:
sage: A.<e1,e2,e3,e4> = GradedCommutativeAlgebra(QQ) sage: d = A.differential({e1:e4*e3,e2:e4*e3}) sage: B = A.cdg_algebra(d) sage: B.cohomology_generators(10) {1: [e4, e3, e1 + e2], 2: [e2*e4, e2*e3]}
Note that e1*e4 = e4*(e1+e2) + e2*e4
comment:12 Changed 3 years ago by
 Commit changed from bbab0bab4dd2e345200359487f9f356592c8dcc8 to 270b5d32e785640d4a64d3e0c05240386d2f4a0a
comment:13 Changed 3 years ago by
 Commit changed from 270b5d32e785640d4a64d3e0c05240386d2f4a0a to a6db43c4241b6f773b5bb3cf93aa294b7f8e15d2
Branch pushed to git repo; I updated commit sha1. New commits:
a6db43c  Minor fix to generator subindices

comment:14 Changed 3 years ago by
 Commit changed from a6db43c4241b6f773b5bb3cf93aa294b7f8e15d2 to 713fca7e9aa2ea6ff74c7cfeb85b10f2df7f2c7f
Branch pushed to git repo; I updated commit sha1. New commits:
713fca7  Some optimizations

comment:15 Changed 3 years ago by
 Commit changed from 713fca7e9aa2ea6ff74c7cfeb85b10f2df7f2c7f to e6c765514620a7b5360a020f6d5869187246081f
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
4d2d95f  Added _im_gens_ method for NCPolynomial_plural

a51cf9d  Implement minimal model of cdga's

f2e748d  Merge branch 't/27045/compute__degree_bounded__minimal_model_of_cdga_s' into minimalmodel

3534f8b  Add method to compute the cohomology algebra

3ff9b4c  Switch from incorrect elimination based method to a linear algebra based for cohomology algebra

8ca775a  Treat case where cohomology algebra is trivial

3a8660d  Add doctest for cohomology_generators

464771f  Minor fix to generator subindices

256b491  Merge branch 'minimalmodel' into t/27045/compute__degree_bounded__minimal_model_of_cdga_s

e6c7655  Add method to check formality

comment:16 Changed 3 years ago by
 Commit changed from e6c765514620a7b5360a020f6d5869187246081f to 5a25d5e7a5e1a378e3af73acbc5c2fd21a85dad2
comment:17 Changed 3 years ago by
 Commit changed from 5a25d5e7a5e1a378e3af73acbc5c2fd21a85dad2 to af07efba70d0689c55ea9c4309110a9fc5d2d133
Branch pushed to git repo; I updated commit sha1. New commits:
af07efb  Adapt search through dict keys to python3

comment:18 Changed 3 years ago by
 Milestone changed from sage8.7 to sage8.8
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
comment:19 Changed 3 years ago by
 Commit changed from af07efba70d0689c55ea9c4309110a9fc5d2d133 to 802d60a0e92d2cf1e0c7f65754c1ff3f3bd7bcc0
Branch pushed to git repo; I updated commit sha1. New commits:
802d60a  Adapt iminimal model to right definition, first implementation of iformality

comment:20 Changed 3 years ago by
 Commit changed from 802d60a0e92d2cf1e0c7f65754c1ff3f3bd7bcc0 to f65eb09b9dcc08137a5bd1bc94cf692a3e7df1f5
Branch pushed to git repo; I updated commit sha1. New commits:
f65eb09  Split is_formal out of the ticket

comment:21 Changed 3 years ago by
 Cc tscrim added
 Description modified (diff)
 Status changed from new to needs_review
comment:22 Changed 3 years ago by
I think this part is ready for review. When this is ready, I will implement a check for iformality in another ticket.
comment:23 Changed 3 years ago by
Some more trivial comments:
if len(cohom1)==0:
>if not cohom1:
 doc formatting:
INPUT:  ``i``  integer (default: `3`); degree to which the result is required to induce an isomorphism in cohomology, and the domain is required to be minimal  ``max_iterations``  integer (default: `3`); the number of iterations of the method at each degree; if the algorithm does not finish in this many iterations at each degree, an error is raised
 ``max_degree``  integer (default: `3`); degree to which the result is required to be isomorphic to self's cohomology
 ``codomain``  the parent where the images live  ``im_gens``  a list or tuple with the images of the generators of this ring
 typo:
the first cohomology o ``self``.
 small tweak:
n'th
>`n`'th
OUTPUT:
usually starts on a separate paragraph. You have some
$
inminimal_model
'sALGORITHM
block. I would also not useself
in here but instead some other variable name.  No space after
:wikipedia:
.  Error messages should start with a lowercase letter (following a general python convention).
 PEP8 says do not put spaces around equals signs when passing as input parameters (e.g.,
foo(n=5)
notfoo(n = 5)
. There are also a few other PEP8 operator spacing issues scattered about.  This should be identically
0
:sum(0*i for i in im_gens)
, so instead just return the appropriate 0 object (should beself.codomain().zero()
).
comment:24 Changed 3 years ago by
 Commit changed from f65eb09b9dcc08137a5bd1bc94cf692a3e7df1f5 to 14ee74185d444671b378076c907744ac6c09d4a7
Branch pushed to git repo; I updated commit sha1. New commits:
14ee741  Doctesting and PEP8 fixes

comment:25 Changed 3 years ago by
I fixed those comments, and while I were at it, also fixed some other PEP8 complaints.
comment:26 Changed 3 years ago by
A few other little things that I would like to see fixed before setting a positive review:
max(self._minimalmodels.keys())
> max(self._minimalmodels)
and if max_degree in self._minimalmodels.keys():
> if max_degree in self._minimalmodels:
.
You still need to fix the docformatting for minimal_model()
and cohomology_algebra
.
Another docformatting thing, but less of an issue since it is hidden in _im_gens_
(but I am picky about these things):
  ``codomain``  The parent where the images live +  ``codomain``  the parent where the images live   ``im_gens``  A list or tuple with the images of the generators of this ring. +  ``im_gens``  a list or tuple with the images of the generators of this ring
im_gens[i]**t[i] for i in range(len(t))
> im_gens[i]val for i,val in enumerate(t)`
Your sum
's also do not need to create the list, but this is a trivial comment.
if len(cohomgens) == 0: raise ValueError("Cohomology ring has no generators")
Could this be if not cohomgens:
? Also, the error message should start with a lowercase letter.
comment:27 Changed 3 years ago by
What exactly do you mean by fixing the docformatting? The long lines in the results of doctests?
comment:28 Changed 3 years ago by
 Commit changed from 14ee74185d444671b378076c907744ac6c09d4a7 to 7b65e366f2862542119d65824f3bde620c8f3838
Branch pushed to git repo; I updated commit sha1. New commits:
7b65e36  Minor format changes

comment:29 Changed 3 years ago by
See comment:23. Specifically, the INPUT:
bullet points are not correctly aligned and should result in an error message when compiling the documentation. Although it would be good to follow the standard conventions (as I understand them) for docstrings too, but I won't strictly enforce that.
comment:30 Changed 3 years ago by
Wouldn't the testing framework complain if the expected output differs from the actual one by some line breaks?
comment:31 Changed 3 years ago by
Can you please take a nother look? I think it is pretty much ready.
comment:32 Changed 3 years ago by
Docbuild errors noted on the patchbot as per comment:29:
 ``i``  integer (default: `3`); degree to which the result is  required to induce an isomorphism in cohomology, and the domain is  required to be minimal. + required to induce an isomorphism in cohomology, and the domain is + required to be minimal
and similar.
comment:33 Changed 3 years ago by
 Commit changed from 7b65e366f2862542119d65824f3bde620c8f3838 to 3d67c5ee66a148d0a597705679cf4d61508cc4ff
Branch pushed to git repo; I updated commit sha1. New commits:
3d67c5e  Fix documentation formatting

comment:34 Changed 3 years ago by
I think I addressed the complains in the patchbot.
New commits:
3d67c5e  Fix documentation formatting

comment:35 Changed 3 years ago by
So the patchbots are reporting failures:
sage t long src/sage/rings/polynomial/multi_polynomial_ideal.py # 6 doctests failed
The 3 main ones seem like they are trivial failures and just need to be updated. Two of the other failures I cannot reproduce, but could always just be marked by # random
if they are an issue. The last one I cannot reproduce either, but is coming from the fact that toy:buchberger
does not return a reduced Gröbner basis (and so is construction order dependent). I suspect these were just brittle tests beforehand.
comment:36 Changed 3 years ago by
Hmmm, that's strange: I get an error message when testing myself:
sage t src/sage/rings/polynomial/multi_polynomial_ideal.py ... ********************************************************************** File "src/sage/rings/polynomial/multi_polynomial_ideal.py", line 2947, in sage.rings.polynomial.multi_polynomial_ideal.NCPolynomialIdeal.elimination_ideal Failed example: I.elimination_ideal([x, z]) Exception raised: Traceback (most recent call last): File "/home/mmarco/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 671, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/mmarco/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 1095, in compile_and_execute exec(compiled, globs) File "<doctest sage.rings.polynomial.multi_polynomial_ideal.NCPolynomialIdeal.elimination_ideal[4]>", line 1, in <module> I.elimination_ideal([x, z]) File "/home/mmarco/sage/local/lib/python2.7/sitepackages/sage/rings/polynomial/multi_polynomial_ideal.py", line 2024, in elimination_ideal return self._elimination_ideal_libsingular(variables) File "/home/mmarco/sage/local/lib/python2.7/sitepackages/sage/libs/singular/standard_options.py", line 140, in wrapper return func(*args, **kwds) File "/home/mmarco/sage/local/lib/python2.7/sitepackages/sage/rings/polynomial/multi_polynomial_ideal.py", line 2051, in _elimination_ideal_libsingular Is = MPolynomialIdeal(R,self.groebner_basis()) File "sage/structure/element.pyx", line 489, in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4611) return self.getattr_from_category(name) File "sage/structure/element.pyx", line 502, in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4720) return getattr_from_other_class(self, cls, name) File "sage/cpython/getattr.pyx", line 394, in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2607) raise AttributeError(dummy_error_message) AttributeError: 'NCPolynomialIdeal' object has no attribute 'groebner_basis' **********************************************************************
But when I run that code inside an interactive session, it works as expected.
I wonder if some of the errors come from the fact that i am developping on a python 3 environment. Seems plausible, since most are due to orderings of the answers in dictionaries.
comment:37 Changed 3 years ago by
Hmm...I didn't think about testing it on Python3. Frédéric (and likely John as well) will be happy that this works on both versions. I cannot say why it doesn't work by using the doctest runner but is fine in an interactive session. Maybe something is being cached or getting put in the "wrong" order in some set/dict. I can probably look into this more tomorrow.
comment:38 Changed 3 years ago by
Ok, if that is a big touble, we could remove the elimination_ideal
method (it is not needed in the final implementation of cohomology_algebra
, but it is probably good to have it anyways).
comment:39 Changed 3 years ago by
With Python3, I am getting the other 3 failures reported by the patchbot. So we can ignore those (I am guessing that is a Python3based patchbot).
I still have no idea about the failure on your doctest run. Which version of Sage are you using to develop this?
I think we should either update the output to match (for the failing tests in elimination_ideal()
, and I get the same output on both Python versions) or we just put ncrelations: {...}
for them.
comment:40 Changed 3 years ago by
Maybe I had something outdated on my sage install. After doing a full rebuild, I get no errors at all.
About the ordering issues in python 3, that is a common problen for all doctests that involve dictionaries... ¿what is the general policy about that?
comment:41 Changed 3 years ago by
It depends on what the issue is. In this case, it seems the added tests do not differ from Python2 and Python3 (at least on my machine), and from looking at the code, it is fed off to the SagePrettyPrinter
, so it should be consistent (if it is not, then there is a bug further down). So I think just updating the doctest output is all we need to do.
comment:42 Changed 3 years ago by
So, just to clarify: you also get errors in a python2 build?
After fully compiling a sagepython2 environment, I get no errors at all.
comment:43 Changed 3 years ago by
Yes, that is correct. I get the same 3 errors about output order in multi_polynomial_ideal.py
.
comment:44 Changed 3 years ago by
That is strange, I get the same result as the doctests. Have you rebased to the last development version? Or mayb there is something machine dependent there?
comment:45 Changed 3 years ago by
I am using 8.4.beta4
, so then there is a machine dependency, which is really bad.
comment:46 Changed 3 years ago by
Well, we can sidestep this problem by what I suggested in commnet:39 (as the ncrelations are not important for the doctest).
comment:47 Changed 3 years ago by
 Commit changed from 3d67c5ee66a148d0a597705679cf4d61508cc4ff to 612cfb33196935934919ae4af1e437fc996ad1e3
Branch pushed to git repo; I updated commit sha1. New commits:
612cfb3  Hide nc relations ordering in doctest

comment:48 Changed 3 years ago by
If that is the only discrepancy, then I agree that is the best we can do right now. Maybe when we do the final switch to python 3 these glitches will stabilize, and get more predictable doctests.
New commits:
612cfb3  Hide nc relations ordering in doctest

comment:49 Changed 3 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
I wish I did have a better understanding why it is not stable even across our machines, but this will do for now. Lo mira bien a mi.
comment:50 Changed 3 years ago by
 Branch changed from u/mmarco/compute__degree_bounded__minimal_model_of_cdga_s to 612cfb33196935934919ae4af1e437fc996ad1e3
 Resolution set to fixed
 Status changed from positive_review to closed
comment:51 Changed 2 years ago by
 Commit 612cfb33196935934919ae4af1e437fc996ad1e3 deleted
New commits:
Improved cohomology_generators to give only a minimal set of generators
Added _im_gens_ method for NCPolynomial_plural
Implement minimal model of cdga's