Research

Thesis research

My thesis project involves developing new algorithms in sparse and dense linear algebra, with the goal of avoiding communication. Communication includes moving data between processors ("parallel"), and moving data between levels of the memory hierarchy ("sequential"). For several decades, communication performance has gotten exponentially worse relative to arithmetic performance. Current hardware trends, such as multicore and off-chip compute accelerators, only exacerbate existing limitations in memory and bus bandwidth. In fact, we cannot expect new developments in hardware to solve the problem completely, because

Flops are cheap, bandwidth is money, latency is physics.
Floating-point (and integer) computational performance scales with the number of transistors on a chip. Bandwidth scales with cost of hardware (number of wires, pipes, banks, disks, ...) and energy consumption. Latency is the hardest to improve, because it's often limited by physical laws (even the speed of light is computationally significant).

These hard facts call for new algorithms that work with the physical and economic laws of hardware. Rearranging algorithms to avoid communication can often improve performance, even if it requires redundant computation. I've applied this observation to iterative methods for sparse linear systems and eigenvalue problems, by rearranging the algorithms so that several steps of the method can be performed at the same time, for the same latency cost as a single step of the original algorithm. Performance tuning involves a subtle balance between latency, bandwidth, redundant computation, and numerical accuracy. I've also worked out new preconditioning techniques that may make our algorithms practically useful for a wide class of problems. On the dense side, I've helped develop and implement a new QR factorization that communicates asymptotically less than existing algorithms in LAPACK and ScaLAPACK, and have helped prove lower bounds on the amount of communication a QR factorization must perform.

Publications and talks

Publications

Conference and seminar talks

General interests

I'm interested in numerical linear algebra, performance tuning, programming languages (especially parallel and embedded languages), and software engineering issues for scientific computing -- especially when it involves using ideas from higher-level programming languages. I have background in the numerical solution of ordinary and partial differential equations, as well as numerical optimization.

Mathematics knows no races or geographic boundaries; for mathematics, the cultural world is one country.
-- David Hilbert
Last updated 09 July 2009.