5.5. BLOCK COMPRESSED ROW STORAGE 39
2
6
6
6
6
6
6
6
4
0 1 0 0 2
1
T
0 3 0 0
0 3
T
0 4 5
0 0 4
T
0 6
2
T
0 5
T
6
T
0
3
7
7
7
7
7
7
7
5
: (5.19)
Note that for cloth simulations there will be contributions on all diagonal elements of
the matrix. Since the matrices will be square and symmetric, we will actually only have to store
the upper triangle half of the matrix. All the other data can be deferred from this. We just
have to remember that there’s a transposed block on the other side of the diagonal when we’re
multiplying with the matrix. is is only a performance issue and not a correctness issue, so we
will continue our explanation with the full sparse matrix. Just keep this in mind when you’re
implementing your own data structure.
It’s easy to get distracted reading long boring mathematical texts, but now is a good time
to pay attention. e essence of the BCRS format is described in this paragraph. e BCRS
format works by storing the blocks sequentially per row in an array that we name blocks. Feel
free to be creative in naming your data structures. Additionally, we need to keep a list of the
associated column indices so we can figure out where in the full matrix the blocks belong. We
call this array columnIndex. e only missing information now is how many blocks there are in
each row. We encode this in an array named rowPointer by storing the accumulative number
of blocks per row. is means that row i has rowPointer
Œ
i C 1
rowPointer
Œ
i
number of
blocks.
e easiest way to understand, is to look at an example. e BCRS format for the matrix
in Equation (5.19) is stored using the following arrays:
blocks W
h
0 1 2 1 3 3 4 5 4 6 2 5 6
i
columnIndex W
0 1 4 0 2 1 3 4 2 4 0 2 3
rowPointer W
0 3 5 8 10 13
:
Note that we’re only storing non-zero blocks in our data array named blocks. Not wasting
any memory here! Well …, actually …, except for the fact that, for clarity of explanation, we’re
not exploiting the symmetry of course.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.