Opened 5 years ago

Closed 3 years ago

#17703 closed defect (wontfix)

use giac for symbolic multivar gcd

Reported by: rws Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: symbolics Keywords:
Cc: burcin Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by rws)

One solution to the bug in #10284 is to use Singular-factory for symbolic multivar gcd. The factory code seems better maintained than Pynac so at least provide the alternative.

However, giac seems much faster: https://groups.google.com/forum/?hl=en#!topic/sage-devel/Wp6ZRoXFYVA

Change History (5)

comment:1 Changed 4 years ago by rws

  • Description modified (diff)
  • Summary changed from use Singular-factory for symbolic multivar gcd to use Singular-factory or giac for symbolic multivar gcd

comment:2 Changed 4 years ago by rws

  • Cc burcin added
  • Milestone changed from sage-6.5 to sage-7.3
  • Summary changed from use Singular-factory or giac for symbolic multivar gcd to use giac for symbolic multivar gcd

A development version of Pynac using Giac is twice as fast as Singular (used from ring polynomials for the example of #10284:

sage: u = var('u')
sage: v = var('v')
sage: w = var('w')
sage: x = var('x')
sage: y = var('y')
sage: z = var('z')
sage: e = 792*z^8*w^4*x^3*y^4*u^7 + 24*z^4*w^4*x^2*y^3*u^4 + \
264*z^8*w^3*x^2*y^7*u^5 + 198*z^4*w^5*x^5*y*u^6  + 110*z^2*w^3*x^5*y^4*u^6 \
- 120*z^8*w*x^4*u^6 - 480*z^5*w*x^4*y^6*u^8 - 720*z^7*x^3*y^3*u^7 + \
165*z^4*w^2*x^4*y*u^5 + 450*z^8*w^6*x^2*y*u^8 + 40*z^2*w^3*x^3*y^3*u^6 - \
288*z^7*w^2*x^3*y^6*u^6  + 250*z^6*w^4*x^2*y^4*u^8 + \
576*z^7*w^7*x^2*y^4*u^8  - 80*z^6*w^2*x^5*y^3*u^7 - 144*z^8*w^4*x^5*u^7 + \
120*z^4*w*x^2*y^6*u^6 + 320*z^5*w^5*x^2*y^7*u^8 + 192*z^7*w^6*x*y^7*u^6 - \
12*z^4*w^3*x^3*y^5*u^6  - 36*z^4*w^4*x^4*y^2*u^8 + 72*z^4*w^5*x^3*u^6  - \
20*z^2*w^2*x^4*y^5*u^8 + 660*z^8*w*x^2*y^4*u^6 + 66*z^4*w^4*x^4*y^4*u^4 + \
440*z^6*w^2*x^3*y^7*u^7  - 30*z^4*w*x^3*y^2*u^7 - 48*z^8*w^3*x^4*y^3*u^5 + \
72*z^6*w^2*x*y^6*u^4 - 864*z^7*w^3*x^4*y^3*u^8 + 480*z^7*w^4*x*y^4*u^7 + \
60*z^4*w^2*x^2*u^5 + 375*z^8*w^3*x*y*u^7 + 150*z^8*w^5*x*y^4*u^6 + \
180*z^6*x*y^3*u^5 + 216*z^6*w^3*x^2*y^3*u^6;
sage: d = e.diff(x)
sage: gcd(d,e)
u^4*z^2
sage: E = e.polynomial(QQ)
sage: D= e.diff(x)
sage: gcd(D,E)
u^4*z^2
sage: %timeit _=gcd(d,e)
100 loops, best of 3: 1.48 ms per loop
sage: %timeit _=gcd(d,e)
1000 loops, best of 3: 1.5 ms per loop
sage: %timeit _=gcd(D,E)
100 loops, best of 3: 3.06 ms per loop
sage: %timeit _=gcd(D,E)
100 loops, best of 3: 3.06 ms per loop
sage: %timeit _=gcd(D,E)
100 loops, best of 3: 3.05 ms per loop

EDIT: if you compare with timings versus the gcd over both a ring polynomial then it's even 6x.

Version 1, edited 4 years ago by rws (previous) (next) (diff)

comment:3 Changed 3 years ago by rws

  • Milestone changed from sage-7.3 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

GCD via giac is implemented in #20742. As long as giac is not a standard package, it will only be an option. If you want it, install giac with sage -i giac and then

sage -p pynac
make start

comment:4 Changed 3 years ago by rws

  • Status changed from needs_review to positive_review

comment:5 Changed 3 years ago by embray

  • Resolution set to wontfix
  • Status changed from positive_review to closed

Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).

Note: See TracTickets for help on using tickets.