Add ModAB root finding method #1148
Description
https://github.com/mathnet/mathnet-numerics/tree/master/src/Numerics/RootFinding
Feature description
This is a new and extremely efficient bracketing root-finding algorithm. It combines initial bisection steps with Anderson-Bjork's (AB) steps to achieve superlinear convergence (e.i. = 1.7-1.8), preserving optimality in worst case poorly behaved functions. ModAB uses clever method switching criteria, based on actually measuring the function linearity. According to the benchmarks, it significantly outperforms "classical" algorithms like ITP, Brent and Ridders:
| Method | bs | fp | mfp | ill | AB | ITP | mAB | Rid | Bre |
|---|---|---|---|---|---|---|---|---|---|
| SUM | 4544 | 8187 | 2525 | 2951 | 3140 | 2897 | 2262 | 2900 | 1721 |
| AVE | 48,4 | 89,0 | 27,4 | 32,1 | 34,1 | 31,5 | 24,6 | 31,5 | 18,7 |
| MAX | 51 | 202 | 202 | 202 | 202 | 53 | 82 | 138 | 52 |
Legend:
bs – Bisection method
fp – False position
mfp – Modified false position
ill – Illinois method
AB – Anderson-Bjork
ITP – Interpolate, truncate, project
mAB – Modified Anderson-Bjork (new)
Rid – Ridders
Brе – Brent
More detailed results are provided here:
https://github.com/Proektsoftbg/Numerical/blob/main/Numerical.Benchmark/doc/Root/Root-tests.pdf
Alternatives considered
No response
Additional context
The algorithm is presented in this paper:
https://iopscience.iop.org/article/10.1088/1757-899X/1276/1/012010
Here is the C# source code:
https://github.com/Proektsoftbg/Numerical/blob/main/Numerical/Solver/ModAB.cs
The algorithm is currently implemented in Calcpad, Jacob Willam's NASA/JSC root-fortran and Julia/NonlinearSolve.jl. Currently, implementation in ROOT.CERN and SciPy is in progress.