Add free and multigraded free resolutions with libSingular backend

[kwankyu]

Sage lacks free resolution computation. We add free and multigraded free resolutions pulling libSingular's resolutions. This will be a ground work for further commutative algebra and algebraic geometry computations.

Depends on #33868

Component: algebra

Author: Kwankyu Lee, Travis Scrimshaw

Branch/Commit: 73f746f

Reviewer: Travis Scrimshaw, Kwankyu Lee

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

[kwankyu]

Branch: u/klee/33950

[sagetrac-git]

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

d2b1b06	Add modules over domain
83cbb2b	Merge branch 'develop' into module-over-domain
5e5b8f1	Add submodule.py
74a3930	Clean up doc tree of modules
c725f74	Small fix on the main toc
4d27982	Add free resolutions

[sagetrac-git]

Commit: 4d27982

[kwankyu]

Author: Kwankyu Lee

[sagetrac-git]

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

c4e61db

Add free resolutions

[sagetrac-git]

Changed commit from 4d27982 to c4e61db

[sagetrac-git]

Changed commit from c4e61db to 59226b1

[sagetrac-git]

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

b2870da	Refactor FreeModule_generic
fcb51da	Add coercion map from a submodule to the free module
c4e89b9	A fix to cooperate with matrix infrastructure
9f12e32	Rename to Module_free_ambient and fix doctests
59226b1	Add free resolutions

[sagetrac-git]

Changed commit from 59226b1 to 2cb093d

[sagetrac-git]

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

1d11ed3	Merge branch 'develop'
d923d35	Fixes for pyflakes warnings
5d20e6e	Remove a blank line between bulletitems at one place
2cb093d	Merge branch #33868

[sagetrac-git]

Changed commit from 2cb093d to 0232e9e

[sagetrac-git]

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

8585adb	Submodules of submodules should respect the defining module.
9bd6f89	Revert change to quotient modules.
568097b	Standardizing submodules as subquotients.
280e8a7	Adding support for quotients of quotients.
1ca0d64	Removing code duplication of span() and submodule().
1baa006	Rename subquotient back to submodule
4a9446c	Fix a title
0b3b860	Fix a doctest
cd28605	Some more edits
0232e9e	Add free resolutions

[tscrim]

comment:10

It is very nice to have this feature in Sage; it is something that has been missing for a long time. Sorry for taking so long to get to reviewing it. I have some issues with the overall design that I would like to discuss:

• I think we should do the main computations lazily; that is only when the user asks for them such as computing the length of the resolution. This is a general Sage philosophy: a Parent should be quick to create (of course, this is not necessarily universal). These lazy computational bits could then be overriden in subclasses for specific implementations. I think this also leads to a better organizational structure for the classes.
• Why are these classes in Cython files? The only thing that uses Cython is the to_sage_resolution(), which could go in the Singular interface file.

Some more trivial points:

• Use _repr_ instead of __repr__ as the former allows a user to use rename() on the object.
• I would have FreeResolution_generic inherit from UniqueRepresentation because we don't want to have to do the computations twice for the same ideal.
• I think we should have the string repr be based off the input data. The _latex_, _ascii_art_, _unicode_art_ can then use the ones from chain_complex() with the current one being something like pp(). Perhaps _latex_ is better directly implemented though (with a latex_name attribute added too).
• You can make _initial_differential a @lazy_attribute.
• I much prefer single underscore instead of double as the name-mangling makes it difficult when you want to directly access the attributes (e.g., for speed).
• Given the chain_complex(), are there any methods there worthwhile to also call from the free resolution? I am not sure there are any (beyond display methods) since resolutions are exact.

[kwankyu]

comment:11

Replying to @tscrim:

Sorry for taking so long to get to reviewing it.

No. Just thank you for attention.

• I think we should do the main computations lazily; that is only when the user asks for them such as computing the length of the resolution.

As you see, the gist of the code is to convert the resolution object computed by Singular to a Sage object as fast as possible and the Sage object contains detailed information (degrees(multi degrees) of generators of component modules and the length) about the resolution. By my experiments, the resolution computation is as fast as Macaulay2.

Then what do you mean by doing the computation lazily? For instance, the length is immediately available after the conversion. And I don't see anything to do lazily in this conversion.

#33953 is dependent on this ticket and requires fast resolution computation.

[sagetrac-git]

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

bdbb479

Merge branch 'develop' into t/33950/free-resolution

[sagetrac-git]

Changed commit from 0232e9e to bdbb479

[tscrim]

comment:13

Replying to @kwankyu:

Replying to @tscrim:

• I think we should do the main computations lazily; that is only when the user asks for them such as computing the length of the resolution.

As you see, the gist of the code is to convert the resolution object computed by Singular to a Sage object as fast as possible and the Sage object contains detailed information (degrees(multi degrees) of generators of component modules and the length) about the resolution. By my experiments, the resolution computation is as fast as Macaulay2.

Indeed. I want to keep that in Cython, but moved to the interface file. I feel that is the more appropriate place for it.

Then what do you mean by doing the computation lazily? For instance, the length is immediately available after the conversion. And I don't see anything to do lazily in this conversion.

This is what I mean: Do not ask Singular to do the computation until it is required by something the user wants to do. Now this can be improved by making the _repr_() not needing to compute the resolution.

A followup ticket would be to make the API for this play nicely with FP graded modules. I would likely want an object for those resolutions, but that will take a little bit of work to handle the potentially infinite length. I can likely modify what I did for the Hochschild complex for that.

Based on that, I would want to convert this to a subclass of CategoryObject instead of SageObject and have it live in the category of ChainComplexes. This shouldn't change much, but it does allow for the possibility of implementing maps or functors on free resolutions (mainly this would allow for computation of (left) derived functors). What do you think?

