Real-Root Isolation

[Ani J]

Is it possible to use SymPy library to get intervals (with rational endpoints) such that there is exactly one root in the interval? I would like to use an implementation of RRI algorithm for my purpose. I believe that the interval function does this. Is this correct? Is it guaranteed that the output intervals are guaranteed to not have any common points?

[Chris Smith]

I strongly suspect that the roots returned by `Poly.intervals` have only one root in them (by definition). If you use  `refine_root(lo,hi,eps)` to refine the root bounds to arbitrary width and give it an interval in which there is more than one root, it will raise an error.

/c

[Aaron Meurer]

Yes, this is the case. The documentation for this method could perhaps
be improved, but the key word is "isolating", meaning each interval
contains exactly one root. You can also read more about the algorithm
that is referenced in the docstring
https://en.wikipedia.org/wiki/Vincent%27s_theorem

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/807f8910-040d-475b-91b6-a5002cedeea0n%40googlegroups.com.

[Ani J]

Oh! I see, but i believe that the intervals overlap on the endpoints, is it possible to make the intervals completely disjoint??

For example consider the following program:

• from sympy import Poly
• from sympy.abc import x
• from sympy import div, QQ
• p = Poly(x**6 + 19/5*x**5 + 131/50*x**4 - x**2 - 19/5*x - 131/50, x, domain='QQ')
• p.intervals()

The intervals that this outputs is: [((-3, -2), 1), ((-1, -1), 1), ((-1, 0), 1), ((1, 1), 1)]

Here we can see that the point -1 is a common endpoint between the second and 

the third term. Is it possible to enforce that there be no common point?

Best

[Aaron Meurer]

I don't know if there's an existing option to do this. It seems like
it would be useful. You can always lower the eps to make the intervals
smaller:

>>> Poly(x**6 + 19/5*x**5 + 131/50*x**4 - x**2 - 19/5*x - 131/50, x, domain='QQ').intervals(eps=0.1)
[((-29/10, -26/9), 1), ((-1, -1), 1), ((-10/11, -9/10), 1), ((1, 1), 1)]

Aaron Meurer

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/884eb7ff-0762-4771-a81f-930c13dada2dn%40googlegroups.com.

[Ani J]

Yes, this seems like a good option, so keep reducing eps in a while loop until the endpoints of all intervals are different, right?

[Aaron Meurer]

I'm not sure if it's enough to just take the minimum length of the
intervals that overlap and set eps to something smaller than that.
Someone more familiar with the inner workings of the algorithm would
have to verify whether that would work or if it could still leave
intersecting endpoints.

IMO, we should just fix the function to not return intersecting
endpoints in the first place. The intervals aren't really isolating if
they intersect.

Aaron Meurer

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/c987974b-cf39-4c8a-ad0a-579b61778513n%40googlegroups.com.

[Ani J]

It doesn't look like just taking the minimum length works.

Consider the following program:

• from sympy import Poly
• from sympy.abc import x

• from sympy import div, ZZ, QQ, RR

• p = Poly(x**6 + 19/5*x**5 + 131/50*x**4 - x**2 - 19/5*x - 131/50, x, domain='QQ')

• print(p.intervals())
• print(p.intervals(eps=0.5))

like just taking the minimum length works. The first output is: [((-3, -2), 1), ((-1, -1), 1), ((-1, 0), 1), ((1, 1), 1)]

Here the minimum interval length (>0) is 1. Even using 0.5 as the interval length in the next line prints: [((-3, -14/5), 1), ((-1, -1), 1), ((-1, -4/5), 1), ((1, 1), 1)]

but this has -1 as the common endpoint between the second and the third interval.

It would be great if the intervals have different endpoint. For now, I just start a while loop with eps=1 and keep dividing eps by 2, 

until I get different endpoints. Hope this works for now.

Best

[Oscar Benjamin]

On Tue, 21 May 2024 at 22:02, Aaron Meurer <asme...@gmail.com> wrote:
>
> IMO, we should just fix the function to not return intersecting
> endpoints in the first place. The intervals aren't really isolating if
> they intersect.

For rational roots the intervals are of length 0. For irrational roots
the root lies in the interior of the interval. In other words what is
returned is a set of individual rational points and open intervals on
the real line. An open interval might be bounded by one of the
rational points but they do not intersect because the interval does
not contain its boundary.

--
Oscar

[Ani J]

For rational roots the intervals may not be of length 0. Consider the following program:

• from sympy import Poly
• from sympy.abc import x

• from sympy import div, ZZ, QQ, RR
• print(Poly(4*x**2 - 9, x, domain='QQ').intervals())

The polynomial 4x^2 - 9 has rational roots, whereas the output of the print statement is: [((-2, -1), 1), ((1, 2), 1)]

All intervals here are of length more than 0. 

It would be great if in general it is possible that the endpoints of different intervals are never the same. Because,

 in my use case, I would like to use the points between the endpoints of two consecutive intervals and not inside any

 interval to find out the sign of the polynomial. For example., with the above two intervals (-2,-1), (1,2) , I would use

 the points -3,0,3 note that all points are outside the intervals and lie in particular regions not in the intervals. 

 I would like to use these points to find out the sign of the polynomial (4x^2-9) in my use case. It would be great if

 the tool itself gives separate intervals.

Thanking you

Best

[Aaron Meurer]

Ah, I was afraid of that. Looking at the code, I'm not sure if the
algorithm provides a better way than continually refining with smaller
epsilon until you get a separation, but I don't know the details of
the algorithm so that could be wrong. I will note that you can use
refine_root() once you have your intervals to just refine a single
interval, which would at least be a little more efficient.

Aaron Meurer

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/a97ce484-8cbf-4b1f-934f-ae7bd908c3adn%40googlegroups.com.

[Oscar Benjamin]

On Wed, 22 May 2024 at 00:23, Ani J <ani...@gmail.com> wrote:
>
> The polynomial 4x^2 - 9 has rational roots, whereas the output of the print statement is: [((-2, -1), 1), ((1, 2), 1)]
> All intervals here are of length more than 0.
> It would be great if in general it is possible that the endpoints of different intervals are never the same. Because,
> in my use case, I would like to use the points between the endpoints of two consecutive intervals and not inside any
> interval to find out the sign of the polynomial. For example., with the above two intervals (-2,-1), (1,2) , I would use
> the points -3,0,3 note that all points are outside the intervals and lie in particular regions not in the intervals.
> I would like to use these points to find out the sign of the polynomial (4x^2-9) in my use case. It would be great if
> the tool itself gives separate intervals.

See the function _find_poly_sign_univariate in
https://github.com/sympy/sympy/issues/26177

That function finds points where a univariate polynomial is nonzero
that separate all roots.

--
Oscar

[Ani J]

Thank you for the quick response. 

Yes, it looks like refine_root() does the job more efficiently. Thank you for the note.

I am facing issues in getting _find_poly_sign_univariate function to work. 

When I run from sympy import find_poly_sign, I get the following error: 

ImportError: cannot import name 'find_poly_sign' from 'sympy' (/path_to_python/python3.8/site-packages/sympy/__init__.py)

The documentation of SymPy here does not seem to have this function. Would be great to get some pointers on how to import
the function in the code.

Best

[Oscar Benjamin]

On Wed, 22 May 2024 at 01:10, Ani J <ani...@gmail.com> wrote:
>
> Thank you for the quick response.
>
> Yes, it looks like refine_root() does the job more efficiently. Thank you for the note.
>
> I am facing issues in getting _find_poly_sign_univariate function to work.
> When I run from sympy import find_poly_sign, I get the following error:
>
> ImportError: cannot import name 'find_poly_sign' from 'sympy' (/path_to_python/python3.8/site-packages/sympy/__init__.py)
>
> The documentation of SymPy here does not seem to have this function. Would be great to get some pointers on how to import
> the function in the code.

The function is not part of SymPy. The code for the function is in the
issue I linked:
https://github.com/sympy/sympy/issues/26177

You would have to copy the code from there to use it.

--
Oscar

[Chris Smith]

You might try

def distinct_intervals(p): P=Poly(p) iv = P.intervals() print(iv) for i in range(len(iv)-1): (lo,hi),n=iv[i] (LO,HI),N=iv[i+1] while hi==LO: if lo!=hi: (lo,hi),n=iv[i]=P.refine_root(lo,hi,(hi-lo)/2),n else: assert LO!=HI (LO,HI),N=iv[i+1]=P.refine_root(LO,HI,(HI-LO)/2),N return iv >>> distinct_intervals(Poly(x**6 + 19/5*x**5 + 131/50*x**4 - x**2 - 19/5*x - 131/50, x, domain='QQ')) [((-3, -2), 1), ((-1, -1), 1), ((-10/11, -9/10), 1), ((1, 1), 1)]

/c

​