Opened 3 years ago

Closed 3 years ago

Last modified 2 years ago

#27045 closed enhancement (fixed)

Compute (degree bounded) minimal model of cdga's

Reported by: mmarco Owned by:
Priority: major Milestone: sage-8.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:

Status badges

Description (last modified by mmarco)

This ticket compute the i-minimal model of a cdg-algebra.

It also implements the cohomology algebra up to a given degree.

Change History (51)

comment:1 Changed 3 years ago by mmarco

  • Branch set to u/mmarco/compute__degree_bounded__minimal_model_of_cdga_s

comment:2 Changed 3 years ago by mmarco

  • Commit set to 81cb6d5a06fbf901b52505456a32986e5b78af93
  • Type changed from PLEASE CHANGE to enhancement

New commits:

25cbd8bImproved cohomology_generators to give only a minimal set of generators
5b53d66Added _im_gens_ method for NCPolynomial_plural
81cb6d5Implement minimal model of cdga's

comment:3 Changed 3 years ago by embray

  • Milestone changed from sage-8.6 to sage-8.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 sage-pending or sage-wishlist.

comment:4 Changed 3 years ago by git

  • Commit changed from 81cb6d5a06fbf901b52505456a32986e5b78af93 to bbab0bab4dd2e345200359487f9f356592c8dcc8

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

bbab0baSimplify variable names

comment:5 Changed 3 years ago by jhpalmieri

  • Cc jhpalmieri added

comment:6 Changed 3 years ago by jhpalmieri

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 mmarco

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 jhpalmieri

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 tscrim

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 mmarco

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 mmarco

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

Last edited 3 years ago by mmarco (previous) (diff)

comment:12 Changed 3 years ago by git

  • Commit changed from bbab0bab4dd2e345200359487f9f356592c8dcc8 to 270b5d32e785640d4a64d3e0c05240386d2f4a0a

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

f29f168Minor comment fix
270b5d3Add doctest for cohomology_generators

comment:13 Changed 3 years ago by git

  • Commit changed from 270b5d32e785640d4a64d3e0c05240386d2f4a0a to a6db43c4241b6f773b5bb3cf93aa294b7f8e15d2

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

a6db43cMinor fix to generator subindices

comment:14 Changed 3 years ago by git

  • Commit changed from a6db43c4241b6f773b5bb3cf93aa294b7f8e15d2 to 713fca7e9aa2ea6ff74c7cfeb85b10f2df7f2c7f

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

713fca7Some optimizations

comment:15 Changed 3 years ago by git

  • Commit changed from 713fca7e9aa2ea6ff74c7cfeb85b10f2df7f2c7f to e6c765514620a7b5360a020f6d5869187246081f

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

4d2d95fAdded _im_gens_ method for NCPolynomial_plural
a51cf9dImplement minimal model of cdga's
f2e748dMerge branch 't/27045/compute__degree_bounded__minimal_model_of_cdga_s' into minimalmodel
3534f8bAdd method to compute the cohomology algebra
3ff9b4cSwitch from incorrect elimination based method to a linear algebra based for cohomology algebra
8ca775aTreat case where cohomology algebra is trivial
3a8660dAdd doctest for cohomology_generators
464771fMinor fix to generator subindices
256b491Merge branch 'minimalmodel' into t/27045/compute__degree_bounded__minimal_model_of_cdga_s
e6c7655Add method to check formality

comment:16 Changed 3 years ago by git

  • Commit changed from e6c765514620a7b5360a020f6d5869187246081f to 5a25d5e7a5e1a378e3af73acbc5c2fd21a85dad2

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

7ba5d05Cache minimal models to speed up computations
f55f993Fast check for formality in trivial case
5a25d5eAdd doctest for fast formality check

comment:17 Changed 3 years ago by git

  • Commit changed from 5a25d5e7a5e1a378e3af73acbc5c2fd21a85dad2 to af07efba70d0689c55ea9c4309110a9fc5d2d133

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

