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 dominates runtime and energy consumption, so avoiding it can greatly improve 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, revised version; original version and 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:*Proceedings of PPAM 2013*, Springer LNCS, to appear.)

(previous tech. report, May 3, 2013)*Avoiding communication in nonsymmetric Lanczos-based Krylov methods*, with E. Carson and J. Demmel

(paper: SIAM J. Sci. Comput. 35(5), S42-S61; MATLAB codes.)*Improving the stability of communication-avoiding Krylov subspace methods*, with E. Carson and J. Demmel

(talk: SIAM ALA12, Jun. 18, 2012, abstract)*Avoiding communication with hierarchical matrices*, with E. Carson and J. Demmel

(talk: 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

(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 successive band reduction*, with G. Ballard and J. Demmel

(paper: EECS dept. tech. report, Jul. 11, 2013)*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 successive band reduction*, with G. Ballard and J. Demmel

(paper:*Proc. ACM PPoPP12*, paper, free version)

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

- 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