1 \documentclass[10pt
]{article
}
2 \setcounter{secnumdepth
}{5}
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
}
30 \let\mypdfximage\pdfximage
31 \def\pdfximage{\immediate\mypdfximage}
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.
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
}.
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.
56 \subsection{Matrix Types
}
59 \subsection{Matrix Representation
}
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
81 \section{Defining CLEM Classes and Making CLEM Instances
}
83 \subsection{Creating CLEM Instances with make-instance
}
85 The following code creates a
16-row by
16-column matrix of typedouble-float-matrix and assigns it to the dynamic variable*m1*.
89 \begin{verbatim
}(defparameter *m1* (make-instance 'double-float-matrix :rows
16 :cols
16))
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;
101 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 .000000000 ...
.000000000]>
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.
110 \subsection{standard-matrix-class
}
113 \subsection{CLEM Matrix Types
}
116 \subsubsection{Number matrices
}
118 The most general class of numerical matrix is the number matrix.
121 \subsubsection{Integer Matrices
}
124 \subsubsection{Floating-point Matrices
}
127 \subsubsection{Complex-value Matrices
}
130 \section{Working with CLEM Matrices
}
132 \subsection{Matrix Dimensions and Values
}
135 \subsection{Typed matrix operations
}
138 \subsection{Matrix Copying
}
141 \subsection{matrix-move
}
144 \section{Matrix Arithmetic
}
146 \subsection{Matrix Addition and Subtraction
}
149 \subsection{Matrix Multiplication
}
152 \subsection{Hadamard Product
}
155 \subsection{Scalar Arithmetic
}
158 \subsection{Other Mathematical Functions
}
160 Discuss mat-log, mat-abs, min, and max.
163 \section{Matrix Operations
}
165 \subsection{Matrix Inversion
}
168 \subsection{Matrix Normalization
}
171 \subsection{Discrete Convolution
}
174 \subsubsection{Derivatives
}
177 \subsubsection{Gradient Magnitude
}
180 \subsubsection{Gaussian Blur
}
183 \subsection{Affine Transformations
}
186 \subsubsection{Interpolation
}
189 \subsection{Morphological Operations
}
192 \subsubsection{Dilation and Erosion
}
195 \subsubsection{Variance
}
198 \subsubsection{Thresholding
}
201 \section{CLEM Implementation Details
}
203 \subsection{Type-specific matrix functions
}
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.
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
227 \subsection{Hacking the SBCL compiler to improve performance
}
231 \begin{thebibliography
}{1}
233 \bibitem{steele1990common
}
234 G.~L. Steele, Jr.,
{\it Common
{L
}isp: the
{L
}anguage\/
} (Digital Press, Bedford MA,
1990), second edn.
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).
239 \bibitem{kiczales1991art
}
240 G.~Kiczales,
{\it The
{A
}rt of the
{M
}etaobject
{P
}rotocol\/
} (The MIT Press,
1991).
242 \end{thebibliography
}