Applied Math Colloquium

Abstract: The tropical semiring consists of the real numbers and infinity along with two binary operations: addition defined by the max or min operation and multiplication. Tropical algebra is the tropical analogue of linear algebra, working with matrices with entries on the extended real line. There are analogues of eigenvalues and singular values of matrices, and matrix factorizations in the tropical setting, and when combined with a valuation map these analogues offer `order of magnitude' approximations to eigenvalues and singular values, and factorizations of matrices in the usual algebra. What makes tropical algebra a useful tool for numerical linear algebra is that these tropical analogues are usually cheaper to compute than those in the conventional algebra. They can then be used in the design of preprocessing steps to improve the numerical behaviour of algorithms. In this talk I will review the contributions of tropical algebra to numerical linear algebra and discuss recent results on the selection of Hungarian scalings prior to solving linear systems and eigenvalue problems.

Abstract: In this talk, I will present some new results on controlling the Liouville (or continuity) equation for the probability density of the state of a smooth controlled dynamical system starting from a random initial state. This problem, first formulated and studied by Roger Brockett, makes contact with the theory of optimal transportation and with nonlinear controllability. I will discuss two settings: (1) controllable linear systems with finite-dimensional states and controls and (2) nonlinear controlled systems defined on smooth manifolds. For the latter, I will sketch the analysis of the complexity of implementing orientation-preserving diffeomorphisms by means of piecewise constant feedback controls. This estimate, which provides a quantitative version of a key result of Agrachev and Caponigro, can be used to assess the complexity of approximating smooth dynamical systems by means of continuous-time neural nets (so-called neural ODEs).

Abstract: Particle methods are a fundamental tool for computing flows in the space of probability measures, whether the flow describes the evolution of fluid in a porous medium, agents in a robotic swarm, or samples transported to a desired target distribution. As a counterpoint to classical stochastic particle methods, such as Langevin dynamics, in today’s talk, I will present recent progress on deterministic particle methods, including (1) a nonlocal approximation of dynamic optimal transport, with state and control constraints, and (2) a nonlocal approximation of general nonlinear diffusion equations.

Abstract: The main building block of large language models is matrix multiplication, which is often bottlenecked by the speed of loading these matrices from memory. A possible solution is to trade accuracy for speed by storing the matrices in low precision ("quantizing" them). In recent years a number of quantization algorithms with increasingly better performance were proposed (e.g., SmoothQuant, Brain compression, GPTQ, QuIP, QuIP#, QuaRot,SpinQuant). In this work, we prove an information theoretic lower bound on achievable accuracy of computing matrix product as a function of compression rate (number of bits per matrix entry). We also construct a quantizer (based on nested lattices) achieving this lower bound.

Based on a joint work with Or Ordentlich (HUJI), arXiv:2410.13780.