DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: help with sparse matrix

#### Hybrid View

1. Registered User
Join Date
Oct 2005
Posts
1

## 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.

2. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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"]

3. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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.

4. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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>();

create your RowNode arraylist.

Code:
```for (int i = 0; i < #rows; i++ )
{
RowNode tempNode = new RowNode( new ArrayList<EdgeNode>() );
}```
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);
}
}
}```

5. Registered User
Join Date
Sep 2013
Posts
2
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);
}

}
}

6. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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.

7. Registered User
Join Date
Sep 2005
Location
istanbul / Turkey
Posts
133
entries = new IntegerNode[numberOfRows][numberOfColumns];

its your biggest and basic mistake.
please first search about sparse matrix , why its used.

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 )

8. Registered User
Join Date
Oct 2005
Posts
12
I have the same prob. but with C++

9. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
take out the <> content ...

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise
 Questions? Contact us. C++ Web Development Wireless Latest Tips Open Source

×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.