REMEZ computational complexity

Can any body tell me the complexity means number of operations required by
the 
1. remezord algorithm to estimate the order of filter.
2. remez algorithm to calculate an N order filter's impulse response
(coefficients).

Thnaks in advance for the information.

"renaudin" <alsaeed86@gmail.com> wrote in message 
news:SfGdncEvNM8-mIzYnZ2dnUVZ_sydnZ2d@giganews.com...
> Can any body tell me the complexity means number of operations required by
> the
> 1. remezord algorithm to estimate the order of filter.
> 2. remez algorithm to calculate an N order filter's impulse response
> (coefficients).
>
> Thnaks in advance for the information.
>

Most of the estimates for filter order are simple expressions that take a 
single evaluation.  Thus, the number of operations is very small compared to 
computing a filter design.
It depends on the actual expression that's used.  I suppose you could figure 
it out from a description of remezord.  It says it uses:
Rabiner, L.R., and O. Herrmann, "The Predictability of Certain Optimum 
Finite Impulse Response Digital Filters," IEEE Trans. on Circuit Theory, 
Vol. CT-20, No. 4 (July 1973), pp. 401-408.

Running a filter design requires an N+1 point interpolation or, 
equivalently, the solution of a system of N+1 linear equations at each 
iteration.  The number of iterations can range from 2-3 for a filter of 
modest length *and* specifications to over 20 for longer filters with more 
stringent specifications.  So, it's not only the length of the filter but 
the specifications as well that drive the number of iterations.  I would say 
that the number of operations is quite dependent on the particular code 
because there are also searches and sorts to do at each iteration to decide 
where the next N+1 points lie in frequency.

To expand this discussion:

My own code that runs on a PC is good for filter lengths up to maybe 128 or 
so.  After that, numerical inaccuracies combine to thwart convergence.

Does anyone know of a readily available Remez program that will go to maybe 
length 1000 or greater?  That would be interesting...  I'm also interested 
in *how* it's done.

Fred 

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> schrieb im Newsbeitrag 
news:bpKdnS5FAP9PH4zYnZ2dnUVZ_sydnZ2d@centurytel.net...
>
> "renaudin" <alsaeed86@gmail.com> wrote in message 
> news:SfGdncEvNM8-mIzYnZ2dnUVZ_sydnZ2d@giganews.com...
>> Can any body tell me the complexity means number of operations required 
>> by
>> the
>> 1. remezord algorithm to estimate the order of filter.
>> 2. remez algorithm to calculate an N order filter's impulse response
>> (coefficients).
>>
>> Thnaks in advance for the information.
>>
>
> Most of the estimates for filter order are simple expressions that take a 
> single evaluation.  Thus, the number of operations is very small compared 
> to computing a filter design.
> It depends on the actual expression that's used.  I suppose you could 
> figure it out from a description of remezord.  It says it uses:
> Rabiner, L.R., and O. Herrmann, "The Predictability of Certain Optimum 
> Finite Impulse Response Digital Filters," IEEE Trans. on Circuit Theory, 
> Vol. CT-20, No. 4 (July 1973), pp. 401-408.
>
> Running a filter design requires an N+1 point interpolation or, 
> equivalently, the solution of a system of N+1 linear equations at each 
> iteration.  The number of iterations can range from 2-3 for a filter of 
> modest length *and* specifications to over 20 for longer filters with more 
> stringent specifications.  So, it's not only the length of the filter but 
> the specifications as well that drive the number of iterations.  I would 
> say that the number of operations is quite dependent on the particular 
> code because there are also searches and sorts to do at each iteration to 
> decide where the next N+1 points lie in frequency.
>
> To expand this discussion:
>
> My own code that runs on a PC is good for filter lengths up to maybe 128 
> or so.  After that, numerical inaccuracies combine to thwart convergence.
>
> Does anyone know of a readily available Remez program that will go to 
> maybe length 1000 or greater?  That would be interesting...  I'm also 
> interested in *how* it's done.
>
> Fred
>
Hello Fred,

I just increase the grid density, if the convergence of the remez is bad. It 
works quite well,
but for higher tap counts it takes a while ;-).

Gerold