Description
Google Page Rank
The objective of this task is to develop Python code that computes the Page Rank of a set of web pages
based on the network adjacency graph. The adjacency graph is represented by a matrix G, where
Gij =
1 if ∃ a link from j to i
0 otherwise
1. [2 marks] Complete the Python function
y = SparseMatMult(G, x)
which multiplies the sparse matrix G by the vector x. The matrix is stored using the dictionaryof-keys method. You can get the key-value pairs using the built-in call G.nonzero(). See the
function’s documentation for full details.
2. [5 marks] Complete the Python function
p, iters = PageRank(G, alpha)
that finds the steady-state solution (eigenvector for λ = 1) of the Page Rank problem using the iterative method discussed in class. The output p is an R × 1 vector (where R is the number of nodes)
containing the node scores, and iters is the number of iterations the method took to converge.
Your method should use your implementation of SparseMatMult from question 1, and must not
form a full R × R matrix at any time (even as an intermediate while evaluating an expression).
To input the initial adjacency matrix, you can use dok_matrix from the scipy.sparse module
(see class demonstration Randy_demo). Your iterations should start with a uniform distribution in
p, and terminate once the solution is found to within a tolerance of 10−8
(ie. none of the elements
in p changes by more than the tolerance).
3. [5 marks] Consider the small web shown in the figure below, where each bi-directional arrow
indicates two links, one in each direction.
0
1
2
4
3
5
6
7
8
9
10
(a) Edit the notebook to create the corresponding sparse matrix G. Again, you should create a
dok_matrix using the scipy.sparse module.
(b) Run your PageRank function on the network with an α-value of 0.85. Create a stem plot of
the node scores.
(c) Run PageRank for α-values in the range [0, 1], in increments of 0.05. Plot the number of
iterations it takes to converge over that range of α values (remember to label your axes). What
do you notice about the relationship between α and the number of iterations?
(d) Create a stem plot of the node scores for α = 0.05, and another plot for α = 0.95? (Do I need
to mention axis labels again?) How does a low α value affect the node scores?
LU Factorization
4. [6 marks] Consider the system of equations:
12×1 + 12×2 − 24×3 − 48×4 = −60
4×1 + 2×3 + 8×4 = −4
6×1 + 4×2 − 11×3 − 16×4 = −30
−4×1 − 12×2 + 20×3 + 40×4 = 36
(a) Write the coefficient (system) matrix A and the right-hand-side vector b so that Ax = b.
(b) By manual calculation (showing your work), compute the LU factorization (with row pivoting) of the system matrix in part (a). That is, find a permutation matrix P, a unit-diagonal,
lower-triangular matrix L, and an upper-triangular matrix U such that P A = LU.
(c) Solve the system manually using the LU factorization above. Show your work.
5. [7 marks] Consider the linear system of equations
2 3 1
6 8.9999 6
4 8 11
x1
x2
x3
=
1
2
−2
. (1)
(a) Evaluate an accurate solution to (1). You may use Python’s numpy.linalg.solve function.
You do not have to show how you got the solution, but write the solution in your answer, and
call it x
(true)
.
(b) Simulating 5-significant-digit rounding by hand, solve (1) using Gaussian elimination without row pivoting, followed by back substitution. Call your answer x
(no-pivot). Show your
work.
(c) Simulating 5-significant-digit rounding by hand, solve (1) using Gaussian elimination with
row pivoting, followed by back substitution. Call your answer x
(pivot). Show your work.
(d) Compute the relative error for each of x
(pivot) and x
(no-pivot) using the L
2
(Euclidean) norm,
and x
(true) as the true solution.
6. [3 marks] Suppose A and B are both N × N nonsingular matrices. Give an algorithm to solve the
N × N linear system ABx = y for x in O(N2
) flops, given the LU factorizations LAUA = PAA and
LBUB = PBB.
In your algorithm, you may use matrix-vector type products, as well as the functions:
ForwardSub(L, y): Solves Lx = y for x using the forward substitution method, and returns the
solution vector.
BackwardSub(U, y): Solves Ux = y for x using the backward substitution method, and returns
the solution vector.
What to submit
You must submit a series of PDF documents to Crowdmark. For each coding question, export your
jupyter notebook to PDF. When a proof or manual calculation is requested, you can typeset your solution
(eg. using LATEX or Word), or write your solution by hand.
In either case, your solution should also be
submitted as PDF. If you submit photos of handwritten work, it is your responsibility to ensure that
they are legible.
Submit the following PDF documents:
1. A single PDF of the notebook containing solutions for all of Q1, Q2, and Q3
2. A PDF for Q4
3. A PDF for Q5
4. A PDF for Q6
