High-Performance Matrix Computations --- 2011
Basic knowledge of numerical linear algebra.
Principles of algorithms and programming.
Familiarity with Matlab and C.
This course is research and programming oriented.
Summer semester 2011.
CAMPUS #: 11ss-24886
Prof. Paolo Bientinesi & Prof. Martin Buecker
Mondays, 17.15-18.45, AICES R432 (Rogowski Building - Schinkelstrasse 2)
Tuesdays, 17.00-18.30, AICES R432 (Rogowski Building - Schinkelstrasse 2)
Tuesdays, 11am-1pm, AICES R432 (Rogowski Building - Schinkelstrasse 2)
First meeting: Tuesday, April 5th, 5pm.
Lectures begin: Monday, April 11th, 5.15pm.
Introduction (Paolo & Martin).
April 11th & 12th
ALU, memory hierarchy, pipelining, caching, cost metrics, performance.
Examples: DGER, DGEMM.
Reference: "Computer organization and design: the hardware/software interface", by
David A. Patterson and John L. Hennessy.
April 18th & 19th
Parallel performance, scalability.
May 2nd, 3rd
collective communication, 2D matrix distribution, analysis of MV; Strassen.
Intro to iterative methods. (Martin)
Linear systems vs. eigenproblems.
Question (BLAS 3): Can you use BLAS3 routines if your matrices are stored by rows?
Program (LAPACK): Write a program that computes the
eigenvalues W and eigenvectors Z of a symmetric matrix A
using the Divide & Conquer method. Check the correctness of
your program by computing the residual ||A Z - Z W|| and the
orthogonality ||Z^T Z - I||. Link your program against an
optimized BLAS (GotoBLAS, MKL, ...), and if possible compare
the timings with the reference (unoptimized) BLAS.
May 16th & 17th
Generalized, standard, tridiagonal eigenproblems;
reductions & backtransformations.
Program (Mathematica/Matlab): Write a program that mimics the proof of the second Gerschgorin's theorem.
May 23th & 24th
Blocked reduction to tridiagonal form;
bisection, Sturm's count.
May 30th & 31th
GPU programming. (Christian Lessig)
On the design of display processors.
T. H. Myer and I. E. Sutherland.
Commun. ACM 11(6) 1968.
June 6th & 7th
The algorithm of Multiple Relatively Robust Representations (MRRR).
Parallelization for distributed and shared memory architectures.
June 18th & 19th
June 25th & 26th
July 4th & 5th
Sparse matrix-vector multiplication. Graphs & hypergraphs. (Martin)
July 11th (final class)
Multithreaded BLAS vs. algorithms by blocks.