3
$\begingroup$

Given an analytic function $f(x)$. What is the best algorithm to find roots on the interval $[a,b]$ inside the radius of convergence> What is its complexity with respect to the length of input of the interval (i. e. length of numbers $a$ and $b$)? Does the work, section 4 give the bound for complexity of such algorithms?

Edit: zeros has to be real

Improve this question
$\endgroup$
6
  • $\begingroup$ It looks like we can use FFT, nlogn $\endgroup$
    – katago
    Commented Dec 21, 2023 at 16:08
  • $\begingroup$ @ katago, is this n a number, or the length of a number? $\endgroup$
    – poeaqnwgo
    Commented Dec 22, 2023 at 0:12
  • $\begingroup$ it is length of a number $\endgroup$
    – katago
    Commented Dec 22, 2023 at 10:35
  • 1
    $\begingroup$ @roignoirewg Just a rough idea, stick [a,b] together to form S1, then use e(nx) to test and obtain information of different scales to obtain the root distribution $\endgroup$
    – katago
    Commented Dec 24, 2023 at 9:00
  • 1
    $\begingroup$ What does it mean "given an analytic function $f$"? In the most general case it would mean that you have some procedure that produces the coefficients up to any degree of the power series expansion in any point. // Why does the encoding of $f$ not contribute to the input length? $\endgroup$
    – Lutz Lehmann
    Commented Jan 27 at 12:13

1 Answer 1

Reset to default
4
$\begingroup$

I don't know about optimality, but this seems to be a relatively recent survey:

Kravanja, Peter; Van Barel, Marc, Computing the zeros of analytic functions, Lecture Notes in Mathematics. 1727. Berlin: Springer. vii, 111 p. (2000). ZBL0945.65018.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .