[julia-users] Re: Remez algorithm
super On Thursday, June 16, 2016 at 3:22:52 AM UTC-4, Simon Byrne wrote: > > I realise this is a bit late to the party, but in case anyone is still > interested (or happens to be searching in future), I've created: > https://github.com/simonbyrne/Remez.jl > > The code is mostly based on some code by ARM: > > https://github.com/ARM-software/optimized-routines/blob/master/auxiliary/remez.jl > but updated for newer Julia versions, and built into a package. > > On Tuesday, 17 June 2014 17:11:22 UTC+1, Hans W Borchers wrote: >> >> That is right. The Remez algorithm finds the minimax polynomial >> independent of any given prior discretization of the function. >> >> For discrete points you can apply LP or an "iteratively reweighted least >> square" approach that for this problem converges quickly and is quite >> accurate. Implementing it in Julia will only take a few lines of code. >> >> See my discussion two years ago with Pedro -- from the *chebfun* project >> -- about why Remez is better than solving this problem as an optimization >> task: >> >> http://scicomp.stackexchange.com/questions/1531/the-remez-algorithm >> >> You'll see that the Remez algorithm gets it slightly better. >> >> >> On Tuesday, June 17, 2014 5:12:21 PM UTC+2, Steven G. Johnson wrote: >>> >>> Note that Remez algorithm can be used to find optimal >>> (minimax/Chebyshev) rational functions (ratios of polynomials), not just >>> polynomials, and it would be good to support this case as well. >>> >>> Of course, you can do pretty well for many functions just by sampling at >>> a lot of points, in which case the minimax problem turns into an >>> finite-dimensional LP (for polynomials) or a sequence of LPs (for rational >>> functions).The tricky "Remez" part is finding the extrema in order to >>> sample at the optimal points, as I understand it. >>> >>
[julia-users] Re: Remez algorithm
I realise this is a bit late to the party, but in case anyone is still interested (or happens to be searching in future), I've created: https://github.com/simonbyrne/Remez.jl The code is mostly based on some code by ARM: https://github.com/ARM-software/optimized-routines/blob/master/auxiliary/remez.jl but updated for newer Julia versions, and built into a package. On Tuesday, 17 June 2014 17:11:22 UTC+1, Hans W Borchers wrote: > > That is right. The Remez algorithm finds the minimax polynomial > independent of any given prior discretization of the function. > > For discrete points you can apply LP or an "iteratively reweighted least > square" approach that for this problem converges quickly and is quite > accurate. Implementing it in Julia will only take a few lines of code. > > See my discussion two years ago with Pedro -- from the *chebfun* project > -- about why Remez is better than solving this problem as an optimization > task: > > http://scicomp.stackexchange.com/questions/1531/the-remez-algorithm > > You'll see that the Remez algorithm gets it slightly better. > > > On Tuesday, June 17, 2014 5:12:21 PM UTC+2, Steven G. Johnson wrote: >> >> Note that Remez algorithm can be used to find optimal (minimax/Chebyshev) >> rational functions (ratios of polynomials), not just polynomials, and it >> would be good to support this case as well. >> >> Of course, you can do pretty well for many functions just by sampling at >> a lot of points, in which case the minimax problem turns into an >> finite-dimensional LP (for polynomials) or a sequence of LPs (for rational >> functions).The tricky "Remez" part is finding the extrema in order to >> sample at the optimal points, as I understand it. >> >
[julia-users] Re: Remez algorithm
Note that Remez algorithm can be used to find optimal (minimax/Chebyshev) rational functions (ratios of polynomials), not just polynomials, and it would be good to support this case as well. Of course, you can do pretty well for many functions just by sampling at a lot of points, in which case the minimax problem turns into an finite-dimensional LP (for polynomials) or a sequence of LPs (for rational functions).The tricky Remez part is finding the extrema in order to sample at the optimal points, as I understand it.
[julia-users] Re: Remez algorithm
That is right. The Remez algorithm finds the minimax polynomial independent of any given prior discretization of the function. For discrete points you can apply LP or an iteratively reweighted least square approach that for this problem converges quickly and is quite accurate. Implementing it in Julia will only take a few lines of code. See my discussion two years ago with Pedro -- from the *chebfun* project -- about why Remez is better than solving this problem as an optimization task: http://scicomp.stackexchange.com/questions/1531/the-remez-algorithm You'll see that the Remez algorithm gets it slightly better. On Tuesday, June 17, 2014 5:12:21 PM UTC+2, Steven G. Johnson wrote: Note that Remez algorithm can be used to find optimal (minimax/Chebyshev) rational functions (ratios of polynomials), not just polynomials, and it would be good to support this case as well. Of course, you can do pretty well for many functions just by sampling at a lot of points, in which case the minimax problem turns into an finite-dimensional LP (for polynomials) or a sequence of LPs (for rational functions).The tricky Remez part is finding the extrema in order to sample at the optimal points, as I understand it.
