Opened 7 years ago

Last modified 3 years ago

#17895 closed defect

Computing all roots is faster than computing a single one — at Initial Version

Reported by: gagern Owned by:
Priority: major Milestone: sage-8.9
Component: number fields Keywords: qqbar polynomial_root roots performance
Cc: sbrandhorst 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.

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: %time z1, = [r for r in p4.roots(QQbar, False) if r in ival]
CPU times: user 1.43 s, sys: 195 ms, total: 1.62 s
Wall time: 1.47 s
sage: %time z2 = QQbar.polynomial_root(p4, ival)
CPU times: user 1min 5s, sys: 212 ms, total: 1min 5s
Wall time: 1min 5s

The computation for z1 works reasonably well and completes in under 2 seconds, but the one for z2 takes over a minute on my system. Which I find really strange, since computing all roots and then choosing the right one should be more work, not less than just computing a single one. Should we change QQbar.polynomial_root to go via the list of all roots, or is there a better solution?

Change History (0)

Note: See TracTickets for help on using tickets.