Opened 7 years ago

Closed 7 years ago

#17896 closed defect (duplicate)

Polred during exactification takes too long

Reported by: gagern Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: number fields Keywords: qqbar polred performance
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges


The following example comes from comment:27:ticket:16964 via comment:2:ticket:17886, with syntax for z discussed in ticket:17895.

sage: x,y = polygens(QQ,"x,y")
sage: p1 = x^5 + 6*x^4 - 42*x^3 - 142*x^2 + 467*x + 422
sage: p2 = p1(x=(x-1)^2)
sage: p3 = p2(x=x*y).resultant(p2,x).univariate_polynomial()
sage: p4, = [f[0] for f in p3.factor() if f[0].degree() == 80]
sage: ival = CIF((0.77, 0.78), (-0.08, -0.07))
sage: z, = [r for r in p4.roots(QQbar, False) if r in ival]
sage: %time z.exactify()

This exactification didn't complete in 6 hours. OK, the polynomial in question has degree 80, so this is quite some work, but nevertheless Mathematica can find a minimal polynomial for just this number in 0.2 seconds. There should be some way we can get at least into the less-than-a-minute range, although I don't know exactly how.

Perhaps we can drop the polred calls in qqbar?

Change History (3)

comment:1 Changed 7 years ago by gagern

  • Status changed from new to needs_review

This appears to be a duplicate of #15600.

comment:2 Changed 7 years ago by mmezzarobba

  • Milestone changed from sage-6.6 to sage-duplicate/invalid/wontfix
  • Status changed from needs_review to positive_review

comment:3 Changed 7 years ago by vbraun

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.