MA5617 - Case Studies in HPC Assignment: Communication-avoiding QR Factorization
M.Sc. in High-Performance Computing MA5617 - Case Studies in HPC
Communication-avoiding QR Factorization
Rules
To submit, make a single tar-ball with all your code and a pdf of any written part you want to include. Submit this via msc.tchpc.tcd.ie by Sunday, 26. February, 2023.
Question
In this assignment, you are being asked to build a simple communication-avoiding TSQRfactorization of a tall, narrow matrix.
-
Familiarize yourself with the QR factorization routines contained in LAPACK. You will use a Householder-based QR routine to perform local, on-processor QR factorizations.
-
Implement a method called TSQR() which executes just the communication-avoiding QR-factorization of a tall-narrow matrix using the technique described in the lecture video/included technical report. It should use LAPACK’s QR factorization routine for local QR. Set your code up so that you can choose on how many nodes the matrix will be distributed. Set up a (relatively) small test problem to demonstrate that your code works.
-
Included with this assignment is are two matrices: A1 ∈ R10 ×10 and A2 ∈ R10 ×10 and right-hand sides: b1 ∈ R10 and b2 ∈ R10 . Let the Matlab notation Ai (:, 1 : k) denote the Ni × k matrix (N1 = 106 and N2 = 105 ) with the first k columns of Ai . Use your CAQR code to factor and solve Ai (:, 1 : k)xk ≈ bi for k = 200, 400, . . . , 103 .
Similarly, use CAQR to factor and solve Ai (1 : j, :)x(j) ≈ bi (1 : j) for NiNij = 2 × , 4 × , . . . , Ni .1010
Does your code fail at some point? Report if your code can solve the full problem or if breaks after a certain size. Please report all your timing results with both tables and plots.
