Results 1 to 6 of 6

Math Help - Sparse Matrix (Yale format)

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    3

    Sparse Matrix (Yale format)

    Dear All,

    I am reading about Sparse matrix article on Sparse matrix - Wikipedia, the free encyclopedia site. I do not follow how the "AI" array is created.

    Could anybody help me to understand Yale format? Some alternative source would be helpful too?

    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    IA measures where in vector A (which has just been constructed) the next row starts, so to speak. The ith component of IA gives the index in A of the number that begins the ith row. If this doesn't make sense for you, consider trying to re-construct the original matrix from the Yale representation. I'm not sure myself what the last component of IA means. In the wiki example, the 0, 2, and 4 make sense; the 6 has me mystified. Another few examples would probably clear that up. This clears things up a bit, I think.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    3
    Thanks Ackbeet for your response!

    My problem is the IA(3) = 6, I can not understand how they get it. Having the matrix(SM) example in wikipedia article, and definition for AI, I am trying to iterate as follows:
    For i = [0, 3]
    Row i = 0 first non-zero value is 1 and has index 0 in A, therefore IA(0) = 0;
    Row i= 1 first non-zero value is 3 and has index 2 in A, therefore IA(1) = 2;
    Row i= 2 first non-zero value is 1 and has index 4 in A, therefore IA(2) = 4;
    Row i=3 (???) out of range in our SM ....

    I am trying to understand this sentance: "Row i of the original matrix extends from A(IA(i)) to A(IA(i+1)-1), i.e. from the start of one row to the last index before the start of the next." could you reformulate it please for me?

    Thanks a lot!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    I think the answer is in this statement, from WikiAnswers: "The length of row i is determined by IA(i+1) - IA(i). Therefore IA needs to be of length N + 1." You have to have the 6 in there in order to determine the nonzero length of the last row of the original matrix. That is, 6 - 4 = length of row i of the original matrix.

    It all comes down to the fence-post problem (the source of many "off-by-one" errors in computer science): if you have a fence with posts and lengths, and the fence is in a straight line, how many lengths are there compared to how many posts? Answer: there must be one more post than there are lengths of fence. However, if the fence is in a circle, the number of posts and the number of lengths are the same.

    The statement, "Row i of the original matrix extends from A(IA(i)) to A(IA(i+1)-1), i.e. from the start of one row to the last index before the start of the next." could be paraphrased thus, in the example on wiki:

    Row 1 of the original matrix extends from A(IA(1)) to A(IA(1+1)-1), or from A(2) to A(4-1), or from A(2) to A(3). Thus, the entries in row 1 are the 2nd and 3rd entries of vector A: 3 and 9.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2010
    Posts
    3
    Thanks Adrian,
    it is clear for me now
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    You're very welcome. Have a good one!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: August 16th 2011, 10:44 AM
  2. Sparse approximations in R^n
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: March 24th 2010, 03:57 AM
  3. format
    Posted in the Calculus Forum
    Replies: 2
    Last Post: December 14th 2008, 02:17 PM
  4. Primes more and more sparse?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 10th 2007, 07:32 AM

Search Tags


/mathhelpforum @mathhelpforum