image of a large network

Network & Matrix Computations

David Gleich

Purdue University

Fall 2011

Course number CS 59000-NMC

Tuesdays and Thursday, 10:30am-11:45am

CIVL 2123

In-class quiz 5 (Solutions)

CS 59000-NMC, 8 September

Please answer the following questions. You may not use any outside references or technology. Justify and explain all answers. This quiz is for my own evaluation, so that I can provide better instruction in the course.


Let be a binary matrix. Suppose this matrix is composed of mostly ones and that the zeros are stored with a compressed-sparse row data structure. Write down an efficient algorithm to compute give the compressed sparse row data structure for ’s zeros in the arrays pointer and columns.


When the matrix is upper-triangular, then there are no updated values of the solution that are affected by the entries of the matrix, and the two iterations will be the same.

Unexpected, and correct, but slightly trivial answer When you start the two with the correct solution!

Reason you shouldn’t solve the system them When is upper-triangular, then we can employ a technique called back-substitution to solve the system without an iterative method.


Let be upper triangular:

A_{i,j} = 0 \text{ when } i > j


\mA = \bmat{A_{1,1} & A_{1,2} & A_{1,3} \\ 0 & A_{2,2} & A_{2,3} \\ 0 & 0 & A_{3,3} }.

Note that for that

x_n = b_n / A_{n,n}.

We can use this value to find now:

A_{n-1,n-1} x_{n-1} + A_{n-1,n} x_n = b_{n-1}


x_{n-1} = A_{n-1,n-1}^{-1} ( b_{n-1} - A_{n-1,n} x_n ).

Just continue in this manner through the rest of the matrix:

x_i = A_{i,i}^{-1} ( b_{i} - \sum_{j > i} A_{i,j} x_j ).

For this algorithm, note that you have to proceed backwards through the rows of the matrix.