search

simonbyrne / Remez.jl

Remez algorithm for computing minimax polynomial approximations
Other
38 stars 9 forks source link

Performance of finding rational approximations #9

Open oscardssmith opened 3 years ago

oscardssmith commented 3 years ago

I have been trying to find some rational approximations, but I am running into cases where ratfn_minimax is not halting in a reasonable amount of time.

As a reduced example, computing a pade approximation with a quintic numerator and denominator only takes .8 seconds, but with 6th degree coefficients, it takes almost a minute.

julia> @time ratfn_minimax(exp, (1,5), 5, 5, (x,y)->exp(-x*x));
  0.826685 seconds (4.99 M allocations: 271.503 MiB, 2.91% gc time, 55.26% compilation time)

julia> @time ratfn_minimax(exp, (1,5), 6, 6, (x,y)->exp(-x*x));
 56.748839 seconds (763.57 M allocations: 39.364 GiB, 3.67% gc time, 0.82% compilation time)

For my real use-case, I want an 8,8 approximation. Is there any specific reason why this should get so much slower as you ask for a higher degree approximation?

oscardssmith commented 3 years ago

Attached is a profile of the 60 second one. It seems like most of the time is in poly_eval. Is there a reason to not replace it's use with evalpoly? It seems like it might just be a worse version. Am I missing something? remez.jlprof.zip