On 03/30/2018 08:21 AM, William F Pokorny wrote:
> 
...
> Bill P.

While studying the missing root problem I finished off some initial 
lower and upper root bound estimation code aimed at polysolve() 
performance. The update is at:

https://github.com/wfpokorny/povray/tree/fix/polynomialsolverAccuracy

The update is directly related to a sub-discussion of issue:

https://github.com/POV-Ray/povray/issues/236

Currently the upper bound method(d) is hard coded to run always. Longer 
term, and given I've found some POV-Ray objects such as blob already 
calculate a 'max_bounds' value, I'm thinking about a change to the 
Solve_Polynomial(), polysolve() calls to add a parameter where :

a) if > 0 value, we'd be passing a known upper bound for all roots.

b) if == 0,  we'd do what we do today.

c) if == -1, we'd run the original Cauchy's bound estimate method good 
for the lowest value root. In some applications, that first root might 
be all we need.

d) if == -2, we'd run an estimator based on Cauchy's method from a 2009 
paper(z) found via:

https://en.wikipedia.org/wiki/Properties_of_polynomial_roots#Other_bounds

and good for the upper bound of all roots.

There are better bound estimators, but all I've looked at are more 
complex - and several I don't understand. In any case I doubt we'd buy 
back the performance given our equation orders are tiny compared to that 
aimed at by the more generic solvers for which these better estimator 
were created. Many others also use complex numbers.

Bill P.

(z) - Had to tweak it slightly due two sor fails in testing. Due the 
surprise with sturm-cubic it's on my list to enable sturm-quadratic in 
Solve_Poly() to do some more testing.

Performance info:
------------ /usr/bin/time povray -j -wt1 -fn -p -d -c lemonSturm.pov

0)  master    30.22user 0.04system 0:30.89elapsed

9)  687f57b   19.44user 0.01system 0:20.06elapsed  -35.67%
10) 0f6afcc   14.77user 0.02system 0:15.36elapsed  -24.02%  -51.13%

Post a reply to this message