From: David Clark
Subject: Le Lisp, and Optimisation of Matrix Calculations
Date:
Message-ID: <4qpelh$33t@badger.wmin.ac.uk>
I am writing a program in Lisp for my MSc project which requires repeated
multiplication of a square matrix. This is rather slow on my ancient 386 pc at home,
so I need to write a version for Le Lisp which is available on the Sun Workstation at
the university.
Does anyone know where I can find documentation for LeLisp. In particular; can I
define an array? I've tried make-array and even create-array with no joy though aref
works and so does vector.
Based on the PC versions a function using arrays should be fater than the list version
which is the only one that works with LeLisp.
The final program needs to perform 100+ multiplications of a 120x120 matrix so any
suggestions for improving the code shown below would be appreciated.
David Clark
MSc Knowledge Engineering, University of Westminster. UK
;time (seconds) 28x28 array on 25mhz 386 PC DOS/Windows Sun Sparc
;tested with Allegro XLISP, CLISP-I FreeLISP CLISP-C LeLisp
;matmultC 4.5 9.1 7.1 9.7 6.5 0.97
;matmultA 3.7 na 28 16 4.01
;matmultV 4.2 68 39 21 5.83
;matmultV0 3.9 22 5.82
;Matrix Calculations in LISP
;cannot define a 2d array in XLISP so we use lists
;M^n
(defun MATMULT (Matrix Times)
(DO ((Result Matrix (MATMULTc Matrix Result))
(Count 2 (1+ Count)))
((> Count Times) Result)))
;the multiplication of two matrices
;XLisp Matrix as List of Lists using cons
(defun MATMULTC (Matrix1 Matrix2)
(LET ((Tsp2 (do ((j (length Matrix2) (1- j))
(Tr nil (cons (mapcar #'(lambda (x) (nth (1- j) x)) Matrix2)
Tr)))
((eq j 0)Tr))))
(map 'list #'(lambda (m1)
(map 'list #'(lambda (t2)(reduce '+ (map 'list '* m1 t2))) Tsp2))
Matrix1)))
;versions with arrays for Allegro, FreeLisp & CLisp
;Matrix Multiplication with 2D arrays
;modified for List of List Operation in XLISP
(defun MATMULTL (MatrixA MatrixB Result)
(LET* ( (RowsA (length (car MatrixA)))
(ColsA (length MatrixA))
(ColsB (length MatrixB)) )
(DOTIMES (i RowsA Result)
(DOTIMES (j ColsB)
(setf (nth j (nth i Result))
(let ((sum 0.0))
(dotimes (l ColsA Sum)
(setf sum (+ sum (* (nth l (nth i
MatrixA)) (nth j (nth l MatrixB))))))))))))
(defun MATMULTA (MatrixA MatrixB Result RowsA ColsA ColsB)
(DOTIMES (i RowsA Result)
(DOTIMES (j ColsB)
(setf (aref Result i j)
(let ((sum 0.0))
(DOTIMES (l ColsA Sum)
(setf sum (+ sum (* (aref MatrixA i l)
(aref MatrixB l j))))))))))
;replacing 2D arrays with 1D vectors
(defun MATMULTV (MatrixA MatrixB Result RowsA ColsA ColsB)
(let ((sum 0.0)
(i1 (- ColsA))
(k2 0))
(DOTIMES (i RowsA Result)
(setf i1 (+ i1 ColsA)) ;; i1=i*m
(DOTIMES (j ColsB)
(setf sum 0.0)
(setf k2 (- ColsB))
(DOTIMES (l ColsA)
(setf k2 (+ K2 ColsB)) ;;k2= l*k
(setf sum (+ sum (* (aref MatrixA (+ i1 l))
(aref MatrixB (+ k2 j)) ))))
(setf (aref Result (+ i1 j)) sum)))))
;replacing 2D arrays with 1D vectors optimised Allegro [Fateman 1993]
(defun MATMULTV0 (vA vB vR RowsA ColsA ColsB)
(declare (optimize (speed 3) (safety 0) )
(type (simple-array single-float (*)) vA vB vR)
(fixnum RowsA ColsA ColsB))
(let ((sum 0.0)
(i1 (- ColsA))
(k2 0))
(declare (single-float sum) (fixnum i1 k2))
(DOTIMES (i RowsA vR)
(declare (fixnum i))
(setf i1 (+ i1 ColsA)) ;; i1=i*m
(DOTIMES (j ColsB)
(declare (fixnum j))
(setf sum 0.0)
(setf k2 (- ColsB))
(DOTIMES (l ColsA)
(declare (fixnum l))
(setf k2 (+ K2 ColsB)) ;;k2= l*k
(setf sum (+ sum (* (aref vA (+ i1 l))
(aref vB (+ k2 j)) ))))
(setf (aref vR (+ i1 j)) sum)))))
From: Ron Parr
Subject: Re: Le Lisp, and Optimisation of Matrix Calculations
Date:
Message-ID: <4qqgpe$sk5@agate.berkeley.edu>
You might want to check out my quick-arrays package. It implements
multi-dimensional arrays as vectors of vectors. It turns out that this
is faster than using standard arrays in many lisps. It comes with a
test program that determines how much of a speedup you can get on your
system using quick arrays. The program multiplies two large square
matrices.
The URL is: http://http.cs.berkeley.edu/~parr/quick-arrays.html
--
Ron Parr email: ····@cs.berkeley.edu
--------------------------------------------------------------------------
Home Page: http://http.cs.berkeley.edu/~parr/
Mac Tips: http://http.cs.berkeley.edu/~parr/rrrt-top.html
>>>>> "DC" == David Clark <·····@wmin.ac.uk> writes:
DC> I am writing a program in Lisp for my MSc project which requires repeated
DC> multiplication of a square matrix. This is rather slow on my ancient 386 pc at home,
DC> so I need to write a version for Le Lisp which is available on the Sun Workstation at
DC> the university.
DC> Does anyone know where I can find documentation for LeLisp. In particular; can I
DC> define an array? I've tried make-array and even create-array with no joy though aref
DC> works and so does vector.
DC> Based on the PC versions a function using arrays should be fater than the list version
DC> which is the only one that works with LeLisp.
DC> The final program needs to perform 100+ multiplications of a 120x120 matrix so any
DC> suggestions for improving the code shown below would be appreciated.
DC> David Clark
DC> MSc Knowledge Engineering, University of Westminster. UK
all the following refers to le_lisp V15.26, but should be ok for previous
le_lisp version
to create an array (k-dimensionnal) :
(makearray n1 n2 ... nk initial-cell-value)
to access a value:
(aref array n1 n2 ... nk)
to modify a value
(aset array n1 n2 ... nk new-value)
to optimise arithmetic operations:
generic 2 integer 2 floating
operator operands operands
+ add fadd
- sub fsub
* mul fmul
/ div fdiv
generic operator are more secure (they do conversions if necessary),
and do automatic type-checking and type-conversion.
add... fadd... are quicker, but when compilled
don't do any type-check. So you must be sure of the
type of the operands.
To get a doc, the best is to get in touch with ilog:
try :
·······@ilog.fr
····@ilog.fr
christophe
--
Christophe MERTZ (societe CR2A-DI) - ·····@cena.dgac.fr -
C.E.N.A - Orly Sud 205 - 94542 ORLY AEROGARE CEDEX - FRANCE
tel: (33 1) 69 57 71 10 - fax: (33 1) 60 48 70 20
web: http://www.cenaath.cena.dgac.fr/~mertz
From: David Clark
Subject: Re: Le Lisp, and Optimisation of Matrix Calculations
Date:
Message-ID: <4qu5bs$d0u@badger.wmin.ac.uk>
Thanks for the help; (makearray x y 0)
not (make-array '(x y) :initial-value 0) I should have guessed.
Now I've changed DOTIMES to DO and MAP to MAPCAR I almost have a
working program -
does (position ...) reside under an assumed name in leLisp or do
I need to write my own version?
>>>>> "DC" == David Clark <·····@wmin.ac.uk> writes:
DC> Thanks for the help; (makearray x y 0)
[...]
DC> does (position ...) reside under an assumed name in leLisp or do
DC> I need to write my own version?
I think (position seq ...) works for sequence, and matrixes are not
sequences ??!!
In fact I don't exactly understand why You should need (position ...)
By the way there is not such function in LE_Lisp (at least for
matrixes)
christophe
--
Christophe MERTZ (societe CR2A-DI) - ·····@cena.dgac.fr -
C.E.N.A - Orly Sud 205 - 94542 ORLY AEROGARE CEDEX - FRANCE
tel: (33 1) 69 57 71 10 - fax: (33 1) 60 48 70 20
web: http://www.cenaath.cena.dgac.fr/~mertz
From: David Clark
Subject: Re: Le Lisp, and Optimisation of Matrix Calculations
Date:
Message-ID: <4r1oe0$940@badger.wmin.ac.uk>
>I think (position seq ...) works for sequence, and matrixes are not
>sequences ??!!
>
>In fact I don't exactly understand why You should need (position ...)
>By the way there is not such function in LE_Lisp (at least for
>matrixes)
>
As my original program was developed for Xlisp it used lists. To save rewiting code where
efficientcy is not critical I need to create a LeLisp version of the following (the code as
shown will work in Allegro, Clisp, and FreeLisp)
(defun BUILDA (Net)
(LET* ( (Dim (length Net))
(Col (LISTCARS Net))
(Matrix (make-array (list Dim Dim) :initial-element 0)) )
(DOLIST (Row Net Matrix)
(DOLIST (J Row)
(setf (aref Matrix (position Row Net) (position J Col))
(IF (eq J (car Row))
(setf(get J 'H)(- 1 (min(reduce '+ (get (car Row) 'P))1)))
(nth (1-(position J Row)) (get (car Row) 'P))
))
))))
where Net is:
'((A B D)
(B C E)
(C F)
(D A B E G)
(E B D F H)
(F B E H I)
(G E)
(H F)
(I F))