Muller's method

[fgittins]

What kind of problems is it mostly used for? Please describe.

Determining the roots of univariate complex functions. Muller's method is commonly used to determine the (quasi-normal) oscillation modes of neutron stars [1,2]. The algorithm only applies to univariate, scalar functions.

Describe the algorithm you’d like

The algorithm is quite simple and described well in Press et al. [3] (see also Wikipedia [4]).

To summarise: Muller's method is a generalisation of the secant method, with the key difference being that it uses quadratic interpolation across three points (as opposed to linear interpolation among two). Solving for the roots of a quadratic is trivial and allows the method to work for complex roots.

Other implementations to know about

There is an existing Julia implementation in Roots.jl [5] and a Fortran routine in IMSL [6]. I also started implementing this in the deprecated SimpleNonlinearSolve.jl (see my fork at [7]).

Notes

I suggested this algorithm before for SimpleNonlinearSolve.jl in #403 and worked on a (now closed) pull request (SciML/SimpleNonlinearSolve.jl#139).

References

[1] Kokkotas & Schutz (1992)
[2] Kruger, PhD Thesis (2016)
[3] Press et al. (2007), Sec. 9.5.2, p. 466
[4] Wikipedia, Muller's method
[5] Roots.muller
[6] IMSL Math/Library Users Manual, Zanly
[7] SimpleNonlinearSolve fork

[fgittins]

I'm closing this issue since it's a duplicate of #403. I'll move discussion over there.