Graphics Reference
In-Depth Information
fori=0ton-1
y(i) = 0
for j = rowstart(i) to rowstart(i+1)-1
y(i) += value(j)*x(colindex(j))
Figure 11.1.
Pseudocode for multiplying an
n
×
n
static CSR matrix with a dense
vector,
y
=
Ax
.
It is fairly straightforward to multiply a static CSR sparse matrix with
a dense vector; see Figure 11.1 for pseudocode. It's another matter to
generalize the incomplete Cholesky preconditioner and associated triangu-
lar solves. It turns out, for general sparsity patterns, that the previous
simplification of only having to compute diagonal entries (and reusing the
off-diagonal entries of
A
) doesn't hold, and furthermore the modified in-
complete Cholesky factorization cannot be computed with the same loop-
ordering presented earlier. It is more natural, in fact, to compute
R
=
L
T
in CSR format (or equivalently,
L
in a compressed sparse column format).
All that said, we can still define the regular incomplete factor from the
previous properties:
•
R
is upper triangular, and
R
i,j
= 0 wherever
A
i,j
=0,
(
R
T
R
)
i,j
=
A
i,j
•
wherever
A
i,j
=0,
•
Set tuning constant
τ
=0
.
97 and safety constant
σ
=0
.
25.
•
Copy the upper triangle of
A
into
R
(including the diagonal).
•
For
k
=0to
n
−
1where
R
k,k
=0:
If
R
k,k
<σA
k,k
then set
R
k,k
←
A
k,k
, otherwise set
R
k,k
←
•
R
k,k
.
R
k,j
R
k,k
Rescale the rest of the
k
'th row of
R
:
R
k,j
←
•
for stored
entries with
j>k
.
•
Loop over
j>k
where
R
k,j
is stored:
•
Set
δ
= 0 (where we keep a sum of the elements we drop).
•
Loop over
i>k
where
R
k,i
is stored:
•
If
R
j,i
is stored, set
R
j,i
←
R
j,i
−
R
k,i
R
k,j
,otherwise
δ ← δ
+
R
k,i
R
k,j
.
•
Set
R
j,j
←
R
j,j
−
τδ
.
Figure 11.2.
The calculation of the MIC(0) preconditioner
R
for general matrices
A
,usingCSRformat.
