449,215 Members | 1,951 Online Need help? Post your question and get tips & solutions from a community of 449,215 IT Pros & Developers. It's quick & easy.

# Sparse Matrix implemented as a doubly-linked list

 P: n/a 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. Second, can anybody point me to some existing code that implements a sparse matrix as a doubly-linked list? I've Googled sparse matrix and found dozens of libraries, but I don't know how to evaluate which of them suits my needs best. Thanks very much, Adam Jun 22 '07 #1
5 Replies

 P: n/a "ad************@gmail.com" wrote: > 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. ..... Only if you build the matrix once and then peruse it. Otherwise maintaining the pointers will be a nightmare. comp.programming is probably a better newsgroup for this. -- cbfalconer at maineline dot net -- Posted via a free Usenet account from http://www.teranews.com Jun 22 '07 #3

 P: n/a 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 = 123. ** if (DarrayError(a) || DarrayError(b)) { ** printf ("Darray error\n"); ** } ** DarrayFree(a); ** DarrayFree(b); */ -- Thad Jun 23 '07 #4 