Literature Notes

[rparini]

Improving derivative-free case

When df is not provided we currently approximate it using a finite difference method

cxroots/cxroots/root_counting.py

Lines 197 to 204 in 1b0c859

	if df is None:
	df = numdifftools.Derivative(f, order=df_approx_order)
	# df = lambda z: scipy.misc.derivative(f, z, dx=1e-8, n=1, order=3)
	# Too slow
	# import numdifftools.fornberg as ndf
	# ndf.derivative returns an array [f, f', f'', ...]
	# df = np.vectorize(lambda z: ndf.derivative(f, z, n=1)[1])

Is there a better way of doing this? I feel like knowing f is complex analytic should let us do something more clever but not sure what. I've seen literature involving contour integrations to do this (and I implemented an approach in the cxroots.derivative.cx_derivative function) but integration can involve a lot of function evaluations. Possibly relevant reading:

• Numerical Differentiation of Analytic Functions, Fornberg 1981

Alternatively, perhaps we could take a different approach to rootfinding that avoids approximating df when it is not provided. Possibly relevant reading:

• Computing zeros of analytic functions in the complex plane without using derivatives, 2006
• A Derivative-Free Algorithm for Computing Zeros of Analytic Functions
  
• A Numerical Method for Locating the Zeros of an Analytic Function suggests evaluating ln(f(z))

Cluster handling

Can we improve how we handle clusters of roots?

• On Locating Clusters of Zeros of Analytic Functions