external/clem/doc/clem.xhtml

   1 <?xml version="1.0" encoding="UTF-8"?>
   2 <!DOCTYPE html
   3      PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   4      "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head><title>clem: A common-lisp matrix package</title>
   5 <link rel="stylesheet" type="text/css" href="simple.css"/></head>
   6 <body><p/><span><h1>Abstract</h1>
   7 <p>CLEM is an open-source Common Lisp library for the
   8  representation and manipulation of matrices. CLEM is designed to
   9  be a flexible and extensible system for the representation of
  10  arbitrary 2-dimensional matrices.</p>
  11 </span>
  12 <h1>Introduction</h1>
  13 <p>The Common Lisp language<span><a href="#ref1">[1]</a>
  14 </span>
  15  offers a rich, dynamic environment for programming and
  16 data analysis. Common Lisp contains a powerful object system, the
  17 Common Lisp Object System (CLOS)<span><a href="#ref2">[2]</a>
  18 </span>
  19 , and most modern implementations support a protocol for
  20 the generation not just of new classes and objects, but to extend
  21 the object system itself using the Meta-object Protocol<span><a href="#ref3">[3]</a>
  22 </span>
  23 .</p>
  24 <p>CLEM uses CLOS and the Meta-object protocol (MOP) to define a<code>standard-matrix-class</code>
  25  that serves as the metaclass for classes that represent
  26 matrices with elements of specific types. The typed matrices can
  27 represent matrices containing values of specific types in the
  28 Common Lisp type system, starting with type <code>t</code>
  29  as the most general data type, and becoming more restrictive by using more specific types such<code>double-float</code>
  30 , <code>fixnum</code>
  31 , or <code>(unsigned-byte 8)</code>
  32 . By using the most specific type that can represent the values of a given matrix, the lisp system can optimize for better performance and memory usage requirements. For example, a <code>bit-matrix</code>
  33  will use 1 bit per matrix element, rather than 32-bits on 32-bit systems for a <code>t-matrix</code>
  34 .</p>
  35 <h2>Matrix Types</h2>
  36 <h2>Matrix Representation</h2>
  37 <p>Common Lisp provides a rich built-in array type which serves as
  38  the storage for CLEM matrices. Given that Common Lisp has built-in
  39  arrays, why do we need CLEM and what value is provided by creating a
  40  set of classses around arrays? First, the Common Lisp arrays have a
  41  limited set of operations defined on them. While there is a built-in
  42  (scalar) addition operator, there is no built-in way to perform an
  43  element-wise addition of two arrays. CLEM addresses these by defining
  44  a set of generic functions that operate on matrices that provide a
  45  number of commonly used matrix operations such as matrix
  46  arithmetic. Second, there is no way to define methods on arrays based
  47  on their element types. Therefore, we define subclasses of matrix
  48  whose underlying arrays are specialized to distinct types. We can
  49  then define methods to operate specifically on these subclasses,
  50  affording the opportunity to treat, say, floating point and integer
  51  matrices differently and to provide declarations to the compiler
  52  based on the array element type, which can, in Common Lisp
  53  implementations with sufficiently smart compilers, lead to much
  54  improved performance.</p>
  55 <h1>Defining CLEM Classes and Making CLEM Instances</h1>
  56 <h2>Creating CLEM Instances with make-instance</h2>
  57 <p>The following code creates a 16-row by 16-column matrix of type<code>double-float-matrix</code>
  58  and assigns it to the dynamic variable<code>*m1*</code>
  59 .</p>
  60 <div class="lisp"><pre><code>(defparameter *m1* (make-instance 'double-float-matrix :rows 16 :cols 16))
  61 </code>
  62 <code class="results">*M1*
  63 </code>
  64
  65 <code>*m1*
  66 </code>
  67 <code class="results">#&lt;DOUBLE-FLOAT-MATRIX [.000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  68  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  69  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  70  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  71  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  72  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  73  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  74  ...
  75  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000]&gt;
  76 </code>
  77
  78 </pre>
  79 </div>
  80 <p>The default is to only show the first 7 and the last rows
  81  and columns of each matrix. The number of rows and columns can
  82  be changed by setting the <code>*matrix-print-row-limit*</code>
  83  and<code>*matrix-print-col-limit*</code>
  84  variables.</p>
  85 <h2>standard-matrix-class</h2>
  86 <h2>CLEM Matrix Types</h2>
  87 <h3>Number matrices</h3>
  88 <p>The most general class of numerical matrix is the number matrix.</p>
  89 <h3>Integer Matrices</h3>
  90 <h3>Floating-point Matrices</h3>
  91 <h3>Complex-value Matrices</h3>
  92 <h1>Working with CLEM Matrices</h1>
  93 <h2>Matrix Dimensions and Values</h2>
  94 <h2>Typed matrix operations</h2>
  95 <h2>Matrix Copying</h2>
  96 <h2>matrix-move</h2>
  97 <h1>Matrix Arithmetic</h1>
  98 <h2>Matrix Addition and Subtraction</h2>
  99 <h2>Matrix Multiplication</h2>
 100 <h2>Hadamard Product</h2>
 101 <h2>Scalar Arithmetic</h2>
 102 <h2>Other Mathematical Functions</h2>
 103 <p>Discuss mat-log, mat-abs, min, and max.</p>
 104 <h1>Matrix Operations</h1>
 105 <h2>Matrix Inversion</h2>
 106 <h2>Matrix Normalization</h2>
 107 <h2>Discrete Convolution</h2>
 108 <h3>Derivatives</h3>
 109 <h3>Gradient Magnitude</h3>
 110 <h3>Gaussian Blur</h3>
 111 <h2>Affine Transformations</h2>
 112 <h3>Interpolation</h3>
 113 <h2>Morphological Operations</h2>
 114 <h3>Dilation and Erosion</h3>
 115 <h3>Variance</h3>
 116 <h3>Thresholding</h3>
 117 <h1>CLEM Implementation Details</h1>
 118 <h2>Type-specific matrix functions</h2>
 119 <p>The general strategy has been to 1) make things work and
 120  then make them work quickly.  To this end, I have been writing
 121  functions for matrix operations in a general manner first and
 122  then recoding type-specific versions to make certain operations
 123  go faster.  This is done via liberal use of macros to generate
 124  type-specific functions and methods for matrix operations that
 125  go much faster than the general versions.</p>
 126 <p>The convention is that a generic function such as sum-range
 127  will have a generic version that works with all matrices and
 128  type specific versions thaqt work with specific matrices. g In
 129  order to support these functions there may be internal methods,
 130  prefixed with a %, that implement certain type-specific
 131  functionality.  Macros that generate the code used for the
 132  type-specific methods will be prefixed with a %%.  In theory,
 133  the %%-macros can be called from other code that need to
 134  generate in-place code where the overhead of the method-call to
 135  the %-method would be too expensive. This convention is not yet
 136  widely enforced and certainly untested. Hopefully this situation
 137  will improve.</p>
 138 <h2>Hacking the SBCL compiler to improve performance</h2>
 139 <div><h1>References</h1>
 140 <p><a name="ref1">1. Steele, Jr., Guy L.. Common {L}isp: the {L}anguage (1990).</a>
 141 </p>
 142 <p><a name="ref2">2. Sonya E. Keene. Object-{O}riented {P}rogramming in {C}ommon {L}isp: {A} {P}rogrammer's     {G}uide to {CLOS} (1989).</a>
 143 </p>
 144 <p><a name="ref3">3. Gregor Kiczales. The {A}rt of the {M}etaobject {P}rotocol (1991).</a>
 145 </p>
 146 </div>
 147 </body>
 148 </html>