# help with sparse matrix

• 10-18-2005, 07:39 PM
jrhaley123
help with sparse matrix
I need to create a sparse matrix implementation. Only allocate space for non-zero matrix elements. Implement methods for addition, subtraction, multiplication and determinant. Here is how I want to implement it:

Matrix is an array of linked lists.

Each linked list represents a row.

Each entry in the linked list has a value and a column associated with it.

I need help with the setEntry method and creating the array of linked lists.

I can include the code I've done so far.
• 10-18-2005, 07:50 PM
nspils
What data will each node in your list hold?

How will you identify each node - for sorting or other such purposes?

You can find a lot of information about using linked lists like this to represent a structure which can also be represented by a sparse matrix - search for GRAPH functions ... [ google "java graph" or "java graph linked list"]
• 10-18-2005, 08:20 PM
nspils
So, if there is a "value" at the "coordinate", you create a node. That node will hold a "key" (the column) and a "value" ( the value stored in the column),

An easy implementation will use ArrayLists - one of which [ a "RowNode" ArrayList] will have as many items as the matrix has rows, and each entry in the ArrayList will hold as its "value" a reference to it's "tail" or "child" or "EdgeNode" array list, which will hold as many nodes as there are values in that row.

To perform your functions, you select the RowNode which reprents your row of interest, then walk that node's EdgeNode ArrayList. For each EdgeNode you have a column (the key) and a value. Extract that data and perform your function.
• 10-18-2005, 08:29 PM
mr1yh1
entries = new IntegerNode[numberOfRows][numberOfColumns];

its your biggest and basic mistake.

imagine:
000000000000000000000000000000000000100000000
000000000000000000000000000000000000100000000
000000000000000000000000000000000000100000000
000000000000000000000000000000000000100000000
000000000000000000000000000000000000100000000
000000000000000000000000000000000000100000000
000000000000000000000000000000000000100000000
000000000000000000000000000000000000100000000
000000000000000000000000000000000000100000000
000000000000000000000000000000000000100000000

a sparse matrix use memory only for 10 element ( which are 1 )
but you waste space for whole matrix. ( 450 elements )
• 10-18-2005, 08:41 PM
nspils
If you're going to do this, there is work involved here coding your RowNode and EdgeNode classes. [if you just used lists which would store "0" as a value for the columns where there is no value it would be easier ...] The most important part is gaining access to the EdgeList contained in your RowNode, and then reporting out the value held in each of the EdgeNodes.

Some psuedocode:

ArrayList<RowNode> rowList = new ArrayList<RowNode>();

Code:

```for (int i = 0; i < #rows; i++ ) {     RowNode tempNode = new RowNode( new ArrayList<EdgeNode>() );     rowList.add( tempNode ); }```
Now, for each column with a value in row 1, add an EdgeNode to the EdgeList held in (referenced by) the RowNode ...

Code:

```for (row 0 to n-1 ) {     for (column 0 to m-1)     {         if( value )         {             create EdgeNode( key = column number, value = value in quadrant );             add this EdgeNode to the EdgeList - RowList.get(row number).add(EdgeNode);           }     } }```
• 10-18-2005, 08:53 PM
nspils
That is Java 5 - all of the containers are now "generic" so that you can tell the compiler/interpreter what datatype is supposed to be held in the container; type checking occurs as objects are added to the container and you don't have to check types (and perform casting) as you get or remove items from the container.

You aren't forced to use this "generic" syntax but you are likely to get a message (warning) if you don't.
• 10-18-2005, 08:55 PM
nspils
take out the <> content ...
• 11-19-2005, 07:18 PM
Qatar
I have the same prob. but with C++

• 09-28-2013, 10:48 PM
keri1
I am trying to implement your pseudocode, and it's not working. I think I am not casting my variables correctly. I am using only the ListNode class...and not separating the Edge/Row class. Is that ok?

//create my rows arraylist
for (int i = 0; i < numrows; i++ )
{

ListNode tempNode = new ListNode( new ArrayList<ListNode>(), null); //columnnode
}

//for each column with a value in row 1,
//add a column node to the column list held in (referenced by) row

ListNode c = (ListNode) rowList.iterator();
for (int j = 0; j < numrows; j++)
{
for (int k = 0; k < numcols; k++)
{
if ( != null)
{
ListNode colNode = new ListNode( new ArrayList<ListNode>(), null);