Re: remez, chebyshev polynomial approximation

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

Yeah, nevermind the transform and divide by x idea :)  I may need to just
find other tools if I need the absolute best small polynomials in those
cases.

  Brian

On Fri, Aug 25, 2023 at 12:20 PM Brian Budge <brian.budge_at_[hidden]> wrote:

> 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
>>
>