ad************@gmail.com wrote:
Hi there,
I'm a novice C programmer working with a series of large (30,000 x
30,000) sparse matrices on a Linux system using the GCC compiler. To
represent and store these matrices, I'd like to implement the sparse
matrices as a doubly-linked list, in which each non-zero cell is
stored roughly as follows:
int rownum
int colnum
double cellvalue
cell *rightptr
cell *downptr
I think this implementation makes the most sense because I need to
traverse the matrix both across rows and down columns -- the i-j-th
cell of one matrix is calculated as the matrix-product of the i-th row
by the j-th column of the other matrix.
First, does this sound like the right approach? Any thoughts or other
ideas would be most appreciated.
It sounds reasonable if you access in the order you describe.
I suggest separating the access routines so that the application code
doesn't care what structure is being used for the sparse array.
Following is an example of a header file that I would define if I were
implementing such a 2D sparse array. The interface doesn't rely on the
structure used to implement the sparse array. You could try different
techniques for implementing the array without changing your application.
Someone here has been known to provide links to a hash table library
that could provide the basis for one implementation. ;-)
Comments welcome on the proposed interface, of course.
/* Dynamic Array Interface */
/* darray is a pointer to a dynamic sparse array descriptor. */
typedef struct darray_desc *darray;
/* Function: DarrayCreate
** Description: This function creates a dynamic sparse two-
** dimensional array with default values of zero.
** It is dynamic in the sense that storage is
** allocated for elements as stored, so a fixed size
** is not needed when the array is created.
*/
darray * /* ptr to descriptor or NULL if out of memory */
DarrayCreate (void);
/* Function: DarrayStore
** Description: This function stores a value in a specified location
** of dynamic array a. If an error occurs, x will
** not be stored.
** On entry: a is the NULL value returned by DarrayCreate.
** On exit: if return 0, x has been stored in a[i][j].
*/
int /* 0: OK, 1: out of memory */
DarrayStore (
darray a, /* darray to receive value */
int i, /* row index */
int j, /* column index */
double x /* value to be stored */
);
/* Function: DarrayGet
** Description: This function returns the last-stored value in
** a[i][j], where a is a dynamic array. If no value
** has been stored in a[i][j], 0.0 is returned.
** On entry: a is the value returned by DarrayCreate.
** On exit: a[i][j] is returned.
*/
double /* last stored value of a[i][j] */
DarrayGet (
darray a, /* darray source */
int i, /* row index */
int j /* column index */
);
/* Function: DarrayError
** Description: This function returns status indicating whether
** an access error has occurred as a result of
** calling DarrayCreate, DarrayStore, or DarrayGet
** since the call to DarrayCreate for this array.
** On entry: a is the value returned by DarrayCreate.
*/
int /* 0: no error, 1: out of memory */
DarrayError (
darray a /* darray being checked */
);
/* Function: DarrayFree
** Description: This function frees memory allocated for a dynamic
** array.
** On entry: a is the non-NULL value returned by DarrayCreate.
** On exit: The memory used for a and associated data have
** been deallocated. The value *a is no longer
** valid.
*/
void DarrayFree (
darray a /* darray to be freed */
);
/* Sample use:
** darray a, b;
** a = DarrayCreate();
** b = DarrayCreate();
** DarrayStore(a, 10, 200, 123.);
** DarrayStore(b, 3000, 4000,
** DarrayGet(a, 10, 200) + DarrayGet(b, 3001, 4000));
** // b[3000][4000] = 123.
** if (DarrayError(a) || DarrayError(b)) {
** printf ("Darray error\n");
** }
** DarrayFree(a);
** DarrayFree(b);
*/
--
Thad
