Georgia Institute of Technology College of Sciences

We show that in many instances, at the heart of a problem in numerical computation sits a special 3-tensor, the structure tensor of the problem that uniquely determines its underlying algebraic structure. In matrix computations, a decomposition of the structure tensor into rank-1 terms gives an explicit algorithm for solving the problem, its tensor rank gives the speed of the fastest possible algorithm, and its nuclear norm gives the numerical stability of the stablest algorithm. We will determine the fastest algorithms for the basic operation underlying Krylov subspace methods --- the structured matrix-vector products for sparse, banded, triangular, symmetric, circulant, Toeplitz, Hankel, Toeplitz-plus-Hankel, BTTB matrices --- by analyzing their structure tensors. Our method is a vast generalization of the Cohn--Umans method, allowing for arbitrary bilinear operations in place of matrix-matrix product, and arbitrary algebras in place of group algebras. This talk contains joint work with Ke Ye and joint work Shmuel Friedland.

Two-photon photoacoustic tomography (TP-PAT) is a non-invasive optical molecular imaging modality that aims at inferring two-photon absorption property of heterogeneous media from photoacoustic measurements. In this work, we analyze an inverse problem in quantitative TP-PAT where we intend to reconstruct optical coefficients in a semilinear elliptic PDE, the mathematical model for the propagation of near infra-red photons in tissue-like optical media, from the internal absorbed energy data. We derive uniqueness and stability results on the reconstructions of single and multiple coefficients, and perform numerical simulations based on synthetic data to validate the theoretical analysis.

For a compact subset $A$ of $R^n$ , let $A(k)$ be the Minkowski sum of $k$ copies of $A$, scaled by $1/k$. It is well known that $A(k)$ approaches the convex hull of $A$ in Hausdorff distance as $k$ goes to infinity. A few years ago, Bobkov, Madiman and Wang conjectured that the volume of $A(k)$ is non-decreasing in $k$, or in other words, that when the volume deficit between the convex hull of $A$ and $A(k)$ goes to $0$, it actually does so monotonically. While this conjecture holds true in dimension $1$, we show that it fails in dimension $12$ or greater. Then we consider whether one can have monotonicity of convergence of $A(k)$ when its non-convexity is measured in alternate ways. Our main positive result is that Schneider’s index of non-convexity of $A(k)$ converges monotonically to $0$ as $k$ increases; even the convergence does not seem to have been known before. We also obtain some results for the Hausdorff distance to the convex hull, along the way clarifying various properties of these notions of non-convexity that may be of independent interest.Joint work with Mokshay Madiman, Matthieu Fradelizi and Arnaud Marsiglietti.

The talk is meant to be a gentle introduction to a part of combinatorial topology which studies randomly generated objects. It is a rapidly developing field which combines elements of topology, geometry, and probability with plethora of interesting ideas, results and problems which have their roots in combinatorics and linear algebra.