Download 4 - Forth Interest Group

Transcript
Listing One. Sparse matrix code.
elementofthezero-throwin
.........................................................
\
\
\
\
Each
1) A
2) A
3) A
4) A
5 A
/ \:
the sparse matrix; the i x r e t h
element ofthe column anchor 1
array points to the first elementof the zero-thcolumn in
the sparse matrix; and so on.
The right pointer of each
sparse-array element leads to
the next element in the same
row. Similarly, the down
pointer of each sparse-array
element points to the next
element in the same column.
A special constant (65535,
defined as NIL) acts as an
end-of-list indicator.
I!
1'
Space Considerations
In terms of physical space,
a sparse-matrix element (as I
have defined it) requires 16
bytes. Each row and column
entry is one byte, allowing
matrices with logical dimen-
I
\
I
sparse matrix element consists of 5 components :
row value (byte)
1
column value (byte)
right-pointer...points to next member in same row (word)
down-pointer.. .points to next member in same column (word)
pay load. . .the actual value
1
\ In this implementation, the payload is a 10-byte floating\ point number. The total size of an element is 16 bytes.
\ *****************
\ * * CONSTANTS * *
\ *****************
\ Indicates end of list
65535 CONSTANT NIL
\ *****************
\ * * VARIABLES * *
\ *****************
\ SMATRIX-BASE holds the base address of the memory block
\ holding the sparse matrix elements
VARIABLE SMATRIX-BASE
\ Sparse matrix elements not in use are kept on an available
\ list. SMATRIX-AVAIL-BASE is the root pointer of that list
VARIABLE SMATRIX-AVAIL-BASE
\ #SMATRIX-ELEMS holds the number of elements in the
\ sparse matrix.
VARIABLE #ISMATRIX
-ELEMS
\ We need two 1-dimensional arrays to "anchor" the sparse
\ matrix. . .one anchors the rows, the other anchors the columns.
columns.Youcaneasil~extend \ These are arrays of 16-bit words.
\ Pointer to base of row-anchoring array
this limit by changing the row VARIABLE ROWS-ARRAY
VARIABLE COLS-ARRAY
\ Pointer to base of column-anchoring array
and column entries to 16-bit
words and modfying specific \ Routines that add to and remove elements from the matrix need
constants in the source code. \ to know the previous element in the current vector.
\ We'll keep that item here.
The right and down pointers VARIABLE PREV ELEM
are 16-bitseach, allowing for a
\ Operations on the sparse array usually take place on row or
total of 64K elements.
\ column vectors. This variable points to the address of the
The payload in my \ anchoring pointer to the current row or column vector we're
implementation is a ten-byte, \ working in.
extended floating point (as VARIABLE R/C-BASE
up to 256 rows by 256
defined in Apple's SANE documentation). Consequently,
each sparse array element
requires six bytes beyond an
element in a standard array
implementation.
When should you use a
sparse matrix storage method
like the one shown here? k t a
equal the number of rows in a
matrix, and b equal the number of columns in a matrix. If
you're going to use a sparse
matrix, then some of the eleNovember 1993 December
\ The sparse matrix has to know how big it is; these variables
\ hold the dimensions.
VARIABLE #SMATRIX-ROWS
VARIABLE #SMATRIX-COLS
\ Following variables are vectors to functions that indicate
\ whether we're searching down through a column or across
\ through a row.
VARIABLE NEXT FUNC
VARIABLE IDX-FUNC
* * LOW-LEVEL DEFINITIONS * *
\
\
...........................
:
:
-ROT ROT ROT ;
ENDIF [COMPILE] THEN
;
IMMEDIATE
\ Following words calculate the address of various components
8
Forth Dimensions