Exploiting Cache Memories in Matrix Computations

	   Sivan Toledo, Tel-Aviv University, Israel

The talk will describe techniques for exploiting cache memories in
scientific computations. Exploiting caches is essential for achieving
high performance on almost all computers.

In the first part of the talk I will focus on techniques for
matrix-vector multiplication, an important computational kernel in
many iterative linear solvers, and on techniques for sparse-matrix
factorizations.  The techniques exploit caches by reordering the
matrices without increasing fill or work, by utilizing elimination
trees to schedule the computation, and by performing simple kinds of
memory accesses as efficiently as possible.

In the second part of the talk I will talk about exploiting caches in
dense matrix algorithms. I will briefly describe classical blocking
techniques. I will then explain their shortcomings and how recursive
algorithms can overcome these shortcomings. In particular, I will
describe a recursive algorithm for gaussian elimination with partial
pivoting and the notion of cache-oblivious algorithms.