1 Consider the mesh of a discretized PDE. In which situations is the graph representing this mesh

the same as the adjacency graph of the matrix? Give examples from both Finite Difference and

Finite Element discretizations.

2 Let and be two sparse (square) matrices of the same dimension. How can the graph of

¢ £

be characterized with respect to the graphs of and ?

£ )¢%66

¢ £

3 Consider the matrix de¬ned as

¢

5 G£ ¡f

Show directly (without using Proposition 3.1 or interchange matrices) that the following three

relations hold

¢ G£ ¢

G£ ¤¢

¢ T f

G £

T 4¢ 5 F£ ¢%

f G

ud

¤§ ¥ §¢

¡

¡© © ¢ ¡ ¥ ¥ © ¡ ¥

§

¡

4 Consider the two matrices

" ¡ 3444

3444

99 8 v" 99 8 44v"

" " """

99 44" " " 4 99 "

" " ¢ " 4

v4" "

" " 44v" ¡"

""" 5

%¢

£

"5

A " 4" " A 44v"

" "¡"

"

4v4"

"""

" "

"

44v4"

"""" 4"

"

4"

"

where a represents an arbitrary nonzero element.

§¦ Show the adjacency graphs of the matrices , , , and . (Assume that there are

¤¢ £ ¢

£ ©£

¢

no numerical cancellations in computing the products and ). Since there are zero ¤¢

£ ©£

¢

f£¦£c

diagonal elements, represent explicitly the cycles corresponding to the edges when

they are present.

§© Consider the matrix . Give an interpretation of an edge in the graph of in terms

g¢ 6

£ 6

of edges in the graph of and . Verify this answer using the above matrices.

¢

£

§ Consider the particular case in which . Give an interpretation of an edge in the graph

% £

¢

of in terms of paths of length two in the graph of . The paths must take into account the

¢

6

cycles corresponding to nonzero diagonal elements of . ¢

¤ 5

§ Now consider the case where . Give an interpretation of an edge in the graph of

¢£

8 %66 in terms of paths of length three in the graph of . Generalize the result to arbitrary

¢ ¢

powers of . ¢

¦ ¥

¥

5 Consider a matrix which has the pattern

¡ 3444

¡ 99@8

9

¡ 4

¡

9

¡

A¢

5

A §¡

§ 5

§¦ Show the adjacency graph of . ¢

( ¦ 2 ¦ ¦ & ¨

¥¦ ¦ ©

§© Consider the permutation . Show the adjacency graph and new pattern

¢ £

¨

for the matrix obtained from a symmetric permutation of based on the permutation array .

¢

6 Consider a matrix which has the pattern

¡¢ 3444 ¢

999@8

¢¡ ¡ 4444

¡

99

99

¡¢ 4 A¢

59

§ ¡ 5

A ¢ §

¢

§¦ Show the adjacency graph of . (Place the 8 vertices on a circle.)

¢

¦ ¦ 2¦ (¦ ¦ ¦ ¦&

¨ ¥ ©

§© ¤

Consider the permutation . Show the adjacency graph and new

¢ £

pattern for the matrix obtained from a symmetric permutation of based on the permutation ¢

¨

array .

§ Show the adjacency graph and new pattern for the matrix obtained from a reverse Cuthill-

McKee ordering of starting with the node 1. (Assume the vertices adjacent to a given

¢

vertex are always listed in increasing order in the data structure that describes the graph.)

d¥ © g¢ ¤© ©

n¥ u¡ § £ ¥

© 6¡

©

¤ § Find a multicolor ordering for (give the vertex labels color 1, followed by those for color