3 5 ) I

Chapter 3 discussed a general greedy approach for multicoloring a graph. Given a general

˜

sparse matrix , this inexpensive technique allows us to reorder it into a block form where

the diagonal blocks are diagonal matrices. The number of blocks is the number of colors.

For example, for six colors, a matrix would result with the structure shown in Figure 12.5

where the ™s are diagonal and , are general sparse. This structure is obviously a £

5

C„

generalization of the red-black ordering.

c„

F

¨„

¤„

„

E ¦„

„

% #

3¡

!

A six-color ordering of a general sparse matrix.

Just as for the red-black ordering, ILU(0), SOR, or SSOR preconditioning can be used

on this reordered system. The parallelism of SOR/SSOR is now of order where is Ei

y y

the number of colors. A loss in ef¬ciency may occur since the number of iterations is likely

to increase.

A Gauss-Seidel sweep will essentially consist of scalings and matrix-by-vector y e #y

products, where is the number of colors. Speci¬cally, assume that the matrix is stored in

y

the well known Ellpack-Itpack format and that the block structure of the permuted matrix

}

is de¬ned by a pointer array . The index is the index of the ¬rst row in the -th

X qw

y Y X qw

y Hx Y H

˜ ˜

} }

¢

block. Thus, the pair represents the sparse matrix consisting

¡ ¡

t d i Vi x

e t d i eVi x t

˜

of the rows to in the Ellpack-Itpack format. The main diagonal of is assumed to

Vi

e di

™ —t

7 —— p w7 z p — |w z

˜ { { | |

§U

“£§

¢ ¢

¡

4 ¢

$#

! § "#

£

be stored separately in inverted form in a one-dimensional array . One single step of

¡4 w

the multicolor SOR iteration will then take the following form.

”9 ) 6 9&$ 54 '2

'6

™Y # vx¤…¨©§¥¢

¡ ¦ ¦¤ §0 ) ¡§§¡¨' ' 7 § 2 8 4 §&%¤¥G

¦ @

6 ©$0¦

2

£¨ %

¢ 8

@

1. Do col = 1, ncol

2. n1 = iptr(col)

3. n2 = iptr(col+1) “ 1

4. y(n1:n2) = rhs(n1:n2)

5. Do j = 1, ndiag

6. Do i = n1, n2

7. y(i) = y(i) “ a(i,j)*y(ja(i,j))

8. EndDo

9. EndDo

10. y(n1:n2) = diag(n1:n2) * y(n1:n2)

11. EndDo

R 3 i

In the above algorithm, is the number of colors. The integers and set in lines eVi d i }

R 3

2 and 3 represent the beginning and the end of block . In line 10, is mul- eVi x di

£

c

tiplied by the diagonal which is kept in inverted form in the array . The outer ¡4 w

v

„

loop, i.e., the loop starting in line 1, is sequential. The loop starting in line 6 is vectoriz-

able/parallelizable. There is additional parallelism which can be extracted in the combina-

tion of the two loops starting in lines 5 and 6.

u hrw i u u ’

’

…

& & u¥

70 3 d

&

¨ '

¨

–•

—

The discussion in this section begins with the Gaussian elimination algorithm for a general

sparse linear system. Parallelism in sparse Gaussian elimination can be obtained by ¬nd-

ing unknowns that are independent at a given stage of the elimination, i.e., unknowns that

do not depend on each other according to the binary relation de¬ned by the graph of the

matrix. A set of unknowns of a linear system which are independent is called an indepen-

dent set. Thus, independent set orderings can be viewed as permutations to put the original