[SciPy-dev] genetic algorithm, number theory, filter design, zero finding

[pearu at scipy.org]

Hi,

On Mon, 8 Apr 2002, Chuck Harris wrote:

> I've written a number of python routines over the past half year for
> my own use, and wonder if it might be appropriate to include some of
> them in scipy. They break down into the general categories:

I would suggest that you first make them modules so that we can look at
them whether they can be included to SciPy and how. Since SciPy itself is
quite short from documentation and unit testing (fixing this has a high
priority level in forthcoming SciPy development) I would expect that any
new module to be considered for inclusion to SciPy should be (more or
less) fully documented and has a (more or less) complete testing site.

> Number Theory : These were used for analysing arrays of antennas used
> in radar interferometry. They are also useful in integer programming,
> cryptography, and computational algebra.
> 
> 	Reduction of a matrix to Hermite normal form
> 	Reduction of a matrix to Smith normal form
> 	LLL basis reduction
> 	LLL basis reduction - deep version
> 	Gram-Schmidt orthogonalization

I am not sure where these should go when considering the current scipy
state. As you mention, they are parts of different fields from what we
have in scipy now. I think they should be parts of the corresponding
packages that may not exist as of yet. Personally, I am very interested in
CA stuff.

> Filter Design: Routines used for designing Complex Hermitian digital
> filters :
> 
> 	Remez exchange algorithm -  for arbitrary Chebychev systems.

Would signal be an appropiate place for this?

> Zero finders: General use and fun. Bisection best for some special
> cases, Ridder is middle of the pack, Brent is generally best, with the
> two versions basically a wash, although the hyperbolic version is
> simpler. Whether or not there is any virtue to these as opposed to
> solve, I don't know.
> 
> 	Bisection
> 	Illinois version of regula falsa
> 	Ridder
> 	Brent method with hyperbolic interpolation
> 	Brent method with inverse quadatic interpolation

Can you compare these zero finders with ones in 
scipy? Performance? Robustness to initial conditions? Etc. Are they any
better?

> Genetic algorithm: Used in digital filter design to optimize for
> coefficient truncation error. I looked at galib and found it easier to
> roll my own, but didn't try for any great generality. I think it would
> be good to include uniform crossover and to pull the fitness function
> out of the genome --- in a tournament, fitness can depend on the
> population. Perhaps it can all be made simpler.

galib seems to be developed more than 6 years and I would expect it to be
rather mature, though, I have not used it myself. May be a
wrapper to such a library would be more appropiate for a longer term.
Though the licence may be an issue, galib seems to be GPL compatible.

Pearu