2015 Abstracts

Rustum Choksi (McGill)

Self-assemby of shapes via generalized centroidal Voronoi tessellations

Self-assembly of shapes from spheres to non-smooth and possibly non-convex shapes, are pervasive throughout the sciences. These arrangements arise in biology for animal flocking and herding, in condensed matter physics with molecular and nano self assembly, and in control theory for coordinated motion problems. While idealizing these often non-convex objects as points or spheres aids in analysis, the effects of shape curvature and convexity are often dramatic, especially for short-range interactions. In this talk, we develop a general purpose model for arranging rigid shapes in Euclidean domains and on flat tori. The shapes are arranged optimally with respect to minimization of a geometric Voronoi-based cost function which generalizes the notion of a centroidal Voronoi tessellation from point sources to general rigid shapes. We present an efficient and fast algorithm for the minimization of this nonlocal, albeit finite-dimensional variational problem. The algorithm applies in any space dimension and can be used to generate self-assemblies of any collection of non convex, piecewise smooth shapes. We will also provide an approximate result for the minimizers of this cost function which supports the intuition that self-assembled shapes should be centered in and aligned with their Voronoi regions. This is joint work with Lisa Larsson (Credit-Suisse and Courant) and JC Nave (McGill).

Nils Bruin (SFU)

Determining the rational solvability of algebraic curves

Given a polynomial f(x,y) with coefficients in Q, can you describe all the values x,y in Q such that f(x,y)=0? Can you determine if there are any such solutions? Many of the oldest questions in mathematics can be viewed as instances of this problem and one might therefore wonder if there is a general procedure for answering this question. Perhaps surprisingly, the answer is probably yes, and we have a candidate procedure! We just have no clue how to prove that this procedure will always eventually terminate. We can test that it often does in practice, though, and part of the procedure does run in provably finite time. In fact, Manjul Bhargava has been able to analyse this part sufficiently precisely to conclude that, in a certain precise sense, most curves of the form y^2-g(x)=0, where g is a polynomial of even degree at least 6, have no rational points. In this talk I shall sketch the procedure and give some computational and heuristic evidency why we think the procedure should always eventually succeed.

Nathan Ilten (SFU)

Using Geometry in Computational Algebra

Many interesting problems in mathematics can be reduced to determining if a system of multivariate polynomial equations has a solution. While the existence of such solutions can be determined algorithmically using Gröbner basis methods, in practice such computations can take longer than the life of our sun to terminate. In this talk, I will discuss how geometrical insight can often be used to avoid such lengthy calculations. As an example, we will see that the three by three determinant polynomial can be written as a sum of five products of linear forms, but not four.

Mark Schmidt (UBC)

Is greedy coordinate descent a terrible algorithm?

There has been significant recent work on the theory and application of randomized coordinate-descent algorithms in machine learning and statistics, beginning with the work of Nesterov [2010] who showed that a random-coordinate selection rule achieves the same convergence rate as the Gauss-Southwell selection rule. This result suggests that we should never use the Gauss-Southwell rule, as it is typically much more expensive than random selection. However, the empirical behaviours of these algorithms contradict this theoretical result: in applications where the computational costs of the selection rules are comparable, the Gauss-Southwell selection rule tends to perform substantially better than random coordinate selection. We give a simple analysis of the Gauss-Southwell rule showing that - except in extreme cases - it is always faster than choosing random coordinates. Further, in this work we (i) show that exact coordinate optimization improves the convergence rate for certain sparse problems, (ii) propose a Gauss-Southwell-Lipschitz rule that gives an even faster convergence rate given knowledge of the Lipschitz constants of the partial derivatives, (iii) analyze the effect of approximate Gauss-Southwell rules, and (iv) analyze a proximal-gradient variant of the Gauss-Southwell rule.

Brian Wetton (UBC)

Numerical methods for geometric motion

We consider the evolution of curves and curve networks in 2D. We describe it as geometric motion if the evolution only depends on the shape of the curve. There are applications in material science (the evolution of microstructure in materials) and image processing. In the first part of the talk, an overview and comparison of several mathematical formulations of the geometric evolution of curves is given, including tracking and level sets, and their numerical approximation. In the second part of the talk, a recently developed numerical framework is presented for computing the evolution of curves subject to a class of generalized singular interface conditions from nonlocal elliptic problems. The motivating example for the current work is a particular, singular, asymptotic limit of a system of reaction-diffusion equations: the saturated Gierer-Meinhardt system. This is joint work with Iain Moyles.