A stable algorithm to compute the roots of polynomials is presented. The roots are found by computing the eigenvalues of the associated companion matrix by Francis's implicitly-shifted $QR$ algorithm.  A companion matrix is an upper Hessenberg matrix that is unitary-plus-rank-one, that is, it is the sum of a unitary matrix and a rank-one matrix.  These properties are preserved by iterations of Francis's algorithm, and it is these properties that are exploited here. The matrix is represented as a product of $3n-1$ Givens rotators plus the rank-one part, so only $O(n)$ storage space is required.  In fact, the information about the rank-one part is also encoded in the rotators, so it is not necessary to store the rank-one part explicitly.  Francis's algorithm implemented on this representation requires only $O(n)$ flops per iteration and thus $O(n^{2})$ flops overall.  The algorithm is described, backward stability is proved under certain conditions on the polynomial coefficients, and an extensive set of numerical experiments is presented.  The algorithm is shown to be about as accurate as the (slow) Francis $QR$ algorithm applied to the companion matrix without exploiting the structure.  It is faster than other fast methods that have been proposed, and its accuracy is comparable or better.

We present advances in several fundamental fields of computer vision: image segmentation, object tracking, stereo reconstruction for depth map estimation and full 3D multi-view reconstruction. The basic method applied to these fields is convex relaxation. Convex relaxation methods allow for global optimization of numerous energy functionals and provide a step towards less user input and more automation. We will show how the respective computer vision problems can be formulated in this convex optimization framework. Efficient parallel implementations of the arising numerical schemes using graphics processing units allow for interactive applications.

Modularity is a quality function on partitions of a network which aims to identify highly clustered components. Given a graph G, the modularity of a partition of the vertex set measures the extent to which edge density is higher within parts than between parts; and the modularity q(G) of G is the maximum modularity of a partition of V(G). Knowledge of the maximum modularity of the corresponding random graph is important to determine the statistical significance of a partition in a real network. We provide bounds for the modularity of random regular graphs. Modularity is related to the Hamiltonian of the Potts model from statistical physics. This leads to interest in the modularity of lattices, which we will discuss. This is joint work with Colin McDiarmid.

The curve graph of a surface has a vertex for each curve on the surface and an edge for each pair of disjoint curves. Although it deals with very simple objects, it has connections with questions in low-dimensional topology, and some properties that encourage people to study it. Yet it is more complicated than it may look from its definition: in particular, what happens if we start following a 'diverging' path along this graph? It turns out that the curves we hit get so complicated that eventually give rise to a lamination filling up the surface. This can be understood by drawing some train track-like pictures on the surface. During the talk I will keep away from any issue that I considered too technical.

Cluster algebras are commutative algebras generated by a set S, obtained by an iterated mutation process of an initial seed. They were introduced by S. Fomin and A. Zelevinski in connection with canonical bases in Lie theory. Since then, many connections between cluster algebras and other areas have arisen.
This talk will focus on cluster algebras for which the set S is finite. These are called cluster algebras of finite type and are classified by Dynkin diagrams, in a similar way to many other objects.

Stallings' folding technique lets us factor a map of graphs as a sequence of "folds" (edge identifications) followed by an immersion. We will show how this technique gives an algorithm to express a free-group automorphism as the product of Whitehead automorphisms (and hence Nielsen transformations), as well as proving finite generation for some subgroups of the automorphism group of a free group.

Traditionally threshold partial pivoting is used to ensure stability of sparse LDL^T factorizations of symmetric matrices. This involves comparing a candidate pivot with all entries in its row/column to ensure that growth in the size of the factors is limited by a threshold at each stage of the factorization. It is capabale of delivering a scaled backwards error on the level of machine precision for practically all real world matrices. However it has significant flaws when used in a massively parallel setting, such as on a GPU or modern supercomputer. It requires all entries of the column to be up-to-date and requires an all-to-all communication for every column. The latter requirement can be performance limiting as the factorization cannot proceed faster than k*(communication latency), where k is the length of the longest path in the sparse elimination tree.

We introduce a new family of communication-avoiding pivoting techniques that reduce the number of messages required by a constant factor allowing the communication cost to be more effectively hidden by computation. We exhibit two members of this family. The first deliver equivalent stability to threshold partial pivoting, but is more pessimistic, leading to additional fill in the factors. The second provides similar fill levels as traditional techniques and, whilst demonstrably unstable for pathological cases, is able to deliver machine accuracy on even the worst real world examples.

The relationship of diagonal dominance ideas to the convergence of stationary iterations is well known. There are a multitude of situations in which such considerations can be used to guarantee convergence when the splitting matrix (the preconditioner) is positive definite. In this talk we will describe and prove sufficient conditions for convergence of a stationary iteration based on a splitting with an indefinite preconditioner. Simple examples covered by this theory coming from Optimization and Economics will be described.

This is joint work with Michael Ferris and Tom Rutherford

This brief lecture will highlight several best-practice observations and
research for writing software for mathematical research, drawn from a
number of sources, including; Best Practices for Scientific Computing
[BestPractices], Code Complete [CodeComplete], and personal observation
from the presenter.  Specific focus will be given to providing the
definition of important concepts, then describing how to apply them
successfully in day-to-day research settings.  Following the outline from
Best Practices, we will cover the following topics:

* Write Programs for People, Not Computers
* Let the Computer Do the Work
* Make Incremental Changes
* Don't Repeat Yourself (or Others)
* Plan for Mistakes
* Optimize Software Only after It Works Correctly
* Document Design and Purpose, Not Mechanics
* Collaborate

[BestPractices]
http://www.plosbiology.org/article/info%3Adoi%2F10.1371%2Fjournal.pbio.1001745
[CodeComplete] http://www.cc2e.com/Default.aspx