af07efbAdapt search through dict keys to python3

comment:18 Changed 3 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.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 git

  • Commit changed from af07efba70d0689c55ea9c4309110a9fc5d2d133 to 802d60a0e92d2cf1e0c7f65754c1ff3f3bd7bcc0

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

802d60aAdapt i-minimal model to right definition, first implementation of i-formality

comment:20 Changed 3 years ago by git

  • Commit changed from 802d60a0e92d2cf1e0c7f65754c1ff3f3bd7bcc0 to f65eb09b9dcc08137a5bd1bc94cf692a3e7df1f5

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

f65eb09Split is_formal out of the ticket

comment:21 Changed 3 years ago by mmarco

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

comment:22 Changed 3 years ago by mmarco

I think this part is ready for review. When this is ready, I will implement a check for i-formality in another ticket.

comment:23 Changed 3 years ago by tscrim

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 $ in minimal_model's ALGORITHM block. I would also not use self 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) not foo(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 be self.codomain().zero()).

comment:24 Changed 3 years ago by git

  • Commit changed from f65eb09b9dcc08137a5bd1bc94cf692a3e7df1f5 to 14ee74185d444671b378076c907744ac6c09d4a7

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

14ee741Doctesting and PEP8 fixes

comment:25 Changed 3 years ago by mmarco

I fixed those comments, and while I were at it, also fixed some other PEP8 complaints.

comment:26 Changed 3 years ago by tscrim

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 mmarco

What exactly do you mean by fixing the docformatting? The long lines in the results of doctests?

comment:28 Changed 3 years ago by git

  • Commit changed from 14ee74185d444671b378076c907744ac6c09d4a7 to 7b65e366f2862542119d65824f3bde620c8f3838

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

7b65e36Minor format changes

comment:29 Changed 3 years ago by tscrim

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 mmarco

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 mmarco

Can you please take a nother look? I think it is pretty much ready.

comment:32 Changed 3 years ago by tscrim

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 git

  • Commit changed from 7b65e366f2862542119d65824f3bde620c8f3838 to 3d67c5ee66a148d0a597705679cf4d61508cc4ff

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

3d67c5eFix documentation formatting

comment:34 Changed 3 years ago by mmarco

I think I addressed the complains in the patchbot.


New commits:

3d67c5eFix documentation formatting

comment:35 Changed 3 years ago by tscrim

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 mmarco

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/site-packages/sage/doctest/forker.py", line 671, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/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/site-packages/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/site-packages/sage/libs/singular/standard_options.py", line 140, in wrapper
        return func(*args, **kwds)
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/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 tscrim

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 mmarco

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 tscrim

With Python3, I am getting the other 3 failures reported by the patchbot. So we can ignore those (I am guessing that is a Python3-based 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 nc-relations: {...} for them.

comment:40 Changed 3 years ago by mmarco

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 tscrim

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 mmarco

So, just to clarify: you also get errors in a python2 build?

After fully compiling a sage-python2 environment, I get no errors at all.

comment:43 Changed 3 years ago by tscrim

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 mmarco

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 tscrim

I am using 8.4.beta4, so then there is a machine dependency, which is really bad.

comment:46 Changed 3 years ago by tscrim

Well, we can sidestep this problem by what I suggested in commnet:39 (as the nc-relations are not important for the doctest).

comment:47 Changed 3 years ago by git

  • Commit changed from 3d67c5ee66a148d0a597705679cf4d61508cc4ff to 612cfb33196935934919ae4af1e437fc996ad1e3

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

612cfb3Hide nc relations ordering in doctest

comment:48 Changed 3 years ago by mmarco

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:

612cfb3Hide nc relations ordering in doctest

comment:49 Changed 3 years ago by tscrim

  • 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 vbraun

  • 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 mmarco

  • Authors changed from Miguel Marco to Miguel Marco, Victor Manero
  • Commit 612cfb33196935934919ae4af1e437fc996ad1e3 deleted
Note: See TracTickets for help on using tickets.