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