Re: remez, chebyshev polynomial approximation

From: Brian Budge (brian.budge_at_[hidden])
Date: 2023-08-25 19:20:57

Thanks John.  I have indeed found the remez tools very useful.  Your idea
of approximate in terms of x^2 is a good one.  I think this might apply in
some cases for odd powers by transforming the function and dividing
everything by x (but with the caveat that you might create singularities).

Thanks again,
  Brian

On Fri, Aug 25, 2023 at 10:24 AM John Maddock via Boost <
boost_at_[hidden]> wrote:

> 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.
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>