FormalPolyhedraModule - (so far finitely generated) free modules

[mkoeppe]

Add a class FormalPolyhedraModule for formal modules generated by polyhedra, graded by dimension, and a category PolyhedraModules.

So far everything is finitely generated. This will be changed in follow-up tickets.

CC: @tscrim @braunmath

Component: geometry

Author: Matthias Koeppe

Branch/Commit: 463dea2

Reviewer: Travis Scrimshaw

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

[mkoeppe]

Branch: u/mkoeppe/formalpolyhedramodule____so_far_finitely_generated__free_modules

[mkoeppe]

Commit: b9d939c

[mkoeppe]

Author: Matthias Koeppe

[mkoeppe]

New commits:

b9d939c

sage.geometry.polyhedron.modules.formal_polyhedra_module: New

[sagetrac-git]

Changed commit from b9d939c to 8721d98

[sagetrac-git]

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

8721d98

Add __init__.py and imports

[mkoeppe]

comment:4

The results of retract print using a prefix "B". Do I need to override the submodule method?

[tscrim]

comment:5

This is the default prefix for a submodule, so if you want a different prefix, you will need to override it with something like

def submodule(self, gens, check=True, already_echelonized=False,
              unitriangular=False, category=None):
    if not already_echelonized:
        gens = self.echelon_form(gens, unitriangular)
    from sage.modules.with_basis.subquotient import SubmoduleWithBasis
        return SubmoduleWithBasis(gens, ambient=self, prefix='M',
                                  unitriangular=unitriangular,
                                  category=category)

However, you can set/change this dynamically at any point with:

sage: M_lower.print_options(prefix='V')
sage: y
V[0]

Although there probably should be an option added to the submodule to pass along such information to the submodule's constructor...

[sagetrac-git]

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

fd5bc34

sage.categories.polyhedra_modules: New

[sagetrac-git]

Changed commit from 8721d98 to fd5bc34

[mkoeppe]

comment:7

Is the idea of the prefix for the submodule elements to refer to the ambient module, or to distinguish from the ambient module?

[tscrim]

comment:8

I am not quite sure I understand your question. All CFMs have a prefix parameter that can be set by the user to help them distinguish between the different *modules they are working with. This is used extensively in Sage (e.g., symmetric functions).

[mkoeppe]

comment:9

I guess I need to ask a more basic question first. In the example:

   sage: M.basis()
   Finite family {conv([0], [1]): [conv([0], [1])], {[1]}: [{[1]}], conv([1], [2]): 
   [conv([1], [2])]}
   sage: M_lower.basis()
   Finite family {0: B[0]}

How come these two bases (of the ambient module and of the submodule) are indexed in very different ways?

[tscrim]

comment:10

A submodule of dimension d just uses the indexing set 0,...,d-1 because any generic submodule would not necessarily have any particular way to relate its basis with that of the ambient module. Moreover, it needs some indexing set for the basis, so it just chooses the simplest and most generic one. One possible way would be to use the leading support of each of the echeleonized basis elements, but that still feels fairly artificial/arbitrary to me.

[mkoeppe]

comment:11

OK, thanks a lot for the explanation. I think I will revisit this cosmetic issue later.

[sagetrac-git]

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

a0d791e	WIP: add submodule method
b2ba70e	Update documentation

[sagetrac-git]

Changed commit from fd5bc34 to b2ba70e

[sagetrac-git]

Changed commit from b2ba70e to 5115960

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

5115960

Update documentation

[sagetrac-git]

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

5988973

Update doctests to set prefixes for distinguishing the ambient, sub, quotient

[sagetrac-git]

Changed commit from 5115960 to 5988973

[sagetrac-git]

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

7ae0c7e

Add to doc

[sagetrac-git]

Changed commit from 5988973 to 7ae0c7e

[tscrim]

comment:17

At this point, I don't see the need for having a category PolyhedraModules. Perhaps this is something you will expand on later, but currently you can just put the degree_on_basis in the FormalPolyhedraModule (which would belong to the category of GradedModulesWithBasis). So can you explain a bit why we should have this category?

If you do keep the category, super_categories needs a doctest.

Your INPUT: block should follow this format:

INPUT:

- ``foo`` -- some information
- ``bar`` -- other information that is
  really long

Note the alignment (you have an additional 1 space indentation) and the double -- for the non-bullet point.

FormalPolyhedraModule.__init__ needs a doctest; here we usually do a TestSuite(M).run() as the test.

[mkoeppe]

comment:18

Replying to @tscrim:

At this point, I don't see the need for having a category PolyhedraModules. Perhaps this is something you will expand on later, but currently you can just put the degree_on_basis in the FormalPolyhedraModule (which would belong to the category of GradedModulesWithBasis). So can you explain a bit why we should have this category?

It is indeed for future use, when I introduce the space generated by indicator functions of polyhedra, which is the quotient by all inclusion-exclusion relations. That space is no longer graded, but only filtered by dimension.

[mkoeppe]

comment:19

But I'll follow your advice and make it just a method of the class for now.

[sagetrac-git]

Changed commit from 7ae0c7e to 37aae77

[sagetrac-git]

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

37aae77

Remove category, merge method degree_on_basis into the class

[mkoeppe]

comment:21

Replying to @tscrim:

Your INPUT: block should follow this format...
Note the alignment (you have an additional 1 space indentation) and the double -- for the non-bullet point.

Thanks, fixed.

I really wish we had a linter for the docstrings that we could run locally instead of wasting reviewers' time with these formatting details and/or waiting for the patchbot...

[sagetrac-git]

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

bdbd9e4

Another formatting fix

[sagetrac-git]

Changed commit from 37aae77 to bdbd9e4

[tscrim]

comment:23

Sorry, that wasn't meant to be a suggestion to remove it; it was purely a question as I don't know what your long term structural plans are. Although I do think purely local to this ticket it is better.

Your __init__ still needs a doctest, something like

            sage: from sage.geometry.polyhedron.modules.formal_polyhedra_module import FormalPolyhedraModule
            sage: def closed_interval(a,b): return Polyhedron(vertices=[[a], [b]])
            sage: I01 = closed_interval(0, 1); I01.rename("conv([0], [1])")
            sage: I11 = closed_interval(1, 1); I11.rename("{[1]}")
            sage: I12 = closed_interval(1, 2); I12.rename("conv([1], [2])")
            sage: I02 = closed_interval(0, 2); I02.rename("conv([0], [2])")
            sage: M = FormalPolyhedraModule(QQ, 1, basis=[I01, I11, I12, I02])
            sage: TestSuite(M).run()

To help avoid some confusion in degree_on_basis, I think it would be a bit better to say this would only be a filtration, since this module does not (yet) have the linear relations implemented and it is in the category of graded modules.

Indeed, such a linter would be nice.

[sagetrac-git]

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

aecc78a	Update doc and link into reference manual
463dea2	FormalPolyhedraModule.__init__: Add test

[sagetrac-git]

Changed commit from bdbd9e4 to 463dea2

[mkoeppe]

comment:25

Done.

[mkoeppe]

comment:26

Replying to @tscrim:

Indeed, such a linter would be nice.

Meta-ticket #28936 (Adopt mainstream Python testing/linting infrastructure, describe in Developer's Guide) has several wishlist items in this direction.

[tscrim]

comment:27

Thank you.

[tscrim]

Reviewer: Travis Scrimshaw

[mkoeppe]

comment:28

Thanks!

[vbraun]

Changed branch from u/mkoeppe/formalpolyhedramodule____so_far_finitely_generated__free_modules to 463dea2