Nick Knight
| e-mail: | knight@cs |
| office: | 593D Soda Hall (Par Lab) |
| advisor: | James Demmel |
Research
My research interests include numerical methods for linear algebra and differential equations. I study algorithms that move less data (communicate less); communication dominates runtime and energy consumption, so avoiding it can greatly improve an algorithm's performance.
- Communication lower bounds (and optimal algorithms) for affine array references
It is possible to compute a lower bound on data movement for computer programs with affine array references. Many algorithms, not just numerical ones, fit into this framework. The proof of the lower bound suggests how to reorganize the algorithm to attain its lower bound, so that it is communication-optimal.
- Communication lower bounds and optimal algorithms for programs that references arrays — part I, with
M. Christ,
J. Demmel,
T. Scanlon, and
K. Yelick
(paper: EECS dept. tech. report, May 14, 2013, errata)
- Communication lower bounds for programs that access arrays, with
M. Christ,
J. Demmel,
T. Scanlon, and
K. Yelick
(talk: Berkeley LAPACK Seminar, Apr. 24, 2013,
slides)
- Communication-avoiding algorithms for linear algebra and beyond, with
M. Christ,
J. Demmel,
T. Scanlon, and
K. Yelick
(talk: Stanford 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.
- Exploiting data sparsity in parallel matrix powers computations, with
E. Carson and
J. Demmel
(paper: EECS dept. tech. report, May 3, 2013)
- Avoiding communication in nonsymmetric Lanczos-based Krylov methods, with
E. Carson and
J. Demmel
(paper: SIAM J. Sci. Comput., to appear; MATLAB codes.)
(previous tech. report from Aug. 16, 2011)
- Improving the stability of communication-avoiding Krylov subspace methods, with E. Carson and
J. Demmel
(talk: SIAM ALA12, Jun. 18, 2012,
slides, abstract)
- Avoiding communication with hierarchical matrices, with E. Carson and J. Demmel
(talk: SIAM ALA12, Jun. 18, 2012,
abstract)
- Exploiting low-rank structure in computing matrix powers with applications to preconditioning, with E. Carson and J. Demmel
(talk: SIAM PP12, Feb. 15, 2012, slides, abstract)
- Hypergraph partitioning for computing matrix powers, with E. Carson and
J. Demmel
(talk: SIAM CSC11, May 20 2011, slides,
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.
- Avoiding communication in parallel bidiagonalization of band matrices, with G. Ballard and
J. Demmel
(talk: SIAM CSE13, Feb. 26, 2013, slides (no movies), abstract)
- Communication avoiding symmetric band reduction, with G. Ballard and
J. Demmel
(paper: Proc. ACM PPoPP12, paper, preprint)
(talk: ACM PPoPP12,
slides (no movies), slides (zip with movies), Feb. 27 2012)
- Avoiding communication for banded eigensolvers,
with G. Ballard and J. Demmel
(talk: SIAM PP12, Feb. 16, 2012, slides, abstract)
(List of publications, via Google scholar)
Older projects:
- Triangular matrix inversion: a survey of sequential approaches
(class project: MATH221, Dec. 9 2009,
paper,
poster)
- Algorithmic-based fault tolerance for matrix multiplication on Amazon EC2, with G. Ballard and
E. Carson
(class project: CS262A, Dec. 21 2009,
paper,
poster)
Affiliations:
- Berkeley Benchmarking and Optimization (Bebop)
- Parallel Computing Laboratory (Par Lab)
- Communication Avoiding and Communication Hiding at Extreme Scales (CACHE)
- Extreme-scale Algorithms and Software (EASI)
- Dynamic Exascale Global Address Space Programming Environments (DEGAS)
- Designated Emphasis in Computational Science and Engineering (CSE)
Teaching