CMPS 373 Final, Spring 2005

CMPS 373: Parallel Computing June 7, 2005 Final Exam Instructor: Fatima Abu Salem Name: Duration: 90 minutes Question 1 (60pts) Let A be a sparse m x m matrix and B a dense m x n matrix with m > n. Consider the matrix-matrix multiplication C = AB. (a) What is the time complexity of a straightforward sequential algorithm? (b) Choose distributions for A, B, and C and formualte a corresponding parallel algo- rithm. Motivate your choices of any distribution you adopt. (c) Analyse the time complexity of the parallel algorithm. Question 2 (40pts) The Conjugent Gradient (CG) method is an iterative method for solving a symmetric positive definite linear system of equations Ax = b. (A matrix A is positive definite if x Ax > 0 for all x £ 0.) The algorithm computes a sequence of approximations x*, k = 0,1,2,..., that con- verges towards the solution x. The algorithm is usually considered converged when ||r*|| < Econy||bj], where r®* = b— Ax*. Recall that for a vector x = (21, 29,...,Zn), the (Euclidean) norm is given by (x? + 23+... + 22)1/2, A sequential CG algorithm is given on the next page !. (a) Design a parallel CG algorithm based on the sparse matrix-vector multiplication discussed in class. How do you distribute the various vectors and matrix A? Motivate your design choices. (b) Analyse the time complexity of your algorithm. eee 1 All bold-face variables denote vectors, and non-bold ones denote scalars F-1 input: A: sparse n x n matrix, b: dense vector of length n. output: x: dense vector of length n, such that Ax ® b. x := x®: { initial guess } k := 0; { iteration number } ri=b— Ax; p= |[rll?s while \/p > €cony||b||&&k < kmaz do if k = 0 then psy else 8 := p/ potas p:=r+t fp; w= Ap; y= ptw; a= p/Y; xX:=x+ ap; r:=r—aw; Pold *= P; p= |r|); k= k+l],