Tuesday 26 February 2008

There’s something magical about complex algorithms. They take a hard problem and build a strong fence around it. Once you’ve got an implementation working, you don’t have to worry about what’s inside any more. Take the specifics of the problem at hand, drop them into the algorithm, and out pops an answer. It’s like a cartoon machine with lights and wheels on the outside, and magic happens on the inside.

I’ve been poking around looking at Python implementations of algorithms for solving. Roughly speaking, these tools take a system of constraints, and produce an answer comprising the values that satisfy the constraints. I’m sure there are more, but these are what I’ve turned up in a quick search.

¶ Simple Gauss-Jordan Elimination is a classic math technique for solving a system of linear equations. This works great, but is crying out to be implemented as a C extension.

¶ SMAWK (an awk-like acronym of the authors’ initials) finds the maxima in each row of a large matrix of values, provided the matrix is totally monotone. This sounds esoteric, but has applications in computational geometry and other areas. David Eppstein used it to implement Knuth’s paragraph wrapping algorithm, and if an algorithm lets you re-implement Knuth-Plass in 65 lines of Python, I’m guessing you have a powerful algorithm. David has a bunch of other algorithmic stuff for Python too.

¶ logilab-constraint and python-constraint are two Python implementations of constraint solvers. These seem to be good at discrete problems like solving Sudoku or eight queens. BTW: Roman Barták maintains a list of constraint system implementations which could be useful.

Beyond these, there are tons of fascinating techniques: simulated annealing (with some Python implementations), genetic algorithms (Python implementations), and optimization algorithms of all sorts.

## Comments

Iain10:57 AM on 26 Feb 2008> Simple Gauss-Jordan Elimination

I'm sure you linked to this because it's neat to see pure-python implementations. But anyone wanting to do serious work with matrices should use numpy and scipy. These use decent Fortran libraries for things like linear system solving.

Ned Batchelder11:25 AM on 26 Feb 2008@Iain: this was the Python implementation I had found. I actually went looking for a numpy version, but must have been using the wrong search terms, because of course there is one: numpy.linalg.solve.

Carlos Santos12:38 PM on 26 Feb 2008Python implementations for genetic algorithms, csp, simulated annealing (and many other algorithms) are available in python-aima, the companion package to Russell and Norvig's AI book:

http://code.google.com/p/aima-python/

I believe there is also a debian package for this stuff (python-aima).

Pedro Lima5:25 PM on 27 Feb 2008This python solver also seems quite interesting:

http://abel.ee.ucla.edu/cvxopt

D. Kelson9:37 PM on 27 Feb 2008While things in Numeric/Numpy/Scipy/Multipack/Whatever are always the first place to look, I find that very often it is trivial to head over to NETLIB and wrap things that are needed in specialized applications. For example: it's trivial to wrap the NNLS fortran routine (Lawson & Hanson's nonnegative least squares subroutine), or Toint's VE08AD subroutine for solving partially separable minimization problems with or without constraints, or from Argonne one has Levine's incredibly powerful PGAPACK genetic algorithm library. With the availability of multiple options for wrapping functions, nobody need be constrained to a few python-based solvers anymore...

Didrik Pinte3:18 AM on 28 Feb 2008There is also LPSolve that can easily be called using python. I've made a python-lpsolve package for Debian for those interested.

K. Hatch2:12 AM on 4 Mar 2008Well I wanted to use pure integer arithmetic to solve large determinants, so I wrote my own python routine to do that. I don't think the available determinant functions can resolve a large determinant that is near singular, but with integer arithmetic it can't miss. With integer arithmetic, if the answer is zero, the determinant is, in fact, singular.

There is another application where python is invaluable because of the infinitely long integer capability. I wanted to solve electronic circuits symbolically (e.g. the answer is (R1*R2)/(R4+R5), not 4.6374853e-7). This required solving determinants with pure integers that can be huge. Python does a real nice job of that.

I am not a python programmer, so my code is very cumbersome and non-standard. But it works! I would like to see someone include a determinant library routine that does pure integer arithmetic, where the integers can be any size.

## Add a comment: