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

Chuck Harris Chuck.Harris at sdl.usu.edu
Tue Apr 9 11:14:27 CDT 2002


Hi,

> From: pearu at scipy.org [mailto:pearu at scipy.org]
> Sent: Tuesday, April 09, 2002 3:24 AM
> 
> 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.
>

Good enough. Would packaging things up with distutils be a good way to go?
Also, are there any documentation guidelines? I assume that more might be wanted than goes in """...""". For testing, I'm guessing that there might be two kinds: first, to check that the routines operate correctly on a given platform and second, to check that the routines do what they are supposed to do. Are there any testing guidelines?
 
> > 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.

These routines really need exact rational arithmetic in the general case. The floating point versions here just happen to be 'good enough' in many situations. Are there any plans to bring exact arithmetic into scipy or numpy? 

> 
> > 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?
>

Sounds right.
 
> > 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?
> 

I took a quick look at the Fortran code for the version of solve in the minimization
package. It seems to be a multidimensional form of Newton's method, really the only way to go in higher dimensions unless the function is holomorphic. The routines here are for the one dimensional case and should be more robust in this situation. If any one has a more general idea of what goes on in the current zero finder, I would like to hear about it.

> > 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
> 
I was sort of hoping for a ga guru to comment. Perhaps all that is really needed here is good documentation and a bit of formatting cleanup.

Chuck
> _______________________________________________
> Scipy-dev mailing list
> Scipy-dev at scipy.net
> http://www.scipy.net/mailman/listinfo/scipy-dev
> 



More information about the Scipy-dev mailing list