Schedule

The course consists of 5 half-day sessions spread across 2 weeks with a total lecture time of 15 hours. Each session consists of two lectures with a duration of 1.5 hours.

What follows next is a brief synopsis of the topics that will be covered. Note that the outline below is only tentative and is therefore subject to change.

Session 1

Date: 09:00-12:30, March 2, 2022
Location: Huis Bethlehem, Aula Wolfspoort, Schapenstraat 34, 3000 Leuven
Lectures:

1. Introduction and motivation for fast structured linear algebra (Shiv)
   • Basic notation and complexity of basic linear algebra operations
   • An enlightening example: divide & conquer and Strassen’s algorithm
   • Implications and limitations of Strassen’s algorithm
   • Iterative methods vs. direct methods
2. Fast structured linear algebra: two important classical examples (Shiv)
   • Example 1 - the DFT matrix and Cooley-Tuckey’s FFT algorithm
   • Example 2 - sparse matrices

Session 2

Date: 09:00-12:30, March 4, 2022
Location: Huis Bethlehem, Aula Wolfspoort, Schapenstraat 34, 3000 Leuven
Lectures:

1. Toeplitz, Hankel, circulant, and DFT matrices (Nithin)
   • Fast multplication with circulant matrices using Cooley-Tuckey’s idea
   • Fast matrix-vector multiply for Toeplitz and Hankel matrices
   • Extending the FFT algorithm to perform any-sized DFT
   • Applications: fast polynomial arithmetic
   • Limitations of FFT: inversion of Toeplitz or Hankel matrices
2. Introduction to displacement rank theory (Shiv)
   • Definition of low-displacement-rank (LDR) matrices
   • Important examples of LDR matrices
   • Intermezzo: solving the Sylvester equations AX + XB = C
   • Link between Sylvester equations and Gauss elimination on LDR matrices

Session 3

Date: 13:30-17:00, March 7, 2022
Location: Huis Bethlehem, Aula Wolfspoort, Schapenstraat 34, 3000 Leuven
Lectures:

1. Displacement rank theory and the Schur algorithm (Shiv)
   • Description of the Schur algorithm
   • An important case study: the Cauchy matrix
   • (Fast) conversion of Toeplitz, Hankel, and Vandermonde matrices to Cauchy matrices
   • Stability concerns and implementation
   • When does displacement rank theory lead to fast algorithms?
2. Sequentially semi-separable matrices - I (Shiv)
   • A motivating example: banded matrices and their inverses
   • Off-diagonal low rank and its algebraic properties
   • More examples of matrices with low off-diagonal rank structure
   • A straightforward fast matrix-vector multiply exploiting low rank
   • Exploiting additional structure: the algebraic relationship between overlapping low-rank blocks
   • The sequentially semi-separable (SSS) representation

Session 4

Date: 13:30-17:00, March 9, 2022
Location: Huis Bethlehem, Aula Wolfspoort, Schapenstraat 34, 3000 Leuven
Lectures:

1. Sequentially semi-separable matrices - II (Shiv)
   • Construction of SSS matrices
   • A fast matrix-vector multiply for SSS matrices
   • Algebra on SSS matrices: addition and multiplication
   • Links to systems theory
2. Sequentially semi-separable matrices - III (Shiv)
   • Fast LU factorization of SSS matrices
   • A fast SSS solver through sparse embedding
   • A fast Toeplitz solver using SSS matrices: the Cauchy connection

Session 5

Date: 09:00-12:30, March 11, 2022
Location: Huis Bethlehem, Aula Wolfspoort, Schapenstraat 34, 3000 Leuven
Lectures:

1. Hierachically semi-separable matrices - I (Shiv)
   • A motivating example: a one-dimensional electromagnetic problem
   • Well-separability and the Fast Multipole Method (FMM) matrix partitioning
   • Advantages of FMM-like structures in higher-dimensional settings
   • Inverse problems: the need for algebraic closure under inversion
   • Hierachically semi-separable (HSS) matrices and their algebraic properties
2. Hierachically semi-separable matrices - II (Shiv)
   • A fast matrix-vector multiply for HSS matrices
   • A fast HSS solver through sparse embedding
   • Summary: key take-aways, open questions, and unadressed topics