Lispology

About me

Feeds

Multiplying matrices using functional programming

16th October 2024

The most efficient way to represent matrices in Common Lisp is as two-dimensional arrays, and there are matrix libraries that work with matrices in this representation.

However, for simple applications it's convenient to represent matrices as lists of lists. This has the advantage that operations such as matrix multiplication can be written very simply in a functional way, by building up the following functions transpose, dot, columns, and multiply.

Representing matrices

For example, a 4 x 3 matrix A would be represented as a list of lists as follows:

(defparameter a '((1 0 1)
                  (2 1 1)
                  (0 1 1)
                  (1 1 2)))

A 3 x 3 matrix B would be represented:

(defparameter b '((1 2 1)
                  (2 3 1)
                  (4 2 2)))

Transpose

The first function we need is transpose, which flips a matrix around its diagonal, converting an n x m matrix into an m x n matrix. This can be written:

(defun transpose (lst)
  (apply #'mapcar #'(lambda (&rest x) x) lst))

Testing it on the matrix A:

> (transpose a)
((1 2 0 1) (0 1 1 1) (1 1 1 2))

Dot

The next function we need is dot, which calculates the dot product of two 1 x n vectors:

(defun dot (x y)
  (reduce #'+ (mapcar #'(lambda (x y) (* x y)) x y)))

For example:

> (dot '(1 0 1) '(1 2 4))
5

which is the dot product of the vectors corresponding to the first row of A and the first column of B.

Columns

Next, columns gives the matrix product of a 1 x n matrix and an n x m matrix:

(defun columns (r y)
  (mapcar #'(lambda (c) (dot r c)) (transpose y)))

For example:

> (multiply '((1 0 1)) b)
((5 4 3))

which multiplies the first row of A, a 1 x 3 matrix, by B, a 3 x 3 matrix, to give a 1 x 3 matrix.

Multiply

Finally, multiply combines these functions to multiply two arbitrary matrices:

(defun multiply (x y)
  (mapcar #'(lambda (r) (columns r y)) x))

Trying it with our two original matrices:

> (multiply a b)
((5 4 3) (8 9 5) (6 5 3) (11 9 6))

which gives the correct 4 x 3 matrix product.

The full set of functions

Here's the full set of functions to implement matrix multiplication:

(defun transpose (lst)
  (apply #'mapcar #'(lambda (&rest x) x) lst))

(defun dot (x y)
  (reduce #'+ (mapcar #'(lambda (x y) (* x y)) x y)))

(defun columns (r y)
  (mapcar #'(lambda (c) (dot r c)) (transpose y)))

(defun multiply (x y)
  (mapcar #'(lambda (r) (columns r y)) x))

Previous: Faster way to reverse the bits in a word