Georgia Institute of Technology College of Sciences

We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process.We use these new algorithms to derive the first nearly linear time algorithms for solving systems of equations in connection Laplacians, a generalization of Laplacian matrices that arise in many problems inimage and signal processing.We also prove that every connection Laplacian has a linear sized approximate inverse. This is an LU factorization with a linear number of nonzero entries that is a strong approximation of the originalmatrix. Using such a factorization one can solve systems of equations in a connection Laplacian in linear time. Such a factorization was unknown even for ordinary graph Laplacians.Joint work with Rasmus Kyng, Yin Tat Lee, Sushant Sachdeva, and Daniel Spielman. Manuscript at http://arxiv.org/abs/1512.01892.

A significant achievement of modern probability theory is the development of sharp connections between the boundedness of random processes and the geometry of the underlying index set. In particular, the generic chaining method of Talagrand provides in principle a sharp understanding of the suprema of Gaussian processes. The multiscale geometric structure that arises in this method is however notoriously difficult to control in any given situation. In this talk, I will exhibit a surprisingly simple but very general geometric construction, inspired by real interpolation of Banach spaces, that is readily amenable to explicit computations and that explains the behavior of Gaussian processes in various interesting situations where classical entropy methods are known to fail. (No prior knowledge of this topic will be assumed in the talk.)

Tropicalization involves passing to an ordered group M, usually taken to be (R, +) or (Q, +), and viewed as a semifield. Although there is a rich theory arising from this viewpoint, idempotent semirings possess a restricted algebraic structure theory, and also do not reflect important valuation-theoretic properties, thereby forcing researchers to rely often on combinatoric techniques. Our research in tropical algebra has focused on coping with the fact that the max-plus’ algebra lacks negation, which is used throughout the classical structure theory of modules. At the outset one is confronted with the obstacle that different cosets need not be disjoint, which plays havoc with the traditional structure theory. Building on an idea of Gaubert and his group (including work of Akian and Guterman), we introduce a general way of artificially providing negation, in a manner similar to the construction of Z from N but with one crucial difference necessitated by the fact that the max-plus algebra is not additively cancelative! This leads to the possibility of defining many auxiliary tropical structures, such as Lie algebras and exterior algebras, and also providing a key ingredient for a module theory that could enable one to use standard tools such as homology.

Solving numerically kinetic equations requires high computing power and storage capacity, which compels us to derive more tractable, dimensionally reduced models. Here we investigate fluid models derived from kinetic equations, typically the Vlasov equation. These models have a lower numerical cost and are usually more tangible than their kinetic counterpart as they describe the time evolution of quantities such as the density ρ, the fluid velocity u, the pressure p, etc. The reduction procedure naturally leads to the need for a closure of the resulting fluid equations, which can be based on various assumptions. We present here a strategy for building fluid models from kinetic equations while preserving their Hamiltonian structure. Joint work with M. Perin and E. Tassi (CNRS/Aix-Marseille University) and P.J. Morrison (University of Texas at Austin).