Project

General

Profile

Bug #1069

GroebnerFan: ERROR: Matrix must be invertible

Added by John Abbott almost 7 years ago. Updated over 5 years ago.

Status:
In Progress
Priority:
Normal
Assignee:
-
Category:
Improving
Target version:
CoCoALib-1.0
Start date:
17 May 2017
Due date:
% Done:

10%

Estimated time:
Spent time:
3.00 h

Description

The following causes an error:

use QQ[x,y,z];
I := ideal(x^3*y^6 +2*x^3*y*z^5,  x^3*y^4*z^2 +2*x*y^3*z^2,  2*y^5*z^3 +2*x^5*z);
fan := GroebnerFanIdeals(I); --> ERROR: Matrix must be invertible

Related issues

Related to CoCoALib - Slug #1049: GroebnerFan: slow examplesIn Progress2017-04-19

Related to CoCoA-5 - Design #984: GroebnerFanIdeals: order matrices sometimes have "large" entriesNew2016-11-26

History

#1 Updated by John Abbott almost 7 years ago

  • Related to Slug #1049: GroebnerFan: slow examples added

#2 Updated by Anna Maria Bigatti almost 7 years ago

Smaller example, but still too big

use QQ[x,y,z];
I := ideal(y^5 -z^5,  x^3*y*z -x*z,  z^8 -x^5*z);
fan := GroebnerFanIdeals(I); --> ERROR: Matrix must be invertible

#3 Updated by Anna Maria Bigatti almost 7 years ago

  • Subject changed from GFAN: ERROR: Matrix must be invertible to GroebnerFan: ERROR: Matrix must be invertible

#4 Updated by John Abbott almost 7 years ago

Another smaller example (but not as small as Anna's)

I= ideal(x^8 +2*x*y^5*z^2,  x*z^7 +2*y*z,  2*x^4*y^2*z^2 +2*x*y^2*z);

#5 Updated by John Abbott almost 7 years ago

Here is a guess as to what the problem is... for matrix orderings there was some "funny trick" using a matrix reduced modulo a prime around 32000... this could cause a matrix to appear not to be of full rank.

#6 Updated by Anna Maria Bigatti almost 7 years ago

John Abbott wrote:

Here is a guess as to what the problem is... for matrix orderings there was some "funny trick" using a matrix reduced modulo a prime around 32000... this could cause a matrix to appear not to be of full rank.

spot on! (As I worked on OrdvArith this morning I knew where to add the check)

--> ERROR: Argument to a numerical function too large (value would be too big)
--> [CoCoALib] OrdvArith::MatrixOrderingMod32749Impl ctor
--> WHERE: at line 89 (column 8) of GroebnerFan.cpkg5

#7 Updated by John Abbott almost 7 years ago

  • Status changed from New to In Progress
  • % Done changed from 0 to 10

The correct solution would be to have a proper implementation of matrix orderings without any "tricks" (too bad if it slow).

An alternative could be to try several different primes, and pick one which works (rather than having the prime "hard-wired" into the code). This should be OK so long as no exponent of an indeterminate becomes bigger than the prime. Nevertheless it would still be a "tricky" solution.

#8 Updated by John Abbott almost 7 years ago

  • Related to Design #984: GroebnerFanIdeals: order matrices sometimes have "large" entries added

#9 Updated by John Abbott almost 7 years ago

Another approach would be to persuade GFan to produce matrices with smaller entries... this is probably not so easy!

#10 Updated by Anna Maria Bigatti almost 7 years ago

John Abbott wrote:

Another approach would be to persuade GFan to produce matrices with smaller entries... this is probably not so easy!

It might be MakeNonNeg to make the big entries.

#11 Updated by John Abbott almost 7 years ago

Here are some order matrices with not-too-big entries whose det is a multiple of 32749:

mat([[28,5,27],
[0,28,29],
[19,27,1]]);

mat([[26,1,28],
[29,19,0],
[5,27,29]]);

mat([[29,26,3],
[0,23,29],
[23,2,28]]);

mat([[28,27,3],
[2,20,29],
[25,0,29]]);

mat([[23,2,26],
[2,29,27],
[27,29,4]]);

mat([[29,3,25],
[29,23,2],
[6,29,29]]);

mat([[29,0,20],
[23,28,1],
[0,27,26]]);

I did try (randomly) searching for some matrices with max entry 28 (or less), but did not find any.

#12 Updated by John Abbott almost 7 years ago

Here is another example which gives trouble:

use QQ[x,y,z];
I := ideal(-66*z^5 +205*x*y*z^2,  134*x^3*y*z +355*y,  97*y^4*z +410*z^2);
GF := GroebnerFanIdeals(I);

You can probably replace the coeffs with smaller ones.

#13 Updated by John Abbott almost 7 years ago

Here is another "slightly smaller" matrix whose determinant is zero mod 32749:

mat([[1,3,35],
     [32,4,3],
     [3,30,4]]);

#14 Updated by Anna Maria Bigatti almost 7 years ago

Just to clarify: this means that one cannot create this ring, hmmmmm....

/**/ NewPolyRing(QQ, "x,y,z", mat([[1,3,35],
                   [32,4,3],
                   [3,30,4]]), 0);

#15 Updated by Anna Maria Bigatti almost 7 years ago

I just removed the coefficients to John's last example:

use QQ[x,y,z];
I := ideal(z^5 +x*y*z^2,  x^3*y*z +y,  y^4*z +z^2);
GF := GroebnerFanIdeals(I);

This fail because det(M)=0 mod p.
The first two examples failed because there where entries > p (now detected, and giving appropriate error message)

#16 Updated by John Abbott over 5 years ago

Yet another example which fails:

use QQ[x,y,z,t];
L := [y^2*z +x*y*t +1,  x^3 +x*y^2,  y^3 +z*t^2];
GF := GroebnerFanIdeals(ideal(L));

And another...

L := [y^2*z +x*z*t +1,  x^3 +x*y^2,  z^3 +y*t^2];

#17 Updated by Anna Maria Bigatti over 5 years ago

I get

--> ERROR: Argument to a numerical function too large (value would be too big)
--> [Cocoalib] OrdvArith::MatrixOrderingMod32749Impl ctor

which is propably as much as we can do.

#18 Updated by John Abbott over 5 years ago

Indeed, if we accept that an error is appropriate then message is reasonable.

It would be better if CoCoA could handle more general orderings (even if only slowly).

Part of the problem is that GFan tends to produce matrices with unnecessarily large entries (I think).

Maybe we can do an internal "matrix order" impl which uses a larger prime (if the platform is 64-bit)?
Or even a completely general one (which will surely be quite slow).

Also available in: Atom PDF