High Performance Linear Algebra

This course will cover topics in Linear Algebra, specifically concerning the way to implement them on modern computer architectures and clusters. The course will cover both the theoretical aspects underlying the routine we want to implement, both the the implementation aspects that are needed to achieve high performance; while specifying what do we actually mean by that.

Main list of the topics

This a tentativ list of the topics that will be covered during the course, we will discuss with the attending students the order and the depth of each topic depending on their interests and background.

• Vector and Matrix Products
  • Inner product
  • Outer product
  • Matrix-vector product
  • Matrix-matrix product
  • Row, column, and submatrix partitioning
• LU Factorization
  • ijk forms of Gaussian elimination
  • Row, column, and submatrix partitioning
  • Partial pivoting and alternatives
• Cholesky Factorization
  • ijk forms of Cholesky factorization
  • Memory access patterns
  • Data dependences
• Triangular, band and tridiagonal Systems
  • Row vs. column partitioning
  • Fan-in and fan-out algorithms
  • Wavefront algorithms
  • Cyclic algorithms
  • Cyclic reduction
• Sparse BLAS
  • Matrix-vector product
  • Matrix-matrix product
  • Matrix storage formats
• Distributed Dense BLAS
  • Data distribution
  • Handling of the parallel environment
  • Programming models
• How to write efficient threaded and GPU accelerated implementation of the different LA routines.

The final exam consists of the implementation and testing of a scalable algorithm for linear algebra, or the discussion and use within an application.

Schedule

The Preliminary meeting will be held on Wednesday, November 5th, 2025 at 4:00 PM/16:00 at the Aula Riunioni of the Mathematics Department.

• Monday 10, November 14.00-16.00 - Aula DM3. Lecture 1: Introduction and Overview
• Friday 14, November 9.00-11.00 - Aula DM3. Lecture 2: Performance Modeling and the Roofline Model .
• Monday 17, November 14.00-16.00 - Aula DM3. Lecture 3: Intra-node parallelism and starting with BLAS .

Slides and Materials

• Lecture notes: pay attention these are a work in progress, hence they will evolve and change during the course: avoid printing as much as possible.
• Introductory lecture: bureaucracy and some motivation
• Lecture 1: Introduction and Overview
• Lecture 2: Performance Modeling and the Roofline Model
• Lecture 3: Intra-node parallelism and starting with BLAS