Add modified Anderson Bjork's algorithm for solving nonlinear equations

[Proektsoftbg]

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	4176	7709	2089	2684	2700	2581	1227	1990	2625
AVERAGE	46	85	23	29	30	28	13	22	29
MAX	48	200	71	200	200	50	48	78	133

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.

[dpiparo]

Hi, interesting. What would be the added value of having this algorithm in ROOT wrt having it as an external library, usable from ROOT in Python and C++?

[Proektsoftbg]

ROOT::Math::RootFinder uses BISECTION, FALSE_POS and BRENT from GSL. ModAB does the same, but much faster. Having this in the library will make it easy and handy for everyone who uses ROOT to benefit from its advantages. Having it as an external library will make it hard to find it, install and include into his code.

After adding this algorithm to Julia, they did some benchmarks. ModAB performed 1.4 times better than Ridder's and ITP and 1.7 times than Brent. For any library, I would always prefer to have faster and more efficient method on hand at equal other parameters.

SciML Performance Benchmarks (times in ms)

Function	Roots.jl	Alefeld	Bisection	Brent	Falsi	ITP	Ridder	ModAB
Wilkinson-like polynomia	12	6,3	5,7	2,3	34,5	2,7	3,1	1,8
sin(x) - 0,5x	18,5	12,5	9,2	5,6	14,6	4	3,6	2,6
exp(x) - 1 - x - x²/2	19,7	22,9	9,2	6,2	482,3	4,2	4,7	3
1/(x-0,5) - 2	12,9	3,9	5,7	2,6	73,5	3,7	2,2	1,7
log(x) - x + 2	19,1	16,5	11,2	4,7	26,2	5,1	4,6	3,8
sin(20x) + 0,1x	16,4	21,1	11,7	4,9	8,5	4,5	7,8	3,9
x³ - 2x² + x	12,9	5,3	5,6	2,3	81,5	3,1	2,3	1,7
x·sin(1/x) - 0,1	20	FAIL	10,5	9,4	16,3	4,2	3,3	3,8
Total	131,5	88,5	68,8	38	737,4	31,5	31,6	22,3
Relative	5,90	3,97	3,09	1,70	33,07	1,41	1,42	1

* as implemented in NonlinearSolve.jl

[dpiparo]

This looks interesting @Proektsoftbg. Would you be interested in contributing this algorithm in C++ to ROOT, accompanied by tests and a table similar to the one above but using the root finders ROOT current provides?

[Proektsoftbg]

@dpiparo Yes, sure. I'd love to. C++ was my favorite language before C# came. Let me translate the code to C++ first and perform some similar benchmarks. Then I will come back with the code and the results to discuss further. I will publish it to my repo first so that everyone can download and try it. :)