Quantum Mechanic

Content from 2012-11-30 22:05:50

Map Take 2: The Slicening

posted on 2012-11-30 22:05:50

It's been a while since I wrote about my scientific computing library for lisp: map.  Map is a great exercise for me -- in learning Lisp and learning algorithms and optimization.  Since I'm between jobs and not yet in grad school, the time has been ripe to work on the library with some toy cases and try to make it as usable as possible by the time I get back in a position where I could use it for real work.

Because of my copious free time, a lot has been changing lately, including the addition of matrix slices, which were important, and such important features as matrix inversion.  I'm also looking at adding parallelization at some point, as well as a matrix-defining macro in the style of the #v() one for vectors.

In any event, here's what's new:


Slices


I promised to write again when I had finished with matrix slices in map.  I'm sure they're not in their final state, but I have implemented them in a way that works. Now you can do things like:
(setf (mref m 1 #r(1 2) t) #2a((2.0d0 1.0d0 3.4d0) (3.1d0 3.2d2 4.2d1)))

Which already has a number of things going on in it.  This is setting a sub-matrix of m, a rank-3 matrix to a rank-2 matrix specified in the end of  the setf call.  Since we selected a single value for the first index of m, mref will not count that dimension as extant for the purposes of comparing with the shape of the matrix we're assigning.  This is really useful, because now things like multiplying matrices can be done like this:
(defmethod .* ((A simple-array) (B simple-array))
(with-result (result (list (array-dimension A 0) (array-dimension B 1)))
(do-matrix (result (i j))
(setf (aref result i j) (dot (mref a i t) (mref b t j))))))

There are three different ways you can specify subscripts to mref:

  1. Integers
    This will work like aref, and the dimension won't be included in the final output

  2. Ranges
    This will select all entries in the matrix that have indices inside the specified range in this dimension, for example, (mref #(1 2 3) #r(0 1)) ==> #(1 2)

  3. t
    This selects all elements in this dimension.  It's great for slicing rows/columns out of matrices a la (mref m t 0), which will take the first column out of m.


Matrix iteration


Since most of the functions in the library were operating on matrices and returning new ones, I thought some macros were in order.  I think it's the reflex of any lisper to write a macro when they see the same code in more than one place.

Of that urge were born (with-result) and (do-matrix)(with-result) is simply a convenient way of defining a new matrix at the start of a function and automatically returning it.  (do-matrix), though, I rather like because it allows looping over matrices in a rather intuitive way.

(defun mandelbrot (matrix)
(with-result (result (list 1001 1001) 'integer)
(do-matrix (matrix (r i))
(setf (aref result r i)
(loop
with c = (aref matrix r i)
with z = c
for i from 0 upto 80
if (> (abs z) 2)
return (1- i)
else
do (setf z (+ (expt z 2) c))
finally (return 80))))))

Here you can see (do-matrix) at work, testing whether each element of an array of complex numbers is in the Mandelbrot set.  It's definition is
(defmacro do-matrix (matrix &optional subscripts) ...)

which means you can then just write element-wise operations inside the loop with all of the indices figured out for you.

I'll end with the figure I made of the Mandelbrot set today on the [-2, 2] range in the complex plane. Along with the (mandelbrot) function above, you need the matrix to call it on,

(mute
(setq cm
(let ((center 500))
(with-result (result (list 1001 1001) '(complex double-float))
(do-matrix (matrix (r i))
(setf (aref matrix r i)
(complex (* (- r center) (/ 2.0d0 500))
(* (- i center) (/ 2.0d0 500)))))))))

and then you can run
(mute (setq r (mandelbrot cm)))
(image r)

.

The Mandelbrot set from -2 to 2 in the complex plane.
The Mandelbrot set from -2 to 2 in the complex plane.

View content from 2009-03-16 04:17:00, 2009-03-21 04:36:00, 2009-04-02 02:00:00, 2009-04-04 01:48:00, 2009-06-25 19:43:00, 2009-07-09 19:15:00, 2009-07-09 19:44:00, 2009-07-20 23:25:00, 2009-07-21 16:57:00, 2009-08-05 05:44:00, 2009-08-05 10:28:00, 2009-08-12 07:11:00, 2009-08-23 02:05:00, 2009-08-23 04:30:00, 2009-10-30 08:02:00, 2009-11-08 06:59:00, 2009-12-04 01:17:00, 2010-05-22 18:55:00, 2010-05-28 22:50:00, 2010-06-05 19:55:00, 2010-06-12 02:12:00, 2010-06-20 20:20:00, 2010-07-02 22:57:00, 2010-08-20 22:16:00, 2010-09-02 02:07:00, 2011-01-07 10:35:30, 2011-01-07 11:17:53, 2011-01-13 06:48:47, 2011-01-24 02:52:06, 2011-01-31 02:41:34, 2011-02-13 23:09:09, 2011-03-23 05:59:11, 2011-04-06 01:33:19, 2011-04-24 22:15:24, 2011-04-24 22:51:30, 2011-06-06 22:36:07, 2011-06-16 02:27:10, 2011-06-30 01:26:18, 2011-07-31 23:10:35, 2011-08-17 04:15:14, 2011-09-11 17:13:48, 2011-10-01 15:55:35, 2011-11-02 15:14:47, 2011-11-08 01:49:00, 2011-11-29 23:28:27, 2011-11-29 23:30:17, 2011-11-30 06:58:06, 2011-12-08 02:41:21, 2012-01-17 17:27:10, 2012-01-20 16:59:54, 2012-01-31 17:26:17, 2012-02-07 15:46:44, 2012-02-10 17:15:32, 2012-03-03 18:35:25, 2012-03-30 02:45:19, 2012-04-23 21:44:13, 2012-07-13 16:39:31, 2012-07-13 16:56:55, 2012-07-17 01:15:15, 2012-08-21 22:12:00, 2012-08-22 21:26:44, 2012-09-19 15:35:27, 2012-11-15 21:27:40, 2012-11-15 21:28:49, 2012-11-26 09:40:14, 2012-11-30 22:05:50, 2013-02-22 20:37:08, 2013-03-08 08:50:26, 2013-03-16 21:41:50, 2013-04-06 06:50:15, 2013-04-15 04:18:48, 2013-04-15 20:27:06, 2013-04-23 20:43:29, 2013-04-30 20:39:31, 2013-06-14 00:17:17, 2013-06-18 16:45:24, 2013-07-08 10:33:06, 2013-07-25 05:00:00, 2013-09-05 14:07:31, 2013-09-25 15:31:00, 2013-09-26 15:35:00, 2013-11-12 15:49:00, 2014-01-04 01:46:27, 2014-02-02 21:48:41, 2014-02-24 02:55:00, 2014-03-05 18:42:00, 2014-07-22 00:46:00, 2014-11-11 14:15:00, 2014-11-13 16:33:00, 2014-11-21 22:17:00, 2014-12-01 20:30:00, 2014-12-05 17:57:00, 2014-12-16 19:53:00, 2015-01-13 18:28:00, 2015-02-12 22:12:00, 2015-07-11 23:54:00, 2015-07-12 00:22:00, 2015-10-18 22:57:35, 2015-10-19 00:32:40, 2015-11-28 19:01:47, 2015-11-29 17:03:00, 2015-12-06 03:02:00, 2015-12-10 13:34:00, 2016-01-03 17:45:00, 2016-01-03 17:56:00, 2016-01-16 20:43:00, 2016-05-10 01:41:00, 2016-05-12 02:01:00, 2016-05-15 14:32:00, 2016-08-01 13:15:00, 2016-08-22 22:05:00, 2016-08-23 22:10:04, 2016-10-26 17:33:48, 2016-11-26 01:36, 2016-12-05 14:42:00, 2016-12-05 19:31:00, 2017-02-03 18:00