external/clem/README

   1
   2 Common-Lisp Egregious Matrices (CLEM)
   3
   4 This is Cyrus Harmon's matrix package for common-lisp. Documentation
   5 should one day be found in doc/index.html.
   6
   7 Background
   8
   9 This was going to be called Common-Lisp Efficient Matrices (CLEM), but
  10 since efficiency is relative, I've decided to back off of that claim
  11 and call it Common-Lisp Egregious Matrices. It is a goal of the
  12 project that one day the intended meaning of egregious in this context
  13 will evolve from the "outstandingly bad" meaning to the "remarkably
  14 good" sense. Unfortunately, we're probably closer to outstandingly bad
  15 at this point.
  16
  17 Why are the matrices egregious?
  18
  19 Well, the main problem is a lack of efficeincy. Through relatively
  20 profuse use of declarations, many of the main matrix operations are
  21 efficient in the lisp-sense in that they are non-consing. It does not,
  22 however, mean that they are particularly fast. This package has only
  23 been tested on SBCL and SBCL's floating point performance is at least
  24 decent. In theory, further tuning of the lisp matrix code and perhaps
  25 the output of the compiler may help increase the performance here. As
  26 it stands, matrix multiplication is an order of magnitude (base 10)
  27 slower here than in BLAS. This performance is actually reasonably good
  28 for a high-level language, in my opinion, and can hopefully be
  29 improved upon. As informal benchmarks for comparison, I used BLAS and
  30 a slightly hand-tuned matrix multiply written in C. Interestingly, I
  31 could make the C version run about three times faster than the lisp
  32 version, while the BLAS matrix multiply was another 3x faster than
  33 that, yielding a roughly 10x speedup for BLAS relative to the CLEM
  34 matrix multiply. It seems as though the performance hit is largely a
  35 memory-access penalty. (Oh, I'll undoubtedly mention this again, but
  36 at the moment this has only been tested on SBCL on PPC. It would be
  37 interesting to see what the results on other processor families are,
  38 but I would imagine they would be fairly similar.) Smarter memory
  39 access patterns through the matrices to be multiplied and to
  40 accumulate the results may help performance here.
  41
  42 But clearly there is more to life than matrix multiplication. One of
  43 the goals of building this package in lisp is to get access to the
  44 nice features of high-level languages. It's all well and good to write
  45 matrix-intensive code in fortran, but I really wouldn't to write code
  46 for interacting with databases, or for processing XML documents or for
  47 serving web-applications in fortran. I hope that CLEM can be used in
  48 contexts such as these.
  49
  50 Why not just use Matlab or R?
  51
  52 This is a very good question. First and foremost, I like the features
  53 of the lisp language and miss them greatly when I go into those
  54 environments. The editing and debugging tools of a modern common lisp
  55 (Emacs/SLIME today and perhaps CLIMACS/SLIME in the not-too-distant
  56 future) are a major win in my eyes. Yes, there are amazing libraries
  57 for doing just about everything under the sun in both Matlab and R,
  58 but they strike me as less-good for general purpose computing than
  59 common lisp. These really should be treated as the pros and cons for
  60 each are in fact quite different.
  61
  62 Matlab
  63
  64 One major problem with Matlab is the licensing model. Ensuring that
  65 Matlab is on every computer to run Matlab software is quite
  66 annoying. A second problem is that the language, while very nice for
  67 building quick and dirty scripts and prototypes, doesn't seem to be
  68 nearly as nice for building large systems as common lisp. More on this
  69 later.
  70
  71 R
  72
  73 R is great, but it's interpreted language leads to performance
  74 problems. It is true that the core math routines in general are
  75 implemented in fast fortran down "under the covers", but for
  76 higher-level processing, one is stuck with a mediocre interpreted
  77 language. It's true that the R language is essentially a scheme
  78 variant, but it is a scheme variant with a C-like syntax on top that,
  79 in my opinion, leaves much to be desired in comparison with common
  80 lisp.
  81
  82 What about Matlisp?
  83
  84 Yes, matlisp is very nice and interfaces with fortran libraries for
  85 fast math performance. In fact, I have started working on tying CLEM
  86 into matlisp. This will probably be more important for floating point
  87 and complex matrices than for integer matrices. Integer matrices are
  88 important to me as one of the main data types I will be working with
  89 are images, so I wanted an efficient package for dealing with integer
  90 matrices.
  91
  92 Anyway, we'll see if this ever proves to be useful. In the meantime,
  93 it has been a fun exercise in trying to build a lisp-based system for
  94 matrix math.
  95
  96 What does CLEM do?
  97
  98 Typed methods for matrix math
  99 * mat-add
 100 * mat-subtr
 101 * mat-mult
 102 * mat-mult-block (to replace mat-mult when fully debugged)
 103 * mat-hprod (hadamard product (C_ij = A_ij * B_ij for all i,j))
 104 * scalar-mult
 105 * scalar-divide
 106 * sum
 107 * sum-range
 108 * max-val
 109 * min-val
 110
 111 Matrix type conversions
 112
 113 Convolution
 114
 115 Morphological Operations
 116
 117 * gaussian-blur
 118 * dilate
 119 * erode
 120
 121 Derivatives
 122
 123 * x-derivative
 124 * y-derivative
 125 * gradmag
 126
 127 Examples
 128
 129 Check out test for now. Hope to have more of this in the near future.
 130