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.
"Communication-avoiding algorithms for linear algebra and beyond",
BASCD12, Dec. 12, 2012.
(slides)
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:
An efficient deflation technique for the communication-avoiding conjugate gradient method,
E. Carson,
N. Knight, and
J. Demmel.
Electronic Transactions on Numerical Analysis 23 (2014), pp.125-141.
(paper)
"Avoiding synchronization in geometric multigrid",
PP14, Feb. 19, 2014.
(slides)
"s-step Krylov subspace methods as bottom solvers for geometric multigrid",
IPDPS14, May 22, 2014.
(slides)
"Avoiding communication in bottom solvers for geometric multigrid methods",
PMAA14, Jul. 2, 2014.
(slides)
Exploiting data sparsity in parallel matrix powers computations,
N. Knight,
E. Carson, and
J. Demmel.
Springer LNCS 8384 (2014), pp.15-25.
(paper)
Associated talks:
"Exploiting low-rank structure in computing matrix powers with applications to preconditioning",
PP12, Feb. 15, 2012.
(slides)
"Avoiding communication with hierarchical matrices", ALA12, Jun. 18, 2012.
(slides)
"Exploiting data sparsity in parallel matrix powers computations",
PPAM13, Sep. 11, 2013.
(slides)
Avoiding communication in nonsymmetric Lanczos-based Krylov subspace methods,
E. Carson,
N. Knight, and
J. Demmel.
SIAM J. Sci. Comput. 35:5 (2013), pp.S42-S61.
(paper;
MATLAB codes)
Talks:
"Improving the stability of communication-avoiding Krylov subspace methods",
E. Carson,
N. Knight, and
J. Demmel.
ALA12, Jun. 18, 2012.
(abstract)
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:
Avoiding communication in successive band reduction,
G. Ballard,
J. Demmel, and
N. Knight.
ACM Trans. Par. Comput. 1:2 (2015), pp.11:1-11:37.
(paper )
Triangular matrix inversion: a survey of sequential approaches,
N. Knight.
MATH 221 class project, Dec. 9 2009.
(paper,
poster)
Algorithmic-based fault tolerance for matrix multiplication on Amazon EC2,
G. Ballard,
E. Carson, and
N. Knight.
COMPSCI 262A class project, Dec. 21 2009.
(paper,
poster)