9.1. Matrix and Vector Multiplication


9.1. Matrix and Vector Multiplication

This example program involves mostly basic programming techniques. It demonstrates simple arithmetic and vector operations, looping with the do syntactic form, dispatching based on object type, and generating error messages.

Multiplication of scalar to scalar, scalar to matrix, or matrix to matrix is performed by a single generic procedure, called mul. mul is called with two arguments, and it decides based on the types of its arguments what operation to perform. Because scalar operations use Scheme's multiplication procedure, *, mul scalars can be any built-in numeric type (exact or inexact complex, real, rational, or integer).

The product of an m n matrix A and an n p matrix B is the m p matrix C whose entries are defined by

The product of a scalar x and an m n matrix A is the m n matrix C whose entries are defined by the equation:

Cij = xAij

That is, each element of C is the product of x and the corresponding element of A. Vector-vector, vector-matrix, and matrix-vector multiplication may be considered special cases of matrix-matrix multiplication, where a vector is represented as a 1 n or n 1 matrix.

Here are a few examples, each preceded by the equivalent operation in standard mathematical notation.

  • Scalar times scalar:

    3 4 = 12

     (mul 3 4)  12 
  • Scalar times vector (1 3 matrix):

    1/2 (1 2 3 ) = (1/2 1 3/2)

     (mul 1/2 #(#(1 2 3)))  #(#(1/2 1 3/2)) 
  • Scalar times matrix:

     (mul -2      #(#(3 -2 -1)        #(-3 0 -5)        #(7 -1 -1)))  #(#(-6 4 2)                              #(6 0 10)                              #(-14 2 2)) 
  • Vector times matrix:

     (mul #(#(1 2 3))      #(#(2 3)        #(3 4)        #(4 5)))  #(#(20 26)) 
  • Matrix times vector:

     (mul #(#(2 3 4)        #(3 4 5))      #(#(1) #(2) #(3)))  #(#(20) #(26)) 
  • Matrix times matrix:

     (mul #(#(1 2 3)        #(4 5 6))      #(#(1 2 3 4)        #(2 3 4 5)        #(3 4 5 6)))  #(#(14 20 26 32)                              #(32 47 62 77)) 

The code for mul and its helpers appears below. The first few definitions establish a set of procedures that support the matrix datatype. A matrix is a vector of vectors. Included are a procedure to create matrices, procedures to access and assign matrix elements, and a matrix predicate. Following these definitions is the definition of mul itself. Inside the lambda expression for mul are a set of definitions for help procedures that support mul.

mul checks the types of its arguments and chooses the appropriate help procedure to do the work. Each helper operates on arguments of specific types. For example, mat-sca-mul multiplies a matrix by a scalar. If the type of either argument is invalid or the arguments are incompatible, e.g., rows or columns do not match up, mul or one of its helpers signals an error. Since no standard mechanism exists for signaling errors, we use the Chez Scheme error procedure briey described in Section 2.7 to illustrate how errors might be reported.

 ;;; make-matrix creates a matrix (a vector of vectors). (define make-matrix   (lambda (rows columns)     (do ((m (make-vector rows))          (i 0 (+ i 1)))         ((= i rows) m)         (vector-set! m i (make-vector columns))))) ;;; matrix? checks to see if its argument is a matrix. ;;; It isn't foolproof, but it's generally good enough. (define matrix?   (lambda (x)     (and (vector? x)          (> (vector-length x) 0)          (vector? (vector-ref x 0))))) ;; matrix-rows returns the number of rows in a matrix. (define matrix-rows    (lambda (x)       (vector-length x))) ;; matrix-columns returns the number of columns in a matrix. (define matrix-columns    (lambda (x)       (vector-length (vector-ref x 0)))) ;;; matrix-ref returns the jth element of the ith row. (define matrix-ref    (lambda (m i j)       (vector-ref (vector-ref m i) j))) ;;; matrix-set! changes the jth element of the ith row. (define matrix-set!    (lambda (m i j x)       (vector-set! (vector-ref m i) j x))) ;;; mul is the generic matrix/scalar multiplication procedure (define mul   (lambda (x y)     ;; mat-sca-mul multiplies a matrix by a scalar.     (define mat-sca-mul (lambda (m x)        (let* ((nr (matrix-rows m))               (nc (matrix-columns m))               (r (make-matrix nr nc)))           (do ((i 0 (+ i 1)))               ((= i nr) r)               (do ((j 0 (+ j 1)))                   ((= j nc))                   (matrix-set! r i j                      (* x (matrix-ref m i j)))))))) ;; mat-mat-mul multiplies one matrix by another, after verifying ;; that the first matrix has as many columns as the second ;; matrix has rows. (define mat-mat-mul    (lambda (m1 m2)       (let* ((nr1 (matrix-rows m1))              (nr2 (matrix-rows m2))              (nc2 (matrix-columns m2))              (r (make-matrix nr1 nc2)))          (if (not (= (matrix-columns m1) nr2))              (match-error m1 m2))          (do ((i 0 (+ i 1)))              ((= i nr1) r)              (do ((j 0 (+ j 1)))                  ((= j nc2))                  (do ((k 0 (+ k 1))                       (a 0                          (+ a                             (* (matrix-ref m1 i k)                             (matrix-ref m2 k j)))))                      ((= k nr2)                       (matrix-set! r i j a)))))))) ;; type-error is called to complain when mul receives an invalid ;; type of argument.  (define type-error     (lambda (what)        (error 'mul          "~s is not a number or matrix"          what))) ;; match-error is called to complain when mul receives a pair of ;; incompatible arguments. (define match-error    (lambda (what1 what2)       (error 'mul         "~s and ~s are incompatible operands"         what1         what2))) ;; body of mul; dispatch based on input types (cond   ((number? x)    (cond      ((number? y) (* x y))      ((matrix? y) (mat-sca-mul y x))      (else (type-error y))))   ((matrix? x)    (cond      ((number? y) (mat-sca-mul x y))      ((matrix? y) (mat-mat-mul x y))      (else (type-error y))))   (else (type-error x))))) 

Exercise 9.1.1.

start example

Make the necessary changes to rename mul to *.

end example

Exercise 9.1.2.

start example

The predicate matrix? is usually sufficient but not completely reliable, since it may return #t for objects that are not matrices. In particular, it does not verify that all of the matrix rows are vectors, that each row has the same number of elements, or that the elements themselves are numbers. Modify matrix? to perform each of these additional checks.

end example

Exercise 9.1.3.

start example

Write similar generic procedures for addition and subtraction. Devise a generic dispatch procedure or syntactic form so that the type dispatching code need not be rewritten for each new operation.

end example

Exercise 9.1.4.

start example

This version of mul uses vectors of vectors to represent matrices. Rewrite the system, using nested lists to represent matrices. What efficiency is gained or lost by this change?

end example




The Scheme Programming Language
The Scheme Programming Language
ISBN: 026251298X
EAN: 2147483647
Year: 2003
Pages: 98

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net