# Thread: Sparse Matrix (Yale format)

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

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.

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!

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

it is clear for me now

6. You're very welcome. Have a good one!