Opened 6 years ago
Last modified 5 years ago
#19362 needs_work enhancement
Improve refine_root()
Reported by:  jdemeyer  Owned by:  

Priority:  major  Milestone:  sage7.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: 
Description (last modified by )
In particular, allow both real and complex input. Also implement bisection if NewtonRaphson cannot be used.
Change History (20)
comment:1 Changed 6 years ago by
 Branch set to u/jdemeyer/ticket/19362
comment:2 Changed 6 years ago by
 Commit set to 3b34e49f73e7a0889d87aa43b26709c14e9b7492
 Status changed from new to needs_review
comment:3 Changed 6 years ago by
 Commit changed from 3b34e49f73e7a0889d87aa43b26709c14e9b7492 to 950eb84d640cb06b0d4ca8363845922713ec8fe6
Branch pushed to git repo; I updated commit sha1. New commits:
950eb84  Implement bisection

comment:4 Changed 6 years ago by
 Description modified (diff)
comment:5 Changed 6 years ago by
 Status changed from needs_review to needs_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 6 years ago by
 Commit changed from 950eb84d640cb06b0d4ca8363845922713ec8fe6 to 972f8e0e87ee7d3a06f82257ddce8804474b257d
Branch pushed to git repo; I updated commit sha1. New commits:
972f8e0  Once converging, keep converging

comment:7 Changed 6 years ago by
 Milestone changed from sage6.9 to sage6.10
 Status changed from needs_work to needs_review
comment:8 Changed 6 years ago by
 Commit changed from 972f8e0e87ee7d3a06f82257ddce8804474b257d to eb6155723e34093e12d3e945bf3acf84ddbac185
Branch pushed to git repo; I updated commit sha1. New commits:
eb61557  When smashing, stop converging

comment:9 Changed 6 years ago by
 Commit changed from eb6155723e34093e12d3e945bf3acf84ddbac185 to 7c689b6b7b94fb21dadec46499c0236675e93d95
Branch pushed to git repo; I updated commit sha1. New commits:
7c689b6  When converging, take the intersection of old and new interval

comment:10 Changed 6 years ago by
 Status changed from needs_review to needs_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 6 years ago by
 Dependencies changed from #19361 to #19361, #19364
comment:12 Changed 6 years ago by
 Commit changed from 7c689b6b7b94fb21dadec46499c0236675e93d95 to 8ab38c44e636f0020c5bb34022a8bd4ab7804068
comment:13 followup: ↓ 14 Changed 6 years ago by
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 6 years ago by
Replying to vdelecroix:
Did you notice that some code in
QQbar
actually duplicates this: method_real_refine_interval
/_complex_refine_interval
of theANRoot
class.
Yes, there are way too many reimplementations 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 6 years ago by
Making it support all use cases of the various existing implementations is also what makes it tricky.
comment:16 Changed 6 years ago by
 Commit changed from 8ab38c44e636f0020c5bb34022a8bd4ab7804068 to 9d5f99cf2d3ed36e6028785ac16dc8cbaf243405
Branch pushed to git repo; I updated commit sha1. New commits:
9d5f99c  Improve convergence check

comment:17 Changed 6 years ago by
What is the work which needs doing?
comment:18 Changed 6 years ago by
 Dependencies #19361, #19364 deleted
 Milestone changed from sage6.10 to sage7.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 6 years ago by
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 5 years ago by
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:
 the sign of
sgn(p(a)) * sgn(p(b)) = 1
 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).
New commits:
Move refine_root() to refine_root.pyx
Improve refine_root()