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
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.
Tradeoffs between synchronization, communication, and work in parallel linear algebra computations,
N. Knight, and
Proc. SPAA '14 (2014), pp.307-318.
"Communication-avoiding algorithms for linear algebra and beyond",
BASCD12, Dec. 12, 2012.
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.
An efficient deflation technique for the communication-avoiding conjugate gradient method,
N. Knight, and
Electronic Transactions on Numerical Analysis 23 (2014), pp.125-141.
( to appear)
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.
Avoiding communication in successive band reduction,
J. Demmel, and
ACM Transactions on Parallel Computing, to appear (accepted Jul. 21, 2014).
(previous tech. report Jul. 11, 2013)