Nick Knight

PhD Candidate, EECS Dept.|University of California, Berkeley

e-mail:knight@cs
office:593D Soda Hall (Par Lab)
advisor:James Demmel

Research

My research interests include numerical algorithms and algorithmic complexity. In particular, I study algorithms that move less data (communicate less); communication often dominates runtime and energy consumption, so avoiding it can greatly improve performance. For a survey of some recent work, see (List of publications, via Google scholar)

Communication lower bounds (and optimal algorithms) for affine loop nests

It is possible to compute a lower bound on data movement for computer programs with affine dependence structures. Many algorithms, not just numerical ones, fit into this framework. The proof of the lower bound suggests how to reorganize an algorithm to attain its lower bound, so that it is communication-optimal.

Papers:

Avoiding communication in Krylov subspace methods

Krylov methods' performance is communication bound due to the sparse matrix-vector multiplication and orthogonalization operations in each iteration. By reformulating as an s-step method (fusing s iterations), we can decrease communication costs by a factor of s, in parallel and sequential.

Papers:

Talks:

Avoiding communication in bidiagonalization and tridiagonalization

Bidiagonalization (resp. tridiagonalization) is often the first step toward solving the singular value (resp. symmetric eigenvalue) problem. Conventional approaches attempt to minimize flops; large speedups are possible by reorganizing the algorithms to improve data reuse.

Papers:

Talks:

Older projects

Teaching

Affiliations

Present: Past: