Colloquia/Fall18
Mathematics Colloquium
All colloquia are on Fridays at 4:00 pm in Van Vleck B239, unless otherwise indicated.
Fall 2013
| date | speaker | title | host(s) | ||
|---|---|---|---|---|---|
| Sept 6 | Matt Baker (Georgia Institute of Technology) | Riemann-Roch for Graphs and Applications | Ellenberg | ||
| Sept 13 | Uri Andrews (University of Wisconsin) | A hop, skip, and a jump through the degrees of relative provability | |||
| Sept 20 | Valerio Toledano Laredo (Northeastern) | Flat connections and quantum groups | Gurevich | ||
| Wed, Sept 25, 2:30PM | Ayelet Lindenstrauss | Meyer | |||
| Wed, Sept 25 (LAA lecture) | Jim Demmel (Berkeley) | Communication Avoiding Algorithms for Linear Algebra and Beyond | Gurevich | ||
| Thurs, Sept 26 (LAA lecture, Joint with Applied Algebra Seminar) | Jim Demmel (Berkeley) | Implementing Communication Avoiding Algorithms | Gurevich | ||
| Sept 27 (LAA lecture) | Jim Demmel (Berkeley) | Communication Lower Bounds and Optimal Algorithms for Programs that Reference Arrays | Gurevich | ||
| Oct 4 | Frank Sottile (Texas A&M) | Caldararu | |||
| Oct 11 | Amie Wilkinson (Chicago) | WIMAW (Cladek) | |||
| Tues, Oct 15, 4PM (Distinguished Lecture) | Alexei Borodin (MIT) | Integrable probability I | Valko | ||
| Wed, Oct 16, 2:30PM (Distinguished Lecture) | Alexei Borodin (MIT) | Integrable probability II | Valko | ||
| No colloquium due to the distinguished lecture | |||||
| Oct 25 | Paul Garrett (Minnesota) | Gurevich | |||
| Nov 1 | Allison Lewko (Microsoft Research New England) | Stovall | |||
| Nov 8 | Tim Riley (Cornell) | Dymarz | |||
| Nov 15 and later | Reserved | Street |
Spring 2014
| date | speaker | title | host(s) |
|---|---|---|---|
| Jan 24 | |||
| Jan 31 | Urbashi Mitra (USC) | Gurevich | |
| Feb 7 | David Treumann (Boston College) | Street | |
| Feb 14 | |||
| Feb 21 | |||
| Feb 28 | |||
| March 7 | |||
| March 14 | |||
| Spring Break | No Colloquium | ||
| March 28 | Michael Lacey (GA Tech) | The Two Weight Inequality for the Hilbert Transform | Street |
| April 4 | Kate Jushchenko (Northwestern) | Dymarz | |
| April 11 | Risi Kondor (Chicago) | Gurevich | |
| April 18 (Wasow Lecture) | Christopher Sogge (Johns Hopkins) | A. Seeger | |
| April 25 | Charles Doran(University of Alberta) | Song | |
| May 2 | Lek-Heng Lim (Chicago) | Boston | |
| May 9 | Rachel Ward (UT Austin) | WIMAW |
Abstracts
Sep 6: Matt Baker (GA Tech)
Riemann-Roch for Graphs and Applications
We will begin by formulating the Riemann-Roch theorem for graphs due to the speaker and Norine. We will then describe some refinements and applications. Refinements include a Riemann-Roch theorem for tropical curves, proved by Gathmann-Kerber and Mikhalkin-Zharkov, and a Riemann-Roch theorem for metrized complexes of curves, proved by Amini and the speaker. Applications include a new proof of the Brill-Noether theorem in algebraic geometry (work of by Cools-Draisma-Payne-Robeva), a "volume-theoretic proof" of Kirchhoff's Matrix-Tree Theorem (work of An, Kuperberg, Shokrieh, and the speaker), and a new Chabauty-Coleman style bound for the number of rational points on an algebraic curve over the rationals (work of Katz and Zureick-Brown).
Sep 20: Valerio Toledano (North Eastern)
Flat connections and quantum groups
Quantum groups are natural deformations of the Lie algebra of nxn matrices, and more generally of semisimple Lie algebras. They first arose in the mid eighties in the study of solvable models in statistical mechanics.
I will explain how these algebraic objects can serve as natural receptacles for the (transcendental) monodromy of flat connections arising from representation theory.
These connections exist in rational, trigonometric and elliptic forms, and lead to quantum groups of increasing interest and complexity.
Sep 25: Jim Demmel (Berkeley)
Communication Avoiding Algorithms for Linear Algebra and Beyond
Algorithm have two costs: arithmetic and communication, i.e. moving data between levels of a memory hierarchy or processors over a network. Communication costs (measured in time or energy per operation) already greatly exceed arithmetic costs, and the gap is growing over time following technological trends. Thus our goal is to design algorithms that minimize communication. We present algorithms that attain provable lower bounds on communication, and show large speedups compared to their conventional counterparts. These algorithms are for direct and iterative linear algebra, for dense and sparse matrices, as well as direct n-body simulations. Several of these algorithms exhibit perfect strong scaling, in both time and energy: run time (resp. energy) for a fixed problem size drops proportionally to the number of processors p (resp. is independent of p). Finally, we describe extensions to algorithms involving arbitrary loop nests and array accesses, assuming only that array subscripts are affine functions of the loop indices.
Sep 26: Jim Demmel (Berkeley)
Implementing Communication Avoiding Algorithms
Designing algorithms that avoiding communication, attaining lower bounds if possible, is critical for algorithms to minimize runtime and energy on current and future architectures. These new algorithms can have new numerical stability properties, new ways to encode answers, and new data structures, not just depend on loop transformations (we need those too!). We will illustrate with a variety of examples including direct linear algebra (eg new ways to perform pivoting, new deterministic and randomized eigenvalue algorithms), iterative linear algebra (eg new ways to reorganize Krylov subspace methods) and direct n-body algorithms, on architectures ranging from multicore to distributed memory to heterogeneous. The theory describing communication avoiding algorithms can give us a large design space of possible implementations, so we use autotuning to find the fastest one automatically. Finally, on parallel architectures one can frequently not expect to get bitwise identical results from multiple runs, because of dynamic scheduling and floating point nonassociativity; this can be a problem for reasons from debugging to correctness. We discuss some techniques to get reproducible results at modest cost.
Sep 27: Jim Demmel (Berkeley)
Communication Lower Bounds and Optimal Algorithms for Programs that Reference Arrays
Our goal is to minimize communication, i.e. moving data, since it increasingly dominates the cost of arithmetic in algorithms. Motivated by this, attainable communication lower bounds have been established by many authors for a variety of algorithms including matrix computations.
The lower bound approach used initially by Irony, Tiskin and Toledo for O(n^3) matrix multiplication, and later by Ballard et al for many other linear algebra algorithms, depends on a geometric result by Loomis and Whitney: this result bounds the volume of a 3D set (representing multiply-adds done in the inner loop of the algorithm) using the product of the areas of certain 2D projections of this set (representing the matrix entries available locally, i.e., without communication).
Using a recent generalization of Loomis' and Whitney's result, we generalize this lower bound approach to a much larger class of algorithms, that may have arbitrary numbers of loops and arrays with arbitrary dimensions, as long as the index expressions are affine combinations of loop variables. In other words, the algorithm can do arbitrary operations on any number of variables like A(i1,i2,i2-2*i1,3-4*i3+7*i_4,…). Moreover, the result applies to recursive programs, irregular iteration spaces, sparse matrices, and other data structures as long as the computation can be logically mapped to loops and indexed data structure accesses.
We also discuss when optimal algorithms exist that attain the lower bounds; this leads to new asymptotically faster algorithms for several problems.
March 28: Michael Lacey (GA Tech)
The Two Weight Inequality for the Hilbert Transform
The individual two weight inequality for the Hilbert transform asks for a real variable characterization of those pairs of weights (u,v) for which the Hilbert transform H maps L^2(u) to L^2(v). This question arises naturally in different settings, most famously in work of Sarason. Answering in the positive a deep conjecture of Nazarov-Treil-Volberg, the mapping property of the Hilbert transform is characterized by a triple of conditions, the first being a two-weight Poisson A2 on the pair of weights, with a pair of so-called testing inequalities, uniform over all intervals. This is the first result of this type for a singular integral operator. (Joint work with Sawyer, C.-Y. Shen and Uriate-Tuero)
Past talks
Last year's schedule: Colloquia 2012-2013