I'm looking for an efficient method to find all the roots of a function f on an interval [a,b]. 
The problem I have is that all the nice methods from scipy.optimize require either that f(a) and f(b) have different signs, or that I provide an initial guess x0, but I know nothing about my roots before running the code.
Note: The function f is smooth (at least C1), and doesn't have a pathological behaviour [nothing like sin(1/x)]. However, it requires building a matrix A(x) and finding its eigenvalues, and is therefore time-consuming. It is expected to have between 0 and 10 roots on [a,b], whose position is completely arbitrary. I can't afford missing any of them (e.g. I can't take 100 initial guesses x0 and just hope that i'll catch all the roots).
I was thinking about implementing something like this:

Find all the extrema {m_1, m_2.., m_k} of f with scipy.optimize [maybe fmin, but I don't know which method is the most efficient]:


Search for a minimum m_1 starting from point a [initial guess for gradient algorithm]
Search for a maximum m_2 starting from point m_1 + dx [forcing the gradient algorithm to go forward]
Search for a minimum m_3...

If two consecutive extrema m_i and m_(i+1) have opposite signs, apply brentq on interval [m_i, m_(i+1)] to find a root.



Is there a better way of solving this problem?
If not, are fmin and brentq the best choices among the scipy.optimize library in order to minimize the number of calls to my function f?
Depends on your function, but it might be possible to solve symbolically using SymPy. That would give all roots. It can find eigenvalues symbolically if necessary.
Finding all extrema is the same as finding all roots of the derivative of your function, so it won't be any easier than finding all roots (as WarrenWeckesser mentioned).
Finding all roots numerically will require using knowledge about the function. As a simple example, say you knew some minimum spacing between roots. You could try to recursively partition the interval and find roots in each. Stop after finding the maximum number of roots. But if the spacing is small, this could require many function evaluations (e.g. in the worst case when there are zero roots). The more constraints you can impose, the more you can cut down on function evaluations.
Finding multiple roots on an interval with Python