POV-Ray : Newsgroups : povray.advanced-users : Sturmian root solver : Re: Sturmian root solver Server Time
25 May 2024 03:27:28 EDT (-0400)
  Re: Sturmian root solver  
From: William F Pokorny
Date: 12 Aug 2019 06:02:31
Message: <5d513937$1@news.povray.org>
On 8/11/19 3:59 PM, Bald Eagle wrote:
> So, I was following a branching path of internet tangenting, and came across
> this little blurb.
> https://en.wikipedia.org/wiki/Real-root_isolation
> The first complete real-root isolation algorithm results from Sturm's theorem
> (1829). However, when real-root-isolation algorithms began to be implemented on
> computers it appeared that algorithms derived from Sturm's theorem are less
> efficient than those derived from Descartes' rule of signs (1637).
> Perhaps that's not the whole story - or there's some licensing issue with the
> Descarte-based algorithm, or ....?
It's not the whole, complicated story.

The statement is not necessarily true for low orders and positive roots 
only realm where we play. We also have frequent effective root 
multiplicities and want to run on float hardware - both complications 
most solver methods avoid up front.

That said, I posted in June to p.programming some details of a method I 
have coded up in tcl one might call a:

Descartes' rule of signs
Budan-Fourier theorem
Vincent's theorem
Collins and Akritas 1976 (and many following papers(1))
Sturm-chain for root counts, but not isolation.
Ruffini-Horner / Taylor-Shift


(1) - Mostly because I learned about Budan / Vincent from these not 
because I'm using the continued fraction stuff.

To that composite method we add the idea of using ray-equation 
generation in place of the traditional Mobius transforms - for much 
better accuracy while isolating roots. The tcl implementation looks good 
to me thus far.  Unsure about performance in the end as still playing 
with details like how to most efficiently evaluate the sign changes 
while always maintaining the original coefficient sign information. 
Anyway, I'm hopeful for something better - mostly for accuracy not 
performance concerns. If the current promise holds, it will be using 
sign changes in addition to Sturm's theorem(2,3).

Aside: Sturm's method depends on sign changes too.


Bill P.

(2) - Our Sturm implementation is really a Sturm bisection / 
Regula-Falsi method with a kind of chain fuzzing (in master on by 
default except in my updated solver branch where it's on only where 
needed). The fuzzing or dumbing down can help with some root 
multiplicities at the cost of isolation accuracy/ability.

(3) - Almost all Sturm implementations derive the Sturm chain in a 
traditional eqn/derivative -remainder etc...way. Sturm's theorom is more 
general having only certain requirements for the chain and it's 
evaluation results. I don't have it in front of me, but I found in an 
old book by L. E. Dickson a direct method for calculating the depressed 
quartic sturm chain (a depressed cubic/quartic equation is the basis for 
cubic and quartic solvers). Not tried an implementation, but seeing such 
a thing got me thinking about perhaps implementing at least the bottom 
parts of the sturm chain as a state machine or similar instead of 
repeated blind evaluations of those equations. Feels like it should be 
doable & probably at better accuracy. I don't know though, maybe too 
obscure to be worth the bother practically. Plus I've got lots of work 
to finish just what I already have going...

Post a reply to this message

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.