I have implemented the Remez algorithm in Python where all calculations were done with the Python mpmath library. I have noticed that sometimes the $|E_{max}|$ and $|E_{min}|$ do not monotonically increase anymore but recurrently iterate over the same values. Mainly, my stopping condition $|E_{max}| - |E_{min}| < u$ where $u$ is round-off error of the working precision never occurs. Increasing the working precision of mpmath did not solve this behavior.

For all steps of the Remez algorithm, I use the default methods for obtaining solutions for each step: mpmath's LU decomposition for solving a linear system of equations, the secant method for root finding and golden section search for extrema. Is using different methods for the different steps, possibly more precise, will improve this behavior, or is there something else that I miss? Is my stopping criterion is practical or I must relax it for general use?

  • 2
    $\begingroup$ Have you verified that in the failing cases, neighboring peaks of the error function still have alternating signs? Sometimes search functions "overstep", leading to violations of this property. Also, some systems of equations can be very ill-conditioned, requiring precision on the order of a thousand bits when solving the system. How much did you increase the working precision? The stopping condition (basically, machine epsilon of the working precision) seems too tight, but I don't recall what I use in my own Remez code. $\endgroup$
    – njuffa
    Sep 26 '20 at 5:00
  • $\begingroup$ @njuffa Yes, I verified that the signs are alternating. I did not try thousands of bits, I tried up to 1000 bits. This is the impression that I had, the stopping condition is too tight. It works well with a relaxed stopping condition. (by "well" I mean it stops and does not recurrently iterate). $\endgroup$
    – Daniel
    Sep 26 '20 at 18:57
  • 2
    $\begingroup$ I use 1000 bits working precision by default. I looked at my stopping condition and it defaults to stop when the error peaks are levelized to three times the target precision, e.g. for a IEEE-754 double precision target it would stop when the relative error is levelized to about $10^{-50}$, as there is no practical benefit in continuing further. I am not aware of any hard & fast guidance about this, it is just a heuristic I adopted during 25 years working with Remez. In recent years I have invested effort into further tuning the coefficients from Remez to be machine efficient. $\endgroup$
    – njuffa
    Sep 26 '20 at 19:22
  • $\begingroup$ Thank you @njuffa for checking out. $\endgroup$
    – Daniel
    Oct 1 '20 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.