search

scijs / poly-roots

Find all roots of a polynomial using the Jenkins-Traub method
18 stars 1 forks source link

Some coefficient combinations cause solver to hang #6

Open borismus opened 7 years ago

borismus commented 7 years ago

I haven't been able to track down exactly when this happens, but some coefficient arrays cause it to spin forever. For example [1, 0, 0] will do it, even though the solution should be x=0.

rreusser commented 7 years ago

Overall I think durand-kerner is probably a more robust (and certainly faster) method for this. I've had pretty good luck with it.

borismus commented 7 years ago

Thanks for the pointer (and the library in the first place). If this fails so clearly in such simple cases, might be worth considering pointing more prominently to durand-kerner, or providing more caveats.

rreusser commented 7 years ago

After a bit of digging, it seems like the problem is when the cauchy approximation returns a radius of exactly zero. It doesn't simply shift things over when deflating and gets into a loop. Likely culprit: reworking the logic to avoid goto/label in the js when translating goto-style fortran loops. 😑

For now, I've just replaced the readme with a deprecation warning and a pointer to durand-kerner, which is at the very least significantly faster and more robust. It didn't always succeed in separating nearby roots, but I have no reason to believe lowering the tolerance wouldn't trivially solve that.

Thanks for raising this though. Leaving it open for now. I'd be glad to get this working better, but it probably won't happen too soon.