Opened 7 years ago

Last modified 6 years ago

#19362 needs_work enhancement

Improve refine_root()

Reported by: Jeroen Demeyer Owned by:
Priority: major Milestone: sage-7.1
Component: algebra Keywords:
Cc: Merged in:
Authors: Jeroen Demeyer Reviewers:
Report Upstream: N/A Work issues:
Branch: u/jdemeyer/ticket/19362 (Commits, GitHub, GitLab) Commit: 9d5f99cf2d3ed36e6028785ac16dc8cbaf243405
Dependencies: Stopgaps:

Status badges

Description (last modified by Jeroen Demeyer)

In particular, allow both real and complex input. Also implement bisection if Newton-Raphson cannot be used.

Change History (20)

comment:1 Changed 7 years ago by Jeroen Demeyer

Branch: u/jdemeyer/ticket/19362

comment:2 Changed 7 years ago by Jeroen Demeyer

Commit: 3b34e49f73e7a0889d87aa43b26709c14e9b7492
Status: newneeds_review

New commits:

2049f5aMove refine_root() to refine_root.pyx
3b34e49Improve refine_root()

comment:3 Changed 7 years ago by git

Commit: 3b34e49f73e7a0889d87aa43b26709c14e9b7492950eb84d640cb06b0d4ca8363845922713ec8fe6

Branch pushed to git repo; I updated commit sha1. New commits:

950eb84Implement bisection

comment:4 Changed 7 years ago by Jeroen Demeyer

Description: modified (diff)

comment:5 Changed 7 years ago by Jeroen Demeyer

Status: needs_reviewneeds_work
sage: from sage.rings.polynomial.refine_root import refine_root
sage: RIF = RealIntervalField(106)
sage: R.<x> = RIF[]
sage: pol = 10*x^6 - 10*x^2 + 1
sage: refine_root(pol, pol.derivative(), RIF(3/4,9/8), RIF)
Traceback (most recent call last):
...
ArithmeticError: cannot refine polynomial root (not enough steps?)

comment:6 Changed 7 years ago by git

Commit: 950eb84d640cb06b0d4ca8363845922713ec8fe6972f8e0e87ee7d3a06f82257ddce8804474b257d

Branch pushed to git repo; I updated commit sha1. New commits:

972f8e0Once converging, keep converging

comment:7 Changed 7 years ago by Jeroen Demeyer

Milestone: sage-6.9sage-6.10
Status: needs_workneeds_review

comment:8 Changed 7 years ago by git

Commit: 972f8e0e87ee7d3a06f82257ddce8804474b257deb6155723e34093e12d3e945bf3acf84ddbac185

Branch pushed to git repo; I updated commit sha1. New commits:

eb61557When smashing, stop converging

comment:9 Changed 7 years ago by git

Commit: eb6155723e34093e12d3e945bf3acf84ddbac1857c689b6b7b94fb21dadec46499c0236675e93d95

Branch pushed to git repo; I updated commit sha1. New commits:

7c689b6When converging, take the intersection of old and new interval

comment:10 Changed 7 years ago by Jeroen Demeyer

Status: needs_reviewneeds_work

I am going to continue working on this a bit more. If anybody feels like reviewing this code, let me know and I'll put up the current version for review.

comment:11 Changed 7 years ago by Jeroen Demeyer

Dependencies: #19361#19361, #19364

comment:12 Changed 7 years ago by git

Commit: 7c689b6b7b94fb21dadec46499c0236675e93d958ab38c44e636f0020c5bb34022a8bd4ab7804068

Branch pushed to git repo; I updated commit sha1. New commits:

388d495Add edges() and endpoints() methods to intervals
8c10c00Merge branch 't/19364/add_edges___method_to_rif_and_cif_elements' into t/19362/ticket/19362
8ab38c4Trim instead of bisect

comment:13 Changed 7 years ago by Vincent Delecroix

Did you notice that some code in QQbar actually duplicates this: method _real_refine_interval/_complex_refine_interval of the ANRoot class.

comment:14 in reply to:  13 Changed 7 years ago by Jeroen Demeyer

Replying to vdelecroix:

Did you notice that some code in QQbar actually duplicates this: method _real_refine_interval/_complex_refine_interval of the ANRoot class.

Yes, there are way too many re-implementations of this in Sage. My eventual goal is to replace all "real/complex root refining" code in Sage by this new refine_root() function. But I'm not there yet...

comment:15 Changed 7 years ago by Jeroen Demeyer

Making it support all use cases of the various existing implementations is also what makes it tricky.

comment:16 Changed 7 years ago by git

Commit: 8ab38c44e636f0020c5bb34022a8bd4ab78040689d5f99cf2d3ed36e6028785ac16dc8cbaf243405

Branch pushed to git repo; I updated commit sha1. New commits:

9d5f99cImprove convergence check

comment:17 Changed 7 years ago by John Cremona

What is the work which needs doing?

comment:18 Changed 7 years ago by Jeroen Demeyer

Dependencies: #19361, #19364
Milestone: sage-6.10sage-7.1

I don't really remember myself, I do remember that it wasn't ready. It was trickier than I initially estimated. I will need to look at it again.

comment:19 Changed 7 years ago by Marc Mezzarobba

You probably know that, but just in case: it is not strictly true that you cannot use the interval Newton method and must switch to bisection when the slope interval contains zero. Another option is to interpret 1/[-a,b] as a kind of ”projective interval” containing ∞ (which gives rise to two disjoint complex intervals after intersecting with the previous estimate, so you'll still need to deal with several pieces).

comment:20 Changed 6 years ago by Vincent Delecroix

IMHO, refine_root is a bad name. I would expect such function to refine an interval that is already known to contain a (possibly unique) root... What about isolating_interval_from_approximate_root or something similar?

On the other hand, there are some possible alternative in the real case that does not involve convergence of Newton algorithm (and might already be implemented elsewhere). Namely p has a unique root in an interval [a, b] if the following holds:

  1. the sign of sgn(p(a)) * sgn(p(b)) = -1
  2. the interval p'([a,b]) does not contain zero

It is also possible to replace 2 with Descartes rules of sign (which is a more expensive).

Note: See TracTickets for help on using tickets.