473,686 Members | 3,394 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Sparse Matrix implemented as a doubly-linked list

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 9709
"ad************ @gmail.com" <ad************ @gmail.comwrite s:
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
This sounds feasible, but I'd like to point out that this is not
what I would call a doubly linked list. The term "doubly linked
list" usually refers to a structure in which a pair of pointers
in each element link to the previous and the next item in the
list. In your structure, on the other hand, the pointers do not
allow a single list to be traversed in both forward and reverse
order. You have a pair of singly linked lists, not just one
doubly linked list.
First, does this sound like the right approach? Any thoughts or other
ideas would be most appreciated.
It sounds feasible, but I know very little about matrix arithmetic.
--
"IMO, Perl is an excellent language to break your teeth on"
--Micah Cowan
Jun 22 '07 #2
"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.programmin g is
probably a better newsgroup for this.

--
<http://www.cs.auckland .ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfoc us.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
cbfalconer at maineline dot net

--
Posted via a free Usenet account from http://www.teranews.com

Jun 22 '07 #3
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
Jun 23 '07 #4
<ad************ @gmail.comwrote :
...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
Unless your needs are unique, or you want to implement your own
library as a learning stepping stone to greater things, I think you
would be better off using an already invented wheel.
>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.
That may or not be adequate depending on the distribution pattern of
the non-zero cells, which in turn, depends on the problems you are
trying to solve. For example, if all the non-zero elements in a single
column are clustered in one (or at most a few) group(s) of consecutive
cells, other implementations could be used, more space/time/both
efficient. (Search for "sparse matrix collection" for more examples)
>Second, can anybody point me to some existing code that implements a
sparse matrix as a doubly-linked list?
As long as a sparse matrix package provides the functionality and
performance you need, for the particular type of problems you need to
solve, why should you care if internally it uses single, double, or
triple linked lists?

As a starting point, check the CSparse package from the book "Direct
Methods for Sparse Linear Systems":

http://www.ec-securehost.com/SIAM/FA02.html
http://www.cise.ufl.edu/research/sparse/CSparse/
http://www.cise.ufl.edu/research/sparse/

Source code snippet:
....
#define CS_COPYRIGHT "Copyright (c) Timothy A. Davis, 2006-2007"

/* --- primary CSparse routines and data structures
------------------------- */
typedef struct cs_sparse /* matrix in compressed-column or
triplet form */
{
int nzmax ; /* maximum number of entries */
int m ; /* number of rows */
int n ; /* number of columns */
int *p ; /* column pointers (size n+1) or col indices (size
nzmax) */
int *i ; /* row indices, size nzmax */
double *x ; /* numerical values, size nzmax */
int nz ; /* # of entries in triplet matrix, -1 for
compressed-col */
} cs ;
....
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,
Right. There are many sparse matrix libraries, some generic, some
optimized for a particular problem domain.
A group or mailing list on mathematics may be a better place than
c.l.c to ask about their suitability to your application.

Roberto Waltman

[ Please reply to the group,
return address is invalid ]
Jun 24 '07 #5
Thank you all for the comments. I would definitely prefer to find a
suitable library rather than write my own. Because I need to traverse
both rows and columns, I've been looking for an implementation like
the one I described -- CSparse (for example, but many others are
similar) uses a column-dominant implementation, meaning row-based
operations will be much slower. Having said that, Roberto Waldman is
right, all I care about is whether the library will be "fast enough",
it need not be optimally fast. I'll give it a try. Thanks again
everyone,

Adam

Jun 25 '07 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

11
2542
by: Michael Bader | last post by:
Hi, I'm currently working on a matrix multiplication code (matrix times matrix), and have come along some interesting/confusing results concerning the running time of the (apparently) same algorithm, when implemented in C or C++. I noticed that the implementation in C is faster by a factor of 2.5 compared to a identical(?) C++-implementation. The basic algorithm in C is:
0
1806
by: George Sakkis | last post by:
Is there any sparse matrix package compatible with Numeric/Numarray ? Ideally, the implementation of a matrix (dense/sparse) should be transparent to the application. However the APIs of the only packages I'm aware of -- the Sparse module in Scipy and PySparse --are both pretty incomplete compared to (dense) numeric arrays. Any alternatives ? George
7
14243
by: mariaczi | last post by:
Hi, I code class to storage sparse matrix row compressed and i have a problem with implements method to setVal and addVal. I will replace later this methods overloaded operator(). Please, can You help me? Thanks in advance. I write this, but it's not so good :(
20
5223
by: Frank-O | last post by:
Hi , Recently I have been commited to the task of "translating" some complex statistical algorithms from Matlab to C++. The goal is to be three times as fast as matlab ( the latest) . I've used various techniques ( loop unrolling, loop jamming...) and tried some matrix libraries : newmat (slow for large matrix) , STL (fast but ..not usefull) , hand coding (brain consuming...), and recently Meschach...
2
1613
by: eriwik | last post by:
I'm working on an application that performs calculations on triangles of a 3D-model. As part of those computations I have to calculate a value for each pair of triangles and the number of triangles can be quite large (testmodel has 16500 triangles). Each triangle has a ID-number, however the number-range does not start from 0 but usually somewhere in the range of 10000-100000 and are not neccesarily contigious. My problem is to store the...
7
2659
by: dolcetheking | last post by:
I have this sparse matrix |5| | | | | | |4| |7| | | | | | | | |1| |3| | | | | | | |2| and I need to make a vector V(6)={5,4,7,1,3,2} I DONT KNOW HOW TO DO THIS IN C++
6
3877
by: hvmclrhu | last post by:
Hi I have a big problem. When we compile serial.c with gcc, I get this error program is generating the sparse matrix Segmentation fault I think ı have to use malloc() but I don't know how to use and add this function in my program. Could you help me please? Thank you for your help... #include <stdio.h> #include <math.h>
5
7561
by: Poseidon13 | last post by:
Hi everyone,
17
2730
by: Andrea Taverna (Tavs) | last post by:
Subject: Initialization of a const matrix implemented as pointer-to-pointer Hello everyone. I've got the following matrix definition in a source file static const char **a; I need it to be initialized as an array of strings, something like
0
8584
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, weíll explore What is ONU, What Is Router, ONU & Routerís main usage, and What is the difference between ONU and Router. Letís take a closer look ! Part I. Meaning of...
0
9054
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
8932
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
8778
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
5796
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4532
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2945
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2205
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
1934
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.