external/clem/doc/clem.tex

   1 \documentclass[10pt]{article}
   2 \setcounter{secnumdepth}{5}
   3 \usepackage{amssymb}
   4 \usepackage{amsmath}
   5 \usepackage{verbatim}
   6 \usepackage{graphicx}
   7 \usepackage{subfigure}
   8 \usepackage{caption}
   9 \usepackage{hyperref}
  10 \usepackage{fancyheadings}
  11 \usepackage{longtable}
  12 \usepackage[letterpaper]{geometry}
  13 \newcommand{\argmax}{\operatornamewithlimits{argmax}}\newcommand{\argmin}{\operatornamewithlimits{argmin}}
  14 \title{clem: A common-lisp matrix package}
  15 \author{Cyrus L. Harmon}
  16 \geometry{verbose,tmargin=1in,bmargin=1in,lmargin=1in,rmargin=1in}
  17 \setcounter{topnumber}{2}
  18 \setcounter{bottomnumber}{2}
  19 \setcounter{totalnumber}{4}     % 2 may work better
  20 \setcounter{dbltopnumber}{2}    % for 2-column pages
  21 \renewcommand{\dbltopfraction}{0.9}     % fit big float above 2-col. text
  22 \renewcommand{\textfraction}{0.07}      % allow minimal text w. figs
  23 %   Parameters for FLOAT pages (not text pages):
  24 \renewcommand{\floatpagefraction}{0.7}  % require fuller float pages
  25 % N.B.: floatpagefraction MUST be less than topfraction !!
  26 \renewcommand{\dblfloatpagefraction}{0.7}       % require fuller float pages
  27 \setlength{\captionmargin}{10pt}
  28 \begin{document}
  29 \maketitle
  30 \let\mypdfximage\pdfximage
  31 \def\pdfximage{\immediate\mypdfximage}
  32 \baselineskip14pt
  33
  34
  35 \clearpage
  36 \section{Abstract}
  37 CLEM is an open-source Common Lisp library for the
  38  representation and manipulation of matrices. CLEM is designed to
  39  be a flexible and extensible system for the representation of
  40  arbitrary 2-dimensional matrices.
  41
  42 \clearpage
  43 \section{Introduction}
  44 The Common Lisp language\cite{steele1990common} offers a rich, dynamic environment for programming and
  45 data analysis. Common Lisp contains a powerful object system, the
  46 Common Lisp Object System (CLOS)\cite{keene1989object}, and most modern implementations support a protocol for
  47 the generation not just of new classes and objects, but to extend
  48 the object system itself using the Meta-object Protocol\cite{kiczales1991art}.
  49
  50 CLEM uses CLOS and the Meta-object protocol (MOP) to define astandard-matrix-class that serves as the metaclass for classes that represent
  51 matrices with elements of specific types. The typed matrices can
  52 represent matrices containing values of specific types in the
  53 Common Lisp type system, starting with type t as the most general data type, and becoming more restrictive by using more specific types suchdouble-float, fixnum, or (unsigned-byte 8). 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 bit-matrix will use 1 bit per matrix element, rather than 32-bits on 32-bit systems for a t-matrix.
  54
  55 \baselineskip12pt
  56 \subsection{Matrix Types}
  57 \baselineskip14pt
  58 \baselineskip12pt
  59 \subsection{Matrix Representation}
  60 \baselineskip14pt
  61 Common Lisp provides a rich built-in array type which serves as
  62  the storage for CLEM matrices. Given that Common Lisp has built-in
  63  arrays, why do we need CLEM and what value is provided by creating a
  64  set of classses around arrays? First, the Common Lisp arrays have a
  65  limited set of operations defined on them. While there is a built-in
  66  (scalar) addition operator, there is no built-in way to perform an
  67  element-wise addition of two arrays. CLEM addresses these by defining
  68  a set of generic functions that operate on matrices that provide a
  69  number of commonly used matrix operations such as matrix
  70  arithmetic. Second, there is no way to define methods on arrays based
  71  on their element types. Therefore, we define subclasses of matrix
  72  whose underlying arrays are specialized to distinct types. We can
  73  then define methods to operate specifically on these subclasses,
  74  affording the opportunity to treat, say, floating point and integer
  75  matrices differently and to provide declarations to the compiler
  76  based on the array element type, which can, in Common Lisp
  77  implementations with sufficiently smart compilers, lead to much
  78  improved performance.
  79
  80 \clearpage
  81 \section{Defining CLEM Classes and Making CLEM Instances}
  82 \baselineskip12pt
  83 \subsection{Creating CLEM Instances with make-instance}
  84 \baselineskip14pt
  85 The following code creates a 16-row by 16-column matrix of typedouble-float-matrix and assigns it to the dynamic variable*m1*.
  86
  87
  88 \baselineskip12pt
  89 \begin{verbatim}(defparameter *m1* (make-instance 'double-float-matrix :rows 16 :cols 16))
  90 *M1*
  91
  92 *m1*
  93 #<DOUBLE-FLOAT-MATRIX [.000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  94  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  95  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  96  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  97  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  98  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
  99  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000;
 100  ...
 101  .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ... .000000000]>
 102
 103 \end{verbatim}
 104 \baselineskip14pt
 105 The default is to only show the first 7 and the last rows
 106  and columns of each matrix. The number of rows and columns can
 107  be changed by setting the *matrix-print-row-limit* and*matrix-print-col-limit* variables.
 108
 109 \baselineskip12pt
 110 \subsection{standard-matrix-class}
 111 \baselineskip14pt
 112 \baselineskip12pt
 113 \subsection{CLEM Matrix Types}
 114 \baselineskip14pt
 115 \baselineskip12pt
 116 \subsubsection{Number matrices}
 117 \baselineskip14pt
 118 The most general class of numerical matrix is the number matrix.
 119
 120 \baselineskip12pt
 121 \subsubsection{Integer Matrices}
 122 \baselineskip14pt
 123 \baselineskip12pt
 124 \subsubsection{Floating-point Matrices}
 125 \baselineskip14pt
 126 \baselineskip12pt
 127 \subsubsection{Complex-value Matrices}
 128 \baselineskip14pt
 129 \clearpage
 130 \section{Working with CLEM Matrices}
 131 \baselineskip12pt
 132 \subsection{Matrix Dimensions and Values}
 133 \baselineskip14pt
 134 \baselineskip12pt
 135 \subsection{Typed matrix operations}
 136 \baselineskip14pt
 137 \baselineskip12pt
 138 \subsection{Matrix Copying}
 139 \baselineskip14pt
 140 \baselineskip12pt
 141 \subsection{matrix-move}
 142 \baselineskip14pt
 143 \clearpage
 144 \section{Matrix Arithmetic}
 145 \baselineskip12pt
 146 \subsection{Matrix Addition and Subtraction}
 147 \baselineskip14pt
 148 \baselineskip12pt
 149 \subsection{Matrix Multiplication}
 150 \baselineskip14pt
 151 \baselineskip12pt
 152 \subsection{Hadamard Product}
 153 \baselineskip14pt
 154 \baselineskip12pt
 155 \subsection{Scalar Arithmetic}
 156 \baselineskip14pt
 157 \baselineskip12pt
 158 \subsection{Other Mathematical Functions}
 159 \baselineskip14pt
 160 Discuss mat-log, mat-abs, min, and max.
 161
 162 \clearpage
 163 \section{Matrix Operations}
 164 \baselineskip12pt
 165 \subsection{Matrix Inversion}
 166 \baselineskip14pt
 167 \baselineskip12pt
 168 \subsection{Matrix Normalization}
 169 \baselineskip14pt
 170 \baselineskip12pt
 171 \subsection{Discrete Convolution}
 172 \baselineskip14pt
 173 \baselineskip12pt
 174 \subsubsection{Derivatives}
 175 \baselineskip14pt
 176 \baselineskip12pt
 177 \subsubsection{Gradient Magnitude}
 178 \baselineskip14pt
 179 \baselineskip12pt
 180 \subsubsection{Gaussian Blur}
 181 \baselineskip14pt
 182 \baselineskip12pt
 183 \subsection{Affine Transformations}
 184 \baselineskip14pt
 185 \baselineskip12pt
 186 \subsubsection{Interpolation}
 187 \baselineskip14pt
 188 \baselineskip12pt
 189 \subsection{Morphological Operations}
 190 \baselineskip14pt
 191 \baselineskip12pt
 192 \subsubsection{Dilation and Erosion}
 193 \baselineskip14pt
 194 \baselineskip12pt
 195 \subsubsection{Variance}
 196 \baselineskip14pt
 197 \baselineskip12pt
 198 \subsubsection{Thresholding}
 199 \baselineskip14pt
 200 \clearpage
 201 \section{CLEM Implementation Details}
 202 \baselineskip12pt
 203 \subsection{Type-specific matrix functions}
 204 \baselineskip14pt
 205 The general strategy has been to 1) make things work and
 206  then make them work quickly.  To this end, I have been writing
 207  functions for matrix operations in a general manner first and
 208  then recoding type-specific versions to make certain operations
 209  go faster.  This is done via liberal use of macros to generate
 210  type-specific functions and methods for matrix operations that
 211  go much faster than the general versions.
 212
 213 The convention is that a generic function such as sum-range
 214  will have a generic version that works with all matrices and
 215  type specific versions thaqt work with specific matrices. g In
 216  order to support these functions there may be internal methods,
 217  prefixed with a %, that implement certain type-specific
 218  functionality.  Macros that generate the code used for the
 219  type-specific methods will be prefixed with a %%.  In theory,
 220  the %%-macros can be called from other code that need to
 221  generate in-place code where the overhead of the method-call to
 222  the %-method would be too expensive. This convention is not yet
 223  widely enforced and certainly untested. Hopefully this situation
 224  will improve.
 225
 226 \baselineskip12pt
 227 \subsection{Hacking the SBCL compiler to improve performance}
 228 \baselineskip14pt
 229 \clearpage
 230 \baselineskip11pt
 231 \begin{thebibliography}{1}
 232
 233 \bibitem{steele1990common}
 234 G.~L. Steele, Jr., {\it Common {L}isp: the {L}anguage\/} (Digital Press, Bedford MA, 1990), second edn.
 235
 236 \bibitem{keene1989object}
 237 S.~E. Keene, {\it Object-{O}riented {P}rogramming in {C}ommon {L}isp: {A} {P}rogrammer's        {G}uide to {CLOS}\/} (Addison-Wesley Professional, 1989).
 238
 239 \bibitem{kiczales1991art}
 240 G.~Kiczales, {\it The {A}rt of the {M}etaobject {P}rotocol\/} (The MIT Press, 1991).
 241
 242 \end{thebibliography}
 243 \end{document}