Cyrus Harmon <firstname.lastname@example.org>
READMEMore 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.