help with sparse matrix


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 9 of 9

Thread: help with sparse matrix

  1. #1
    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. #2
    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. #3
    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. #4
    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 )

  5. #5
    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>() );
        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);
              }
         }
    }

  6. #6
    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. #7
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    take out the <> content ...

  8. #8
    Join Date
    Oct 2005
    Posts
    12
    I have the same prob. but with C++
    http://forums.devx.com/showthread.ph...ghlight=sparse

    please help

  9. #9
    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
    rowList.add( tempNode );
    }


    //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);
    colList.add(colNode.setData(rowList.get(j)));
    }

    }
    }

Similar Threads

  1. Replies: 0
    Last Post: 04-24-2003, 05:42 PM
  2. Web Matrix
    By Zane Thomas in forum .NET
    Replies: 26
    Last Post: 06-20-2002, 10:00 PM
  3. Free ASP.NET Web Matrix Design/Editor Tool Released
    By ASPSmith Training in forum dotnet.announcements
    Replies: 0
    Last Post: 06-18-2002, 03:39 AM
  4. Dot matrix printer
    By Dan Thibodeaux in forum .NET
    Replies: 1
    Last Post: 05-29-2002, 10:49 AM
  5. Replies: 3
    Last Post: 06-20-2000, 07:48 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center