Trivial strategy for basis

[mahrud]

Here is a strategy for basis which I would have thought engine should already take advantage of:

Suppose $S$ is a multigraded ring with $S_0 = k$ and $M$ is an $R$-module which has some generators in degree 0 and lots of other generators in higher degrees. If I asked for basis(degree 1_S, M), I would expect M2 to simply return the generators in degree 0 with no computation, but this doesn't seem to be the case (in fact, the computation can get significantly slower in some examples). The same should be the case for basis of $M(d)$ in degree d of course.

It's easy to patch this at the top level, but I'm wondering if there's something easy that can be fixed in the engine.

More generally, say we want to compute $M_1$ for a module with some generators in degrees 0 and 1 and lots others in larger degrees. I presume the algorithm should only care about generators in degrees 0 and 1, and disregard the others. Right? The example above seems to suggest this isn't the case.

cc: @jkyang92 @mikestillman

[DanGrayson]

A graded module can have elements in degree 0 without having generators in degree 0. And it's supposed to return a basis, so things have to be reduced.

[mahrud]

See the bolded correction in my description. Say a module has generators in degrees 0, 1, and 100. Then basis(0, M) should simply return the generators in degree 0, maybe with a trim.

[mahrud]

Here's an example to show how unnecessarily slow M2's algorithm is:

i1 : debug needsPackage "FGLM";

i2 : I = cyclic(7, MonomialOrder=>Lex)

o2 = ideal (a + b + c + d + e + f + g, a*b + a*g + b*c + c*d + d*e + e*f + f*g, a*b*c + a*b*g + a*f*g + b*c*d + c*d*e + d*e*f
     ------------------------------------------------------------------------------------------------------------------------
     + e*f*g, a*b*c*d + a*b*c*g + a*b*f*g + a*e*f*g + b*c*d*e + c*d*e*f + d*e*f*g, a*b*c*d*e + a*b*c*d*g + a*b*c*f*g +
     ------------------------------------------------------------------------------------------------------------------------
     a*b*e*f*g + a*d*e*f*g + b*c*d*e*f + c*d*e*f*g, a*b*c*d*e*f + a*b*c*d*e*g + a*b*c*d*f*g + a*b*c*e*f*g + a*b*d*e*f*g +
     ------------------------------------------------------------------------------------------------------------------------
     a*c*d*e*f*g + b*c*d*e*f*g, a*b*c*d*e*f*g - 1)

o2 : Ideal of kk[a..g]

i3 : B = basis(0, I)

This basis command takes >20min to literally return the zero matrix.

[mikestillman]

Interesting, it is assuming it needs to compute a Groebner basis to determine if 1 is in the basis or not (actually, it does need to determine that). But in fact, this should complain as I is not presented as a homogeneous ideal, I would think...

I agree, this should be fixed, in the case when the input is homogeneous. (And perhaps give an error if not homogeneous). It should be fairly easy to change the code to only compute a GB in degrees <= d (if we want basis(d, M)). That part is not part of the engine code though: the engine code gets matrices which are presumed to be GB's, if I recall correctly.

[mahrud]

Ah, I didn't realize it's not homogeneous, but try with this:

I = ideal I_*_{0..5}
basis(0, I)

Again, should be trivial to check that by degree reasons the answer should be zero.

Similarly, since there's only a single generator in degree 1, it should be trivial to do this:

basis(1, I)

[mahrud]

It should be fairly easy to change the code to only compute a GB in degrees <= d

I agree that it should be a simple stop condition to add. I would like it to work in the multigraded case as well, but that's a bit more complicated since you need to check <= against the effective cone ...

[mikestillman]

Using polyhedral code in the multi-graded case, on larger examples, is way preferable, it seems. However, that might be quite a bit of overhead in simpler multi-graded settings. I wonder if we could somehow determine which is best?

[mahrud]

I totally agree. I've ran into this on multiple occasions and I'm not sure what's best. Having a super fast code for cone comparison and finding minimal generators would perhaps alleviate this. Do we have something like this?