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

e-mail: | knight@cs |

office: | 593D Soda Hall (Par Lab) |

advisor: | James Demmel |

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, e.g.,

*Communciation lower bounds and optimal algorithms for numerical linear algebra*, with G. Ballard, E. Carson, J. Demmel, M. Hoemmen, and O. Schwartz.*Acta Numerica*23 (2014), pp.1-55. (paper)

**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:
*Tradeoffs between synchronization, communication, and work in parallel linear algebra computations*, with E. Solomonik, E. Carson, and J. Demmel, EECS dept. tech. report, Jan. 25, 2014. (paper)*Communication lower bounds and optimal algorithms for programs that references arrays — part I*, with M. Christ, J. Demmel, T. Scanlon, and K. Yelick. EECS dept. tech. report, May 14, 2013. (revised paper, fixing errata in the original paper)

- Talks:
*Communication lower bounds for programs with affine dependences*, with M. Christ, J. Demmel, T. Scanlon, and K. Yelick. SIAM PP14, Feb. 19, 2014. (slides)*Communication lower bounds for programs that access arrays*, with M. Christ, J. Demmel, T. Scanlon, and K. Yelick. 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. Stanford BASCD12, Dec. 12, 2012. (slides)

- 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:
*Exploiting data sparsity in parallel matrix powers computations*, with E. Carson and J. Demmel.*Springer LNCS*8384 (2014), pp.15-25. (paper)*Avoiding communication in nonsymmetric Lanczos-based Krylov methods*, with E. Carson 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*, with E. Carson and J. Demmel. SIAM ALA12, Jun. 18, 2012. (abstract)*Avoiding communication with hierarchical matrices*, with E. Carson and J. Demmel. SIAM ALA12, Jun. 18, 2012. (slides, abstract)*Exploiting low-rank structure in computing matrix powers with applications to preconditioning*, with E. Carson and J. Demmel. SIAM PP12, Feb. 15, 2012. (slides, abstract)*Hypergraph partitioning for computing matrix powers*, with E. Carson and J. Demmel. SIAM CSC11, May 20 2011. (slides, abstract)

- Papers:
**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*, with G. Ballard and J. Demmel. EECS dept. tech. report, Jul. 11, 2013. (paper)*Communication avoiding successive band reduction*, with G. Ballard and J. Demmel.*ACM Proc. PPoPP '12*(2012), pp.35-44. (paper, open-access version)

- Talks:
*Minimizing communication in large symmetric eigenproblems*, with G. Ballard, J. Demmel, and E. Solomonik. PMAA14, Jul. 2, 2014. (slides)*Avoiding communication in parallel bidiagonalization of band matrices*, with G. Ballard and J. Demmel. SIAM CSE13, Feb. 26, 2013. (slides (no movies), abstract)*Communication avoiding successive band reduction*, with G. Ballard and J. Demmel. ACM PPoPP12, Feb. 27, 2012. (slides (no movies), slides (with movies))*Avoiding communication for banded eigensolvers*, with G. Ballard and J. Demmel. SIAM PP12, Feb. 16, 2012. (slides, abstract)

- Papers:

(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)

- 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)

- CS70 - Discrete Mathematics and Probability Theory (Spring 2011) - Head GSI
- CS267 - Applications of Parallel Computers (Spring 2012) - GSI
- Outstanding Graduate Student Instructor Award