Opened 11 years ago
Closed 9 years ago
#12718 closed defect (fixed)
polynomial substitution overflow hell (libsingular bug?)
Reported by:  was  Owned by:  malb 

Priority:  critical  Milestone:  sage6.3 
Component:  commutative algebra  Keywords:  sd59 
Cc:  Merged in:  
Authors:  Martin Albrecht  Reviewers:  Volker Braun, William Stein 
Report Upstream:  N/A  Work issues:  
Branch:  18ddc6d (Commits, GitHub, GitLab)  Commit:  18ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc 
Dependencies:  Stopgaps: 
Description
sage: R.<x,y> = QQ[] sage: n=1000; f = x^n; f.subs(x = x^n) x^1000000 sage: n=100000; f = x^n; f.subs(x = x^n) x^1410065408*y^2
Attachments (1)
Change History (28)
comment:1 Changed 11 years ago by
Stopgaps:  → todo 

comment:2 Changed 11 years ago by
comment:3 Changed 11 years ago by
By the way, this bug was quickly hit by Ben Hutz, who is doing research in arithmetic dynamics, which involves dynamics of *iterating* maps.
comment:4 Changed 11 years ago by
Authors:  → Martin Albrecht 

Status:  new → needs_review 
comment:5 Changed 11 years ago by
I am not sure what I am supposed to do about this stopgap business.
comment:6 Changed 11 years ago by
Status:  needs_review → needs_work 

REFEREE REPORT:
This looks great except for one little thing. Can you give examples to illustrate the
max_degree_per_variable
parameter in the Pythoncallable functions that define it.
Changed 11 years ago by
Attachment:  trac_12718_singular_overflow.patch added 

comment:7 Changed 11 years ago by
Status:  needs_work → needs_review 

comment:8 Changed 11 years ago by
I removed max_degree_per_variable
because it turns out to not work anyway.
comment:10 Changed 11 years ago by
Reviewers:  → Volker Braun, William Stein 

Status:  needs_review → positive_review 
Stopgaps:  todo 
comment:11 Changed 11 years ago by
In cdef int singular_polynomial_subst()
, did you verify that adding the sig_on()
conditions doesn't slow things down? If you need a function call to determine whether to call sig_on()
, it's probably faster to always call sig_on()
.
comment:12 Changed 11 years ago by
Never mind, the difference is hardly noticable anyway. Your way (with the conditional sig_on()
) seems to be very slightly faster.
comment:13 Changed 11 years ago by
Btw. it's the "standard" way we do it in the singular interface. I think Joel Mohler introduced it ages ago.
comment:14 Changed 11 years ago by
Status:  positive_review → needs_work 

On moufang (OSX 10.4 ppc32):
********************************************************************** File "/Users/buildbot/build/sage/moufang1/moufang_full/build/sage5.0.beta15/devel/sagemain/sage/rings/polynomial/multi_polynomial_libsingular.pyx", line 3154: sage: n=1000; f = x^n; f.subs(x = x^n) Exception raised: Traceback (most recent call last): File "/Users/buildbot/build/sage/moufang1/moufang_full/build/sage5.0.beta15/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/Users/buildbot/build/sage/moufang1/moufang_full/build/sage5.0.beta15/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/Users/buildbot/build/sage/moufang1/moufang_full/build/sage5.0.beta15/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_61[28]>", line 1, in <module> n=Integer(1000); f = x**n; f.subs(x = x**n)###line 3154: sage: n=1000; f = x^n; f.subs(x = x^n) File "multi_polynomial_libsingular.pyx", line 3240, in sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular.subs (sage/rings/polynomial/multi_polynomial_libsingular.cpp:21411) raise OverflowError("Exponent overflow (%d)."%(degree)) OverflowError: Exponent overflow (1000000). ********************************************************************** File "/Users/buildbot/build/sage/moufang1/moufang_full/build/sage5.0.beta15/devel/sagemain/sage/rings/polynomial/multi_polynomial_libsingular.pyx", line 3157: sage: n=100000; f = x^n; f.subs(x = x^n) Expected: Traceback (most recent call last): ... OverflowError: Exponent overflow (10000000000). Got: Traceback (most recent call last): File "/Users/buildbot/build/sage/moufang1/moufang_full/build/sage5.0.beta15/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/Users/buildbot/build/sage/moufang1/moufang_full/build/sage5.0.beta15/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/Users/buildbot/build/sage/moufang1/moufang_full/build/sage5.0.beta15/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_61[29]>", line 1, in <module> n=Integer(100000); f = x**n; f.subs(x = x**n)###line 3157: sage: n=100000; f = x^n; f.subs(x = x^n) File "multi_polynomial_libsingular.pyx", line 2347, in sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular.__pow__ (sage/rings/polynomial/multi_polynomial_libsingular.cpp:16619) singular_polynomial_pow(&_p, self._poly, exp, _ring) File "polynomial.pyx", line 322, in sage.libs.singular.polynomial.singular_polynomial_pow (sage/libs/singular/polynomial.cpp:3976) File "singular.pyx", line 667, in sage.libs.singular.singular.overflow_check (sage/libs/singular/singular.cpp:6526) OverflowError: Exponent overflow (100000). **********************************************************************
comment:15 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

