Multiple exchange algorithm heuristics can fail when Haar condition is not fulfilled (from gforge #17200)
Imported issue: Initially reported by @chevilla in https://gforge.inria.fr/tracker/?group_id=1015&aid=17200
The following example enters an infinite loop:
p=remez(1,[|0, 4, 7, 9, 10, 11, 12|],[-163b-6;489b-6],1 / erf(-861b-6 + x),2621b-19,[13b-61;13b-59]);
Indeed, this example reveal a funny phenomenon: after a few iteration of the exchange algorithm where it seems to converge, the algorithm enters a pseudo-cycle of length 4, with roughly these characteristics:
eps = 1.90e-17, norm = 9.15e-17, pseudo-alternation pattern: [1, 1, -1, -1, 1, -1, 1, -1]
eps = 2.04e-17, norm = 2.2e-17, pseudo-alternation pattern: [1, -1, -1, -1, 1, -1, 1, -1]
eps = 2.045e-17, norm = 2.1e-17, pseudo-alternation pattern: [1, -1, -1, -1, 1, -1, 1, -1]
eps = 2.05e-17, norm = 2.08e-17, pseudo-alternation pattern: [1, -1, -1, -1, 1, -1, 1, -1]
and then again: eps = 1.90e-17, etc.
Indeed, everything seems to go well, but when the polynomial comes too close to the function, the pseudo-alternating property changes, which combined to the multipoint exchange strategy has the effect of lowering eps.