Matrix Inversion

Appeared in Volume 6/3, August 1993

jackson@sandman.ece.clarkson.edu
Peter Jackson
26th May 1993

Roland Paterson-Jones writes:
I'm looking for matrix manipulation/Gaussian reduction implementations in Prolog. Can anyone help me?

I wonder if Prolog is a sensible language for this? I imagine that coding algorithms like LUP decomposition is a non-trivial exercise.

alan@geg.mot.com
Alan Newman
26th May 1993

I haven't done any serious matrix math in Prolog but we do have an interesting analogous experience with complex math.

We found that a Prolog 1024 point complex DFT spectral analysis ran with about one half the performance of an C version (an optimized FFT), with substantially less source code, and far better versitility. I wouldn't recommend doing a direct port of some FORTRAN LU decomposition algorithm, but you may find (like we did) that a rethinking of the problem into a more recursive, declarative representation will yield a very elegant Prolog solution with execellent performance.

If anyone is interested, contact the author of the DFT program, Sam Daniel, at smdaniel@geg.mot.com.

dis@eng.buffalo.edu
David I Schwartz
27th May 1993

You're right about elegance. With a little craftiness, you can create some clever math subroutines with recursion.

For matrix operations, Stuart S. Chen (ciechen@eng.buffalo.edu) and I have been developing code for Gauss-Seidel, Cramer's rule, inversion by the cofactors method, and a determinant solver (a good example of double recursion). Also, we borrowed gaussian elminination from the Quintus library.

We still need to clean up the code slightly, and then we'll make it available in the public domain.

wfc@cl.cam.ac.uk
William Clocksin
3rd June 1993

People have been asking about numerical methods in Prolog. This may seem unlikely, but is actually a good idea, as many numerical methods have an inherently logical specification. However, practical problems do arise because good numerical methods usually contain tricks (such as backsubstitution in the case of matrix methods, and shuffling in the case of the FFT). These tricks often rely on mutable arrays, and do not translate well into Prolog. However, there is a way around this. My approach is to compile dataflow diagrams that do the backsubstitution and shuffling as lengthy but trivial special cases of collecting common subexpressions. It really works!

For details, see my paper:
"A technique for translating clausal specifications of numerical methods into efficient programs", Journal of Logic Programming, vol 5, no. 3, 1988, pp 231-242.

It deals with the FFT, solution of matrix equations, etc. Instead of just writing code to solve the problems, I take an abstract interpretation approach in order to generate efficient dataflow programs.

Another paper does the same thing to automatically produce dynamic programming dataflow programs for recursively specified optimisation problems:
"Logic programming specification and execution of dynamic programming problems" Journal of Logic Programming, vol 12, 1992, pp 325-333

Also, somebody asked whether anyone is doing parallel implementations of numerical methods in Prolog. Currently, I am getting ready to run the programs emitted from a Prolog-to-dataflow graph compiler on a dataflow machine which has been built in the Computer Lab by Simon Moore. Hope to report something soon.