POV-Ray : Newsgroups : povray.programming : Sturmian root solver Server Time
10 Dec 2024 03:39:49 EST (-0500)
  Sturmian root solver (Message 1 to 1 of 1)  
From: Bald Eagle
Subject: Sturmian root solver
Date: 26 Jul 2024 09:10:00
Message: <web.66a39f46734934b46563700825979125@news.povray.org>
Given that:

Sturm's theorem
The first complete root-isolation procedure results of Sturm's theorem (1829),
which expresses the number of real roots in an interval in terms of the number
of sign variations of the values of a sequence of polynomials, called Sturm's
sequence, at the ends of the interval. Sturm's sequence is the sequence of
remainders that occur in a variant of Euclidean algorithm applied to the
polynomial and its derivatives. When implemented on computers, it appeared that
root isolation with Sturm's theorem is less efficient than the other methods
that are described below.[3] Consequently, Sturm's theorem is rarely used for
effective computations, although it remains useful for theoretical purposes.

https://en.wikipedia.org/wiki/Real-root_isolation#Sturm's_theorem

And IIRC, we've had some issues concerning the current Sturmian root solver,

Maybe we ought to take a look into using the following:
SLV, ANewDsc:

The implementation of this algorithm appears to be more efficient than any other
implemented method for computing the real roots of a polynomial, even in the
case of polynomials having very close roots (the case which was previously the
most difficult for the bisection method).

https://arxiv.org/pdf/1308.4088

https://oaktrust.library.tamu.edu/bitstream/handle/1969.1/186132/JordanLamkin_EH-CSCE_honors_thesis.pdf?sequence=1&isAl
lowed=y

https://github.com/JDLamkin/Curve-Intersect


- BE


Post a reply to this message

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