FoCM 2014 conference
Plenary talks
December 11, 9:30 ~ 10:25
On subset sums
Endre Szemeredi
Hungarian Academy of Science and Rutgers University , Hungary and USA - szemered@cs.rutgers.edu
Let $A \subset [1;N]$ be a set of integers. We denote by $S_A$ the collection of partial sums of $A$,
$$S_A =\left\{ \sum_{x\in B} x: B\subset A\right\}.$$
For a positive integer $l \le A$ we denote by $l^*A$ the collection of partial sums of $l$ elements of $A$,
$$l^*A =\left\{ \sum_{x\in B} x: B\subset A, |B|=l\right\}.$$
We will discuss the structure of $l^*A$ and give a tight bound of the size of $A$ not containing an $N$ element arithmetic progression.
Some of the results are joint with Van Vu, the others are joint work with Simao Herdade.
View abstract PDF | View talk slides
December 11, 11:00 ~ 11:55
Some Problems For This Century
Michael Shub
City University of New York, USA - shub.michael@gmail.com
In 1998 Steve Smale published a list of 18 problems for the next century. Four of them arose in our joint work, one with Lenore Blum. I will speak about progress (or lack of it) on some of these problems. In particular, Problem 17 on finding roots of polynomial equations will be included with some recent results about the eigenvalue, eigenvector problem. These problems involve finding well conditioned polynomial systems with respect to roots or matrices with respect to eigenvalues, eigenvectors. For one homogeneous polynomial in two variables the problem is related to Problem 7 on the distribution of points on the 2-sphere.
Time permitting, I will speak about some ideas related to Problem 4 on integer zeros of a polynomial.
View abstract PDF | View talk slides
December 12, 9:00 ~ 9:55
The L-functions and modular forms database project
John Cremona
University of Warwick, UK - j.e.cremona@warwick.ac.uk
The simplest and most famous L-function is the Riemann Zeta function. L-functions are ubiquitous in number theory, and have applications to mathematical physics and cryptography. Two of the seven Clay Mathematics Million Dollar Millennium Problems deal with their properties: the Riemann Hypothesis and the Birch and Swinnerton-Dyer Conjecture. They arise from and encode information about a number of mathematical objects, and also provide links between them: for example, Wiles' celebrated proof of Fermat's Last Theorem centred on proving that L-functions associated with certain elliptic curves were also associated with other objects called modular forms.
At least a dozen different mathematical objects are connected in various ways to L-functions. The study of those objects is highly specialized, and most mathematicians have only a vague idea of the objects outside their specialty and how everything is related. Helping mathematicians to understand these connections was the motivation for the L-functions and Modular Forms Database (LMFDB) project, which started at AIM in 2007 and has been supported by major grants from the NSF and (currently) the UK EPSRC. Its mission is to chart the landscape of L-functions and modular forms in a systematic and concrete fashion. This involves developing their theory, creating and improving algorithms for computing and classifying them, and hence discovering new properties of these functions, and testing fundamental conjectures.
In the lecture I will explain and demonstrate how we organise our large collection of data and display it, together with the interrelations between linked objects, through our website [www.lmfdb.org]. I will also show how this has been built via a world-wide collaborative open source project which we hope may become a model for others.
View abstract PDF | View talk slides
December 12, 11:00 ~ 11:55
Multipliers and contraints for spline-based methods
Annalisa Buffa
Istituto di Matematica e Tecnologie Informatiche , ITALY - annalisa.buffa@imati.cnr.it
Lagrange multipliers are used to impose constraints to the solution of a partial differential equation in a variational way. Relevant examples are the continuity across interfaces, or conservation of mass and volumes. It is well known that the resulting system represents a saddle point problem and its discretization requires special care.
Indeed, the choice of discretization spaces for multipliers depend upon the discretization of the primal variables and it is key to stability. I will discuss the choices that are possible when the primal variables are described by splines or NURBS in various contexts. I will introduce mortaring techniques to impose continuity across non-matching spline surfaces and their applications to contact mechanics, as well as the numerical treatment of (quasi-)incompressibility and its application to large deformation problems.
Joint work with Pablo Antolín (University of Pavia, Italy), E. Brivadis (IUSS, Pavia, Italy) and Giancarlo Sangalli (University of Pavia, Italy).
View abstract PDF | View talk slides
December 13, 9:00 ~ 9:55
Pursuit of Low-dimensional Structures in High-dimensional Data
Yi Ma
ShanghaiTech University, P. R. China - mayi@shanghaitech.edu.cn
In this talk, we will discuss a new class of models and techniques that can effectively model and extract rich low-dimensional structures in high-dimensional data such as images and videos, despite nonlinear transformation, gross corruption, or severely compressed measurements. This work leverages recent advancements in convex optimization for recovering low-rank or sparse signals that provide both strong theoretical guarantees and efficient and scalable algorithms for solving such high-dimensional combinatorial problems. These results and tools actually generalize to a large family of low-complexity structures whose associated regularizers are decomposable. We illustrate how these new mathematical models and tools could bring disruptive changes to solutions to many challenging tasks in computer vision, image processing, and pattern recognition. We will also illustrate some emerging applications of these tools to other data types such as web documents, image tags, microarray data, audio/music analysis, and graphical models.
Joint work with John Wright (Columbia University), Emmanuel Candes (Stanford University), Zhouchen Lin (Peking University) and Yasuyuki Matsushita (Microsoft Research Asia).
View abstract PDF | View talk slides
December 13, 11:00 ~ 11:55
Heating the sphere
Carlos Beltrán
Universidad de Cantabria, Spain - beltranc@unican.es
Where would you allocate $N$ sources of heat in the 2-dimensional sphere in order to maximize the steady state average temperature, assuming a constant cooling rate everywhere?
In this talk I will describe a theoretical solution to this facility location problem, relating it to other classical questions in potential theory, stability of polynomial zeros, eigenvalue computations and numerical integration. Novel results about some of these classical problems will be presented as a consequence of the analysis.
Joint work with : Different coauthors in several parts of the talk will be credited in the slides.
View abstract PDF | View talk slides
December 15, 9:30 ~ 10:25
The joy and pain of skew symmetry
Arieh Iserles
University of Cambridge, United Kingdom - ai@damtp.cam.ac.uk
Skew symmetry is good for you! More specifically, once a derivative is discretised with a skew-symmetric matrix, a numerical PDE scheme displays a range of favourable features: it is stable and various structural features of the original equation are preserved.
It is easy to design skew-symmetric differentiation matrices in tandem with periodic boundary conditions, e.g. using spectral collocation, and the first part of the talk will be devoted to a detailed study of the discretisation of the semiclassical Schrödinger equation using asymptotic splittings. Our main tools are a free Lie algebra of operators, palindromic Zassenhaus splitting and the symmetric BCH formula.
In the second part of the talk we consider Dirichlet boundary conditions, and this is the instant the pain kicks in. Using finite differences on a uniform grid, the highest order of a skew-symmetric differentiation matrix is just two! We will derive detailed necessary conditions for a non-uniform grid so that a skew-symmetric differentiation matrix of given order exists and prove that they can be always realised by a banded matrix. We will also discuss the state of the art in the construction and properties of such matrices.
View abstract PDF | View talk slides
December 15, 11:00 ~ 11:55
Stochastic Asynchronous Parallel Methods in Optimization
Stephen Wright
University of Wisconsin-Madison, USA - swright@cs.wisc.edu
The ubiquity of multicore computer architectures and clusters and the advent of new applications of optimization in machine learning, data analysis and other areas has prompted a reevaluation of elementary optimization methods that had long been out of fashion. Stochastic synchronous parallel variants of such methods as stochastic gradient, coordinate descent, and successive projections have been a particular focus of interest. We survey such methods here, presenting computational results for several of them. We then focus on two such methods - coordinate descent for convex optimization and the Kaczmarz method for linear systems - and introduce a model of multicore computation that is both close to reality and amenable to analysis of convergence behavior. We show in particular that there is a threshold number of cores below which near-linear speedup of the algorithm (as a function of the number of cores) can be expected.
Joint work with Ji Liu (University of Rochester).
View abstract PDF | View talk slides
December 16, 9:00 ~ 9:55
Architectural Geometry
Helmut Pottmann
King Abdullah University of Science and Technology, Saudi Arabia - helmut.pottmann@kaust.edu.sa
Free forms constitute one of the major trends within contemporary architecture. While the digital design of freeform geometry with current modeling tools is well understood, the actual fabrication on the architectural scale is a big challenge: one has to decompose the skins into manufacturable panels, provide appropriate support structures, meet structural constraints and last, but not least make sure that the cost does not become excessive. These practical requirements form a rich source of research topics in geometry and geometric computing. The talk will provide an overview of recent progress in the emerging field of Architectural Geometry, elaborate on important relations to contemporary research in Discrete Differential Geometry and Geometric Optimization, and illustrate the transfer of mathematical research into the architectural practice at hand of selected projects.
View abstract PDF | View talk slides
December 16, 11:00 ~ 11:55
Liberating the Dimension - Quasi Monte Carlo Methods for High Dimensional Integration
Frances Kuo
University of New South Wales, Australia - f.kuo@unsw.edu.au
High dimensional problems are coming to play an ever more important role in applications, including, for example, option pricing problems in mathematical finance, maximum likelihood problems in statistics, and porous flow problems in computational physics and uncertainty quantification. High dimensional problems pose immense challenges for practical computation, because of a nearly inevitable tendency for the cost of computation to increase exponentially with dimension. Effective and efficient methods that do not suffer from this "curse of dimensionality" are in great demand, especially since some practical problems are in fact infinite dimensional.
In this talk I will start with an introduction to "quasi-Monte Carlo methods", focusing on the theory and construction of "lattice rules" (order one) and "interlaced polynomial lattice rules" (higher order) developed in the past decade. Then I will showcase our very latest work on how this modern theory can be "tuned" for a given application. The motivating example will involve an elliptic PDE with a random coefficient, which is based on a simplified porous flow problem where the permeability is modeled as a random field.
View abstract PDF | View talk slides
December 17, 9:00 ~ 9:55
On the characterization of approximation spaces in Nonlinear Approximation
Pencho Petrushev
University of South Carolina, USA - pencho@math.sc.edu
An overview of old and new results in Nonlinear Approximation Theory will be presented and several open problems will be discussed. The emphasis will be placed on nonlinear $n$-term approximation from localized frames in various settings such as on the sphere, ball, box and simplex as well as on Lie groups and Riemannian manifolds. Nonlinear approximation from multivariate splines will also be considered. This talk will focus on the characterization of the rates of nonlinear approximation of interest and the related smoothness spaces.
View abstract PDF | View talk slides
December 17, 11:00 ~ 11:55
Differential Groups and the Gamma Function
Michael F. Singer
North Carolina State University, USA - singer@math.ncsu.edu
In 1887, Hoelder proved that the Gamma Function, defined by the difference equation y(x+1) = x y(x), satisfies no nonzero polynomial differential equation with complex coefficients. In the last several years Galois theories have been developed that reprove this result and allow one to characterize when functions satisfying certain linear differential or difference equations also satisfy auxiliary difference or differential equations. These Galois theories allow one to reduce such kinds of questions to questions concerning linear differential or difference groups, that is groups of matrices whose entries are functions satisfying a fixed set of differential or difference equations. I will give an introduction to the theory of these groups and the related Galois theories and survey recent results applying these theories to questions of functional transcendence.
View abstract PDF | View talk slides
December 18, 9:30 ~ 10:25
Models of tumor growth and therapy
Benoit Perthame
Laboratoire J.-L. Lions, Universite Pierre et Marie Curie (Paris 6), France - benoit.perthame@upmc.fr
Models of tumor growth are now commonly used to predict the evolution of cancers, based on images for instance. These models serve to predict the evolution of the disease in medical treatments, to understand the biological effects that permit tumor growth and decide of the optimal therapy. A more recent subject is to explain emergence of resistance to drug and its implication in therapeutic failures.
These models contain several levels of complexity, both in terms of the biological and mechanical effects, and therefore in their mathematical description. The number of scales, from molecules to the organ and entire body, explains partly the complexity of the problem.
In this talk I shall give a general presentation of the field and focus on two aspects. I shall firstly present a multiscale approach to mechanical models of tumor growth and secondly, models of resistance to therapy and treatment optimization.
The part on Hele-Shaw is a collaboration with F.Quiros and J.-L.Vazquez (Universidad Autonoma Madrid), M.Tang (SJTU) and N.Vauchelet (LJLL). The part on adaptation and resistance is a collaboration with O.Diekmann, P.-E.Jabin, S.Mischler, A.Escargueil, J.Clairambault, T.Lorenzi, A.Lorz, G.Barles, S.Mirrahimi, P.E.Souganidis, V.Calvez.
View abstract PDF | View talk slides
December 18, 11:00 ~ 11:55
On Adaptive Multilevel Monte Carlo and Multi-Index Monte Carlo
Raul Tempone
King Abdullah University of Science and Technology, Saudi Arabia - raul.tempone@kaust.edu.sa
We provide a quick glance into recently developed Adaptive Multilevel Monte Carlo (MLMC) Methods for the following widely applied mathematical models: (i) Itô Stochastic Differential Equations, (ii) Stochastic Reaction Networks modeled by Pure Jump Markov Processes and (iii) Partial Differential Equations with random inputs. In this context, the notion of adaptivity includes several aspects such as mesh refinements based on either a priori or a posteriori error estimates, the local choice of different time stepping methods and the selection of the total number of levels and the number of samples at different levels. Our Adaptive MLMC estimator is based on a hierarchy of adaptively refined, non-uniform time discretizations, and, as such, it may be considered a generalization of the uniform discretization MLMC method introduced independently by M. Giles and S. Heinrich. In particular, we show that under some assumptions our adaptive MLMC algorithms are asymptotically accurate and have the correct complexity with an improved control of the complexity constant factor in the asymptotic analysis. Moreover, we show the asymptotic normality of the statistical error in the MLMC estimator, justifying in this way our error estimate that allows prescribing both the required accuracy and confidence level in the final result.
We will show several examples, including some dynamics with singularities and/or non-smooth observables, to illustrate the above results and the corresponding computational savings.
Finally, we will briefly describe the Multi Index Monte Carlo method, presenting new and improved complexity results which are natural generalizations of Giles's MLMC analysis.
Joint work with Nathaniel Collier (Oak Ridge National Laboratory, USA), Abdul Lateef Haji-Ali (King Abdullah University of Science and Technology, Saudi Arabia), Hákon Hoel (University of Oslo, Norway), Alvaro Moraes (King Abdullah University of Science and Technology, Saudi Arabia), Fabio Nobile (Ecole Politechnique Fédérale Lausanne, Switzerland), Erik von Schwerin (Royal Institute of Technology, Sweden), Anders Szepessy (Royal Institute of Technology, Sweden) and Pedro Vilanova (King Abdullah University of Science and Technology, Saudi Arabia).
View abstract PDF | View talk slides
December 19, 9:00 ~ 9:55
AFEM for the Laplace-Beltrami Operator: Convergence Rates
Ricardo H. Nochetto
University of Maryland, USA - rhn@math.umd.edu
Elliptic partial differential equations (PDEs) on surfaces are ubiquitous in science and engineering. We present several geometric flows governed by the Laplace-Beltrami operator. We design a new adaptive finite element method (AFEM) with arbitrary polynomial degree for such an operator on parametric surfaces, which are globally Lipschitz and piecewise in a suitable Besov class: the partitions thus match possible kinks. The idea is to have the surface sufficiently well resolved in $W^1_\infty$ relative to the current resolution of the PDE in $H^1$. This gives rise to a conditional contraction property of the PDE module and yields optimal cardinality of AFEM. Moreover, we relate the approximation classes to Besov classes.
If the meshes do not match the kinks, or they are simply unknown beforehand, we end up with elliptic PDEs with discontinuous coefficients within elements. In contrast to the usual perturbation theory, we develop a new approach based on distortion of the coefficients in $L_q$ with $q<\infty$. We then use this new distortion theory to formulate a new AFEM for such discontinuity problems, show optimality of AFEM in the sense of distortion versus number of computations, and report insightful numerical results supporting our analysis.
Joint work with A. Bonito (Texas A&M University, USA), M. Cascon (Universidad de Salamanca, Spain), R. DeVore (Texas A&M University, USA), K. Mekchay (Chulalongkorn University, Thailand) and P. Morin (Universidad Nacional del Litoral, Argentina).
View abstract PDF | View talk slides
December 19, 11:00 ~ 11:55
Solving high-dimensional PDEs by tensor product approximation
Reinhold Schneider
TU Berlin , Germany - schneidr@math.tu-berlin.de
Hierarchical Tucker tensor format introduced by Hackbusch et al. including Tensor Trains (TT) (Tyrtyshnikov) have been introduced in 2009. These representations offer stable and robust approximation of high order tensors and multi-variate functions by a low order cost . For many high dimensional problems, including many body quantum mechanics, uncertainty quantification etc., this approach has great potential to circumvent from the {\em curse of dimensionality}. In case $\mathcal{V} = \bigotimes_{i=1}^d \mathcal{V}_i $ the complexity remains proportional to $d$ and polynomial in some multilinear ranks. The approximation properties w.r.t. to these ranks are depending on bilinear approximation rates and corresponding trace class norms. Despite fundamental problems in multilinear approximation, under certain conditions optimal convergence rates could be shown. The present formats are equivalent to tree tensor networks states and matrix product states (MPS) introduced for the treatment of quantum spin systems. For numerical computations, we cast the PDEs into optimization problems constraint by restricting to set of d tensors of bounded multilinear ranks $\mathbf{r} $. The underlying admissible set is no longer convex, but it is an algebraic variety. We consider optimization on Riemannian manifold and corresponding gradient schemes. Numerical examples include electronic Schrödinger equations, uncertainty quantification and molecular dynamics.
Joint work with A. Uschmajew (U Bonn).
View abstract PDF | View talk slides
December 20, 9:00 ~ 9:55
Zeros (of some polynomials) prefer curves
Andrei Martínez-Finkelshtein
University of Almería, Spain - andrei@ual.es
Polynomials satisfying non-Hermitian orthogonality relations appear naturally in approximation theory (as denominators of Padé and Hermite-Padé approximants), random matrix theory, differential equations and special functions, just to mention a few branches of analysis. They are defined by orthogonality relations on the complex plane in which we can freely deform the paths of integration. It is natural to ask where the zeros of these polynomials choose to go. Computation shows that they like to align themselves along certain curves on the plane. What are these curves? In some cases we can answer this question, at least asymptotically. But the answer connects fascinating mathematical objects, such as extremal problems in electrostatics, Riemann surfaces, trajectories of quadratic differentials, algebraic functions; this list is not complete.
This is a brief survey of some ideas related to this problem, starting from the classics, with an emphasis on the breakthrough developments in the 1980-ies, and finishing with some recent results and open problems.
Joint work with E. A. Rakhmanov (University of South Florida, USA).
View abstract PDF | View talk slides
December 20, 11:00 ~ 11:55
Combinatorial Algebraic Geometry
David Cox
Amherst College, USA - dacox@amherst.edu
This talk will survey aspects of the emerging field of combinatorial algebraic geometry. The topics covered will include polytopes involved in quantum computing, formulas for a classical secant variety, likelihood functions, and the combinatorics of a classical moduli space as revealed by tropical geometry. I will also mention some of the computational issues involved.