LISP - Matrix Multiplication

Lisp Project: Implementing Matrix Multiplication

Matrix multiplication is a fundamental operation in fields like computer graphics, scientific computing, and machine learning. This chapter will guide you through implementing it in Common Lisp as a practical learning exercise.

Disclaimer: For production-level scientific computing, it is highly recommended to use a dedicated, optimized library like Magicl, which can be installed via Quicklisp. Our implementation is for educational purposes.

Data Representation: Using 2D Arrays

While you can represent matrices using lists of lists, the natural and more performant choice in Common Lisp is a 2D array. Arrays provide fast, constant-time access to elements, which is crucial for numerical computations.

;; Create a 2x3 matrix (2 rows, 3 columns) initialized with zeros
(make-array '(2 3) :initial-element 0)

;; Access the element at row 1, column 2
(let ((matrix (make-array '(2 3) :initial-contents '((1 2 3) (4 5 6)))))
  (aref matrix 1 2)) ; Returns 6

The Logic of Matrix Multiplication

To multiply matrix A (dimensions m x n) by matrix B (dimensions n x p):

• Compatibility: The number of columns in A (n) must equal the number of rows in B (n).
• Result Dimensions: The resulting matrix C will have dimensions m x p.
• Calculation: Each element C(i, j) is the dot product of the i-th row of A and the j-th column of B.

Implementation

We will write a function multiply-matrices that takes two 2D arrays and returns their product as a new 2D array. We will use the loop macro for a clean and efficient implementation.

matrix-ops.lisp

(defun multiply-matrices (matrix-a matrix-b)
  "Multiplies matrix-a by matrix-b and returns the resulting matrix."
  (let* ((dims-a (array-dimensions matrix-a))
         (dims-b (array-dimensions matrix-b))
         (rows-a (first dims-a))
         (cols-a (second dims-a))
         (rows-b (first dims-b))
         (cols-b (second dims-b)))

    ;; Check for dimension compatibility
    (unless (= cols-a rows-b)
      (error "Matrix dimensions are incompatible for multiplication."))

    ;; Create the result matrix, initialized to 0.0 for floating point precision
    (let ((result (make-array (list rows-a cols-b) :initial-element 0.0)))
      (loop for i from 0 below rows-a
            do (loop for j from 0 below cols-b
                     do (loop for k from 0 below cols-a
                              do (incf (aref result i j)
                                     (* (aref matrix-a i k)
                                        (aref matrix-b k j))))))
      result)))

;; --- Example Usage ---
(let ((matrix-a (make-array '(2 3) :initial-contents '((1 2 3)
                                                      (4 5 6))))
      (matrix-b (make-array '(3 2) :initial-contents '((7 8)
                                                      (9 10)
                                                      (11 12)))))
  (let ((result (multiply-matrices matrix-a matrix-b)))
    (format t "Matrix A:~%~a~%" matrix-a)
    (format t "Matrix B:~%~a~%" matrix-b)
    (format t "Result C:~%~a~%" result)))

Output

Matrix A:
#2A((1 2 3) (4 5 6))
Matrix B:
#2A((7 8) (9 10) (11 12))
Result C:
#2A((58.0 64.0) (139.0 154.0))

Testing Our Function

Good code should be testable. A simple way to test our function is to use assertions. For example, multiplying any matrix by the identity matrix should yield the original matrix. We can use assert to verify this.

(defun test-matrix-multiplication ()
  "A simple test case for our function."
  (let* ((matrix (make-array '(2 3) :initial-contents '((1 2 3) (4 5 6))))
         (identity-matrix (make-array '(3 3) :initial-contents '((1 0 0)
                                                                  (0 1 0)
                                                                  (0 0 1))))
         (result (multiply-matrices matrix identity-matrix)))
    ;; `equalp` compares arrays element by element.
    (assert (equalp result matrix))
    (format t "Test passed!~%")))

;; Run the test
(test-matrix-multiplication)