Graphics Reference
In-Depth Information
matrix capabilities: the regular structure of the matrices used up until now
will not accommodate the addition of solids.
There are several possible data structures for storing and manipulating
general sparse matrices. The one we will focus on is sometimes called
compressed sparse row
(or CSR) format. Here each row of the matrix is
stored as an array of non-zero values and their associated column indices.
We'll actually use two variations of CSR, a simple dynamic version (that
makes adding new non-zeros when dynamically constructing a matrix fairly
e
cient) and a static version that gives better performance in PCG.
In dynamic CSR, the array for each sparse row is stored independently
with an associated length. To support adding new non-zeros relatively
eciently, we may allocate extra storage for these arrays and keep track
of the total available; when the extra space runs out, we can reallocate
the array with double the size. This is the strategy taken in the C++
STL
vector
container for example. Often people will further maintain the
arrays in order sorted by column index, making it more ecient to find
entries or add two sparse rows together.
However multiplying the sparse matrix by a dense vector, the core of
PCG, loses some eciency with this approach: each sparse row might be
scattered in memory leading to poor cache usage. Therefore, after con-
structing a matrix using the dynamic CSR structure, we convert it to a
static CSR structure. Here just three arrays are defined, ensuring that all
matrix non-zeros are contiguous in memory:
•
a floating-point array
value
containing all non-zero values ordered
row by row,
•
an integer array
colindex
of the same length containing the corre-
sponding column indices, and
•
an integer array
rowstart
of length
n
+1 (for an
n
n
matrix) indicat-
ing where each sparse row begins in
value
and
colindex
—an extra
entry at the end points just past the end of the
value
and
colindex
arrays (i.e., contains the number of non-zeros in the matrix).
×
The small overhead of converting a dynamic CSR matrix to static format
is generally well worth it for PCG, bringing the cost back in line with our
earlier grid-based method.
You may recall that with our grid version of the matrix we optimized
the storage by exploiting symmetry, in some sense just storing the upper
(or lower) triangle of the matrix. This is generally not worthwhile with
CSR: it considerably complicates matrix operations.
