Re: remez, chebyshev polynomial approximation

From: John Maddock (jz.maddock_at_[hidden])
Date: 2023-08-25 17:24:14

On 25/08/2023 14:54, Brian Budge via Boost wrote:
> Hi folks -
>
> I have a couple of questions regarding the math tools for polynomial
> approximation.  Context:  I'm interested in making fast math approximations
> that are also highly accurate.  These include standard functions, but also
> custom fits.
Please note that these tools were designed to be just good enough to get 
the job done for what we needed internally, that said, it's good to see 
them being used elsewhere.
> I've successfully used the chebyshev_transform and remez
> tools to make such approximations.  However, I know in many cases I could
> get better results.  So my questions are the following:
>
> 1. For the remez tool, how could we constrain e.g. odd or even powers of
> numerator, denominator, or both to zero?  This is common in highly accurate
> trig approximations for example.  Looking at the code, I suspect we'd need
> to change the degrees of freedom for the solver, but I don't know how
> straightforward it would be to make such a change (or if there are
> theoretical reasons why this couldn't work with the remez algorithm)
There's the obvious "generate an approximation in terms of x^2" 
workaround for even powers, constraining others would require hacking 
into the code quite substantially I suspect to fix some coefficients to 
zero.
> 2. Getting accurate results with chebyshev_transform requires the Crenshaw
> algorithm, which makes these approximations far slower than those I get
> from the remez tool.  Are there a class of polynomials where I could
> transform these to a standard Horner's or Estrin's scheme in a way that is
> numerically stable?  If so, any pointers to how to do that?

No... except of course a Chebyshev approximation "is a" polynomial, 
whether it's numerically stable is another matter.  If the goal is a 
polynomial, then I would tend to go with a minimax solution, and it will 
pretty much tell you right away whether it's stable or not.

Probably not helping much, John.