comment:16 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:17 Changed 9 years ago by
Milestone:  sage6.2 → sage6.3 

comment:18 Changed 9 years ago by
Branch:  → u/malb/trac_12718 

Commit:  → a35f3d18c57f087e99419ee47d89f4e170c2d23b 
Keywords:  sd59 added 
Status:  needs_work → needs_review 
A mere two years later … and I fixed those doctest failures.
New commits:
a35f3d1  catch overflows in f.subs() where f is a libsingular polynomial

comment:19 Changed 9 years ago by
Commit:  a35f3d18c57f087e99419ee47d89f4e170c2d23b → 38c07da8745a467c2669ee70adab4e5fbb927876 

comment:22 Changed 9 years ago by
I'm getting a bunch of doctest errors, including
sage t long src/sage/rings/polynomial/multi_polynomial_libsingular.pyx ********************************************************************** File "src/sage/rings/polynomial/multi_polynomial_libsingular.pyx", line 3279, in sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular.subs Failed example: try: f.subs(x = x^n) print "no overflow" except OverflowError: print "overflow" Expected: no overflow Got: x^1000000 no overflow
but really there is a bunch more. Did you run the tests?
comment:23 Changed 9 years ago by
Status:  needs_review → needs_work 

I did and they passed (I thought at least), but I'm now getting these, too. Damn.
comment:24 Changed 9 years ago by
Commit:  38c07da8745a467c2669ee70adab4e5fbb927876 → 3e8a09e700d9a83f84e1c2085818d6aea81b1515 

comment:25 Changed 9 years ago by
Commit:  3e8a09e700d9a83f84e1c2085818d6aea81b1515 → 18ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc 

Branch pushed to git repo; I updated commit sha1. New commits:
a35f3d1  catch overflows in f.subs() where f is a libsingular polynomial

4dfd393  Merge branch 'develop' into trac_12718

c9a1ebc  fixed SIGSEGV when calling subs on 0

38c07da  shut up Cython warnings about complicated declarations

5f84119  fixed some doctest failures

18ddc6d  we still need to run subst if self == 0 to allow ring changes

comment:26 Changed 9 years ago by
Status:  needs_work → needs_review 

Okay, figured out what went wrong:
 the doctest failure Volker posted was missed because I ran my last tests on 32bit not on 64bit, but it only shows on 64bit
 the other doctest failures were introduced in my last  seemingly innocent  fix
I've addressed these and ran doctests on one 64bit and one 32bit system. They passed.
comment:27 Changed 9 years ago by
Branch:  u/malb/trac_12718 → 18ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc 

Resolution:  → fixed 
Status:  needs_review → closed 
Ah, crap, we took care of the actual overflows but missed this one. I'll try to port our fix from
__pow__
over this weekend.