Many large-scale scientific simulations face challenges that are combinatorial in nature. These include graph and hypergraph partitioning (e.g., for parallel sparse matrix-vector multiplication and for sparse matrix factorizations), graph coloring (used in automatic differentiation), matching (used in static pivoting), and more. Combinatorial Scientific Computing (CSC) is the study of these problems and of the algorithms that solve them.
The tutorial will provide a quick overview of CSC, but most of it will be devoted to three related problems within CSC that I have worked on. In each problem area, I will describe some easy-to-follow basic results, some results that I worked on, and some remaining challenges. The first problem that I will talk about is sparse matrix factorization. This is a classical problem in which the connections between the numerics and the combinatorial structures have been studied since the 1970s. I will explain the basics of sparse elimination and fill-reducing orderings, as well as topics of current interest: sparse symmetric indefinite factorizations, static pivoting techniques, and sparse singular-value decompositions.
The next part of the talk will focus on combinatorial preconditioners. I will describe the relationships between iterative solvers for sparse systems of equations and pairs of graphs, the algorithms that exploit these relationships, and applications of these techniques.
The last part of the talk will focus on recently-discovered uses of randomization in numerical linear algebra. This part of the talk will again cover some basic notions but will then move on to state-of-the-art results and recent solvers that my group has produced.