---

New commits:

736d448

Moving the main computation to be done on demand.

[tscrim]

Changed branch from u/klee/33950 to public/rings/free_multigraded_resolutions-33950

[tscrim]

Changed commit from bdbb479 to 736d448

[tscrim]

Reviewer: Travis Scrimshaw

[kwankyu]

comment:14

Replying to @tscrim:

This is what I mean: Do not ask Singular to do the computation until it is required by something the user wants to do. Now this can be improved by making the _repr_() not needing to compute the resolution.

The lazy computation looks good to me.

Based on that, I would want to convert this to a subclass of CategoryObject instead of SageObject and have it live in the category of ChainComplexes. This shouldn't change much, but it does allow for the possibility of implementing maps or functors on free resolutions (mainly this would allow for computation of (left) derived functors). What do you think?

Okay. Feel free to modify the code for your needs, till the code pass the original doctests and run as fast as before.

[kwankyu]

comment:15

Replying to @tscrim:

Indeed. I want to keep that in Cython, but moved to the interface file. I feel that is the more appropriate place for it.

I felt that too, but also thought that keeping [Graded]FreeResolution class and to_sage_resolution[_graded] function in the same cython file would make them run fast. If I am wrong, I am okay with moving them to the Singular interface file.

[tscrim]

comment:16

I was hoping to get to this today, but something unexpected came up.

The speed of the functions is not affected by being in the same Cython file. Now there will be some slight slowdown for converting the resolution class to a Python file (versus Cython), but since that is all of the boilerplate code that is called infrequently to only once (e.g., the __getitem__), this should be insignificant (i.e., nearly all of the time is spent computing the resolution). However, having it be a Python class will make maintenance and extensions easier in the long term.

Is there some tests I should use that are particularly good for timing purposes?

[kwankyu]

Changed author from Kwankyu Lee to Kwankyu Lee, Travis Scrimshaw

[tscrim]

comment:23

Replying to @kwankyu:

• The base class FreeResolution_generic seems generic rather than abstract.

Bikeshedding (nor do I really care that much): I am not sure I agree with calling it generic as it really doesn't work unless subclasses implement certain aspects. While instances can be created, I don't think that qualifies it to be generic.

• I prefer a spaced list than a tight list in INPUT section. From the discussion in sage-devel, I learned that I should respect whichever style an author uses. So I reverted my own change of an AUTHOR section.

That was not my takeaway from that discussion; nobody wanted to make a policy. Yet, I don't care too much about this file to insist.

Otherwise it looks good to me.

Thank you.

For performance, I tested with #33953. I got

Thank you for testing.

I don't know if the difference in timings is statistically significant. Anyway, it seems negligible.

Using the numbers you gave, it less than 1% slower by comparing the means. So if this is something that is going to be called very frequently or in a tight loop, then we might want to care about it. Although I am fairly certain it will become even smaller on larger examples.

If everything is good with you, then you can set a positive review and I will try to review #33953.

[kwankyu]

comment:24

Replying to @tscrim:

Bikeshedding (nor do I really care that much): I am not sure I agree with calling it generic as it really doesn't work unless subclasses implement certain aspects. While instances can be created, I don't think that qualifies it to be generic.

Perhaps I learned somewhere that an abstract class defines interfaces, and a subclass provides implementations. A generic class provides common operations...

If everything is good with you, then you can set a positive review and I will try to review #33953.

Thank you!

[tscrim]

comment:25

Replying to @kwankyu:

Replying to @tscrim:

Bikeshedding (nor do I really care that much): I am not sure I agree with calling it generic as it really doesn't work unless subclasses implement certain aspects. While instances can be created, I don't think that qualifies it to be generic.

Perhaps I learned somewhere that an abstract class defines interfaces, and a subclass provides implementations. A generic class provides common operations...

There isn't universal definitions of this IIRC. My understanding of Sage is a generic class is one that can do most functionality on its own, but lacks some specific features that subclasses can do. Consequently, anything that requires a subclass to implement even partial functionality should be considered an abstract class. Well, it is possible that the FreeResolution_generic will eventually become more of a generic class. I feel that calling it a generic class is slightly misleading, but I don't think it is so important here.

[kwankyu]

comment:26

Replying to @tscrim:

Perhaps I learned somewhere that an abstract class defines interfaces, and a subclass provides implementations. A generic class provides common operations...

There isn't universal definitions of this IIRC.

Okay.

I uploaded #33953 rebased on this ticket.

[vbraun]

comment:27

PDF docs don't build:

[sagemath_doc_pdf-none] ! Package inputenc Error: Unicode character ⊕ (U+2295)
[sagemath_doc_pdf-none] (inputenc)                not set up for use with LaTeX.

[tscrim]

comment:28

You either need to update build/pkgs/sage_docbuild/src/sage_docbuild/conf.py with the unicode symbol

    \DeclareUnicodeCharacter{2295}{\ensuremath{\oplus}}

or use ⨁ (2A01) instead of ⊕ (2295).

[sagetrac-git]

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

73f746f

Add unicode symbol 2295 for pdf docs

[sagetrac-git]

Changed commit from ab725f2 to 73f746f

[kwankyu]

comment:30

Replying to @tscrim:

You either need to update build/pkgs/sage_docbuild/src/sage_docbuild/conf.py with the unicode symbol

    \DeclareUnicodeCharacter{2295}{\ensuremath{\oplus}}

or use ⨁ (2A01) instead of ⊕ (2295).

Thanks. This ⨁ (2A01) looks too big on my terminal.

[tscrim]

comment:31

Thanks.

[vbraun]

Changed branch from public/rings/free_multigraded_resolutions-33950 to 73f746f