Page 84, Exercise 4 : Fast Transpose Function

The fast transpose function achieves its efficiency through the use of two auxiliary arrays both indexed by the number of columns in the original matrix (a). Array rowTerms holds the number of columns in the original matrix (a); array startingPos holds the starting position of the column, which will become the row, in the new matrix (b). Using the example from the text, arrays a, startingPos, and rowTerms will hold the following values:

    (a)
    r c v

[0] 6 6 8
[1] 0 0 15
[2] 0 3 22
[3] 0 5 −15
[4] 1 1 11
[5] 1 2 3
[6] 2 3 −6
[7] 4 0 91
[8] 5 2 28

rowTerms
[0] 1
[1] 2
[2] 2
[3] 2
[4] 0
[5] 1

startingPos
[0] 1
[1] 2
[2] 4
[3] 6
[4] 8
[5] 8

Reading down the c column of a verifies that column 2 contains two entries. By cumulating the entries in rowTerms, we obtain the starting position for each row in the transposed matrix.