Finding the maximum of a real valued trigonometric polynomial I have been posting all over SE looking for a good method of finding the maximum of a trigonometric polynomial. A trigonometric polynomial is the sum of a set of sinusoids,

$$a_0 + \sum_{k = 1}^{N} a_k \cos(k \theta + \phi_k)$$

and can also be written in the form

$$ \sum_{k=-N}^{N} c_k \, e^{i k \theta} $$
where $c_k$ = $\bar{c}_{-k}$

Substituting $z = e^{i \theta}$ turns this into the typical form of a complex valued polynomial.

The method I am currently using is to take the find the roots of the derivative of the polynomial, then evaluate the original polynomial at these locations to find the maximum. While quite fast with MATLABs roots command, it is not quite fast enough.

I need a method where I can trade accuracy for speed. Does anyone know of any other fast methods? This is a similar problem to estimating the crest factor of a signal. In my problem $N$ ranges from 3 to 15.
This function is periodic with 2*pi and it it's highest frequency component is N times the fundamental frequency. As such it can be sampled at a rate of 1/2*N without losing information. However, there is no guarantee that sampling will hit the maximum or that maximum sampled value is close to the analog maximum. The likelihood of this increases drastically by oversampling, e.g sample 4*N or 8*N values. 

So one thing to try would be to basically calculate the function values on a equidistant grid of, say 8*N, values, locate the maximum and then do a binary search around the maximum until the desired accuracy is reached. 

Again there is no guarantee that this will ALWAYS work, however you can try it with a few actual data sets and see how much over sampling is required and whether this is actually faster than the root search.