solve hangs on a small algebraic system with 4 equations in 4 unknowns

[zimmermann6]

The following command hangs with Sage 4.4.4:

var = [s,t,w,z]
sys = [-83065036657810695629*s^2 + 83065036657810695629*t*w - 68998003149632685\
30106646060491053792528*s - 395748941050538664245556665401237631434*w + 6899800\
710712292645598903080085537498136631434, 124597554986716043444*s^2 - 1245975549\
86716043444*t*w + 10349700472444902795201501609065485036608*s - 268851627794621\
336185309600880111037777*w - 10349700203593399598010554584812612113052962223, -\
282961047374832134660970*s^2 - 8410334961603332923585*s*z + 8410334961603332923\
585*t^2 + 282961047374832134660970*t*w - 23504169772922374247873205131210852239\
883040*s - 30616067929472784598571512251700309424241225*t - 7028115267891297114\
2272480500812537457*w - 349302390945015468969034253953644989640360*z - 94573827\
6702217921211141587964108207667243789392, -5322973679105824997312280*s^2 + 9157\
920291523629102472*s*z - 9157920291523629102472*t^2 + 5322973679105824997312280\
*t*w - 442153003783476173947515315017330812575960960*s + 3127353268883216472554\
94866020283168151616125*t - 167582752514587776396443776337970730676*w + 3803514\
92362350173958234007398030593401152*z - 176904945185291980573382635775655917064\
32113716525]
solve(sys,var)

In comparison, Maple 13 answers in 38 milliseconds...

CC: @jasongrout @kcrisman @malb @williamstein

Component: calculus

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

[qed777]

comment:1

I see this problem on both bsd and sage.math. Pressing Control-C yields

sage: solve(sys, [s, t, w, z])
Control-C pressed.  Interrupting Maxima. Please wait a few seconds...
Maxima crashed -- automatically restarting.
[]
sage: 

Possibly naive question: Is this a problem in the Maxima wrapper or in Maxima itself?

On sage.math, Maple 12 responds to solve({...}, [s, t, w, z]); almost immediately with

[[s = 1/15 RootOf(145777 _Z  - 2724518665994742900057173191849397

                                                         57108616849397
     + 181634577732980673347190960 _Z, label = _L6), t = --------------, w = 1,
                                                            32799825

          137699550319729285466821911369819307114778019367342119879667352
    z = - --------------------------------------------------------------- -
              618583496779496012457663125225479925612236417948265175

          9946390625479936819718245891740613642685141                        2
    -------------------------------------------------------- RootOf(145777 _Z
    27836257355077320560594840635146596652550638807671932875

     - 2724518665994742900057173191849397 + 181634577732980673347190960 _Z,

    label = _L6)]]

But I think it's too late in the 4.5.2 release cycle to fix this problem, so I've changed the milestone to 4.5.3.

Out of curiosity: Does this system have a special provenance?

[qed777]

comment:2

Replying to @qed777:

But I think it's too late in the 4.5.2 release cycle to fix this problem, so I've changed the milestone to 4.5.3.

Or is there a simple fix someone can post very soon?

[zimmermann6]

comment:3

Replying to @qed777:

Possibly naive question: Is this a problem in the Maxima wrapper or in Maxima itself?

it seems to be a problem in the main Maxima to_poly_solve function. With the option
use_grobner=true it returns (but never gets a chance to get there in the try ... except).

Out of curiosity: Does this system have a special provenance?

yes, it comes from Coppersmith's algorithm to find small roots of a polynomial system, which was itself used by a master student (Thomas Prest) in the context of polynomial selection for the
Number Field Sieve with two non-linear polynomials.

Paul

[qed777]

comment:4

Is this purely an upstream problem?

[qed777]

comment:5

The 4.5.3 series will soon be in "feature freeze."

[zimmermann6]

comment:6

Replying to @qed777:

Is this purely an upstream problem?

I have no idea. The maxima SPKG.txt contains no maintainer name, thus I don't know who to put in cc to report this problem upstream (if needed). Can anybody help?

Paul