Compute (degree bounded) minimal model of cdga's

[miguelmarco]

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

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

CC: @jhpalmieri @tscrim

Component: algebra

Author: Miguel Marco, Victor Manero

Branch: 612cfb3

Reviewer: Travis Scrimshaw

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

[miguelmarco]

Branch: u/mmarco/compute__degree_bounded__minimal_model_of_cdga_s

[miguelmarco]

New commits:

25cbd8b	Improved cohomology_generators to give only a minimal set of generators
5b53d66	Added `_im_gens_` method for NCPolynomial_plural
81cb6d5	Implement minimal model of cdga's

[miguelmarco]

Commit: 81cb6d5

[embray]

comment:3

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.

[sagetrac-git]

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

bbab0ba

Simplify variable names

[sagetrac-git]

Changed commit from 81cb6d5 to bbab0ba

[jhpalmieri]

comment:6

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

[miguelmarco]

comment:7

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.

[jhpalmieri]

comment:8

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.

[tscrim]

comment:9

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.

[miguelmarco]

comment:10

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.

[miguelmarco]

comment:11

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

[sagetrac-git]

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

f29f168	Minor comment fix
270b5d3	Add doctest for cohomology_generators

[sagetrac-git]

Changed commit from bbab0ba to 270b5d3

[sagetrac-git]

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

a6db43c

Minor fix to generator subindices

[sagetrac-git]

Changed commit from 270b5d3 to a6db43c

[sagetrac-git]

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

713fca7

Some optimizations

[sagetrac-git]

Changed commit from a6db43c to 713fca7

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 713fca7 to e6c7655

[sagetrac-git]

Changed commit from e6c7655 to 5a25d5e

[sagetrac-git]

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

7ba5d05	Cache minimal models to speed up computations
f55f993	Fast check for formality in trivial case
5a25d5e	Add doctest for fast formality check

[sagetrac-git]

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

af07efb

Adapt search through dict keys to python3

[sagetrac-git]

Changed commit from 5a25d5e to af07efb

[miguelmarco]

comment:30

Wouldn't the testing framework complain if the expected output differs from the actual one by some line breaks?

[miguelmarco]

comment:31

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

[tscrim]

comment:32

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.

[sagetrac-git]

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

3d67c5e

Fix documentation formatting

[sagetrac-git]

Changed commit from 7b65e36 to 3d67c5e

[miguelmarco]

comment:34

I think I addressed the complains in the patchbot.

---

New commits:

3d67c5e

Fix documentation formatting

[tscrim]

comment:35

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.

[miguelmarco]

comment:36

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.

[tscrim]

comment:37

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.

[miguelmarco]

comment:38

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

[tscrim]

comment:39

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.

[miguelmarco]

comment:40

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?

[tscrim]

comment:41

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.

[miguelmarco]

comment:42

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.

[tscrim]

comment:43

Yes, that is correct. I get the same 3 errors about output order in multi_polynomial_ideal.py.

[miguelmarco]

comment:44

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?

[tscrim]

comment:45

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

[tscrim]

comment:46

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

[sagetrac-git]

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

612cfb3

Hide nc relations ordering in doctest

[sagetrac-git]

Changed commit from 3d67c5e to 612cfb3

[miguelmarco]

comment:48

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

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:49

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.

[vbraun]

Changed branch from u/mmarco/compute__degree_bounded__minimal_model_of_cdga_s to 612cfb3

[miguelmarco]

Changed author from Miguel Marco to Miguel Marco, Victor Manero

[miguelmarco]

Changed commit from 612cfb3 to none