More bogus changes.

Common-Lisp Egregious Matrices (CLEM)

This is Cyrus Harmon's matrix package for common-lisp. Documentation
should one day be found in doc/index.html.

Background

This was going to be called Common-Lisp Efficient Matrices (CLEM), but
since efficiency is relative, I've decided to back off of that claim
and call it Common-Lisp Egregious Matrices. It is a goal of the
project that one day the intended meaning of egregious in this context
will evolve from the "outstandingly bad" meaning to the "remarkably
good" sense. Unfortunately, we're probably closer to outstandingly bad
at this point.

Why are the matrices egregious?

Well, the main problem is a lack of efficeincy. Through relatively
profuse use of declarations, many of the main matrix operations are
efficient in the lisp-sense in that they are non-consing. It does not,
however, mean that they are particularly fast. This package has only
been tested on SBCL and SBCL's floating point performance is at least
decent. In theory, further tuning of the lisp matrix code and perhaps
the output of the compiler may help increase the performance here. As
it stands, matrix multiplication is an order of magnitude (base 10)
slower here than in BLAS. This performance is actually reasonably good
for a high-level language, in my opinion, and can hopefully be
improved upon. As informal benchmarks for comparison, I used BLAS and
a slightly hand-tuned matrix multiply written in C. Interestingly, I
could make the C version run about three times faster than the lisp
version, while the BLAS matrix multiply was another 3x faster than
that, yielding a roughly 10x speedup for BLAS relative to the CLEM
matrix multiply. It seems as though the performance hit is largely a
memory-access penalty. (Oh, I'll undoubtedly mention this again, but
at the moment this has only been tested on SBCL on PPC. It would be
interesting to see what the results on other processor families are,
but I would imagine they would be fairly similar.) Smarter memory
access patterns through the matrices to be multiplied and to
accumulate the results may help performance here.

But clearly there is more to life than matrix multiplication. One of
the goals of building this package in lisp is to get access to the
nice features of high-level languages. It's all well and good to write
matrix-intensive code in fortran, but I really wouldn't to write code
for interacting with databases, or for processing XML documents or for
serving web-applications in fortran. I hope that CLEM can be used in
contexts such as these.

Why not just use Matlab or R?

This is a very good question. First and foremost, I like the features
of the lisp language and miss them greatly when I go into those
environments. The editing and debugging tools of a modern common lisp
(Emacs/SLIME today and perhaps CLIMACS/SLIME in the not-too-distant
future) are a major win in my eyes. Yes, there are amazing libraries
for doing just about everything under the sun in both Matlab and R,
but they strike me as less-good for general purpose computing than
common lisp. These really should be treated as the pros and cons for
each are in fact quite different.

Matlab

One major problem with Matlab is the licensing model. Ensuring that
Matlab is on every computer to run Matlab software is quite
annoying. A second problem is that the language, while very nice for
building quick and dirty scripts and prototypes, doesn't seem to be
nearly as nice for building large systems as common lisp. More on this
later.

R

R is great, but it's interpreted language leads to performance
problems. It is true that the core math routines in general are
implemented in fast fortran down "under the covers", but for
higher-level processing, one is stuck with a mediocre interpreted
language. It's true that the R language is essentially a scheme
variant, but it is a scheme variant with a C-like syntax on top that,
in my opinion, leaves much to be desired in comparison with common
lisp.

What about Matlisp?

Yes, matlisp is very nice and interfaces with fortran libraries for
fast math performance. In fact, I have started working on tying CLEM
into matlisp. This will probably be more important for floating point
and complex matrices than for integer matrices. Integer matrices are
important to me as one of the main data types I will be working with
are images, so I wanted an efficient package for dealing with integer
matrices.

Anyway, we'll see if this ever proves to be useful. In the meantime,
it has been a fun exercise in trying to build a lisp-based system for
matrix math.

What does CLEM do?

Typed methods for matrix math
* mat-add
* mat-subtr
* mat-mult
* mat-mult-block (to replace mat-mult when fully debugged)
* mat-hprod (hadamard product (C_ij = A_ij * B_ij for all i,j))
* scalar-mult
* scalar-divide
* sum
* sum-range
* max-val
* min-val

Matrix type conversions

Convolution

Morphological Operations

* gaussian-blur
* dilate
* erode

Derivatives

* x-derivative
* y-derivative
* gradmag

Examples

Check out test for now. Hope to have more of this in the near future.