Thread: 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!

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.

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!

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.

Thanks Adrian,
it is clear for me now

You're very welcome. Have a good one!