Tue, 18 Feb 2020
16:00
C1

Quasi-locality and asymptotic expanders

Jan Spakula
(University of Southampton)
Abstract

Let $X$ be a countable discrete metric space, and think of operators on $\ell^2(X)$ in terms of their $X$-by-$X$ matrix. Band operators are ones whose matrix is supported on a "band" along the main diagonal; all norm-limits of these form a C*-algebra, called uniform Roe algebra of $X$. This algebra "encodes" the large-scale (a.k.a. coarse) structure of $X$. Quasi-locality, coined by John Roe in '88, is a property of an operator on $\ell^2(X)$, designed as a condition to check whether the operator belongs to the uniform Roe algebra (without producing band operators nearby). The talk is about our attempt to make this work, and an expander-ish condition on graphs that came out of trying to find a counterexample. (Joint with: A. Tikuisis, J. Zhang, K. Li and P. Nowak.)
 

Fri, 06 Dec 2019

15:00 - 16:00
N3.12

Measuring the stability of Mapper type algorithms

Matt Burfitt
(University of Southampton)
Abstract

The goal of topological data analysis is to apply tools form algebraic topology to reveal geometric structures hidden within high dimensional data. Mapper is among its most widely and successfully applied tools providing, a framework for the geometric analysis of point cloud data. Given a number of input parameters, the Mapper algorithm constructs a graph, giving rise to a visual representation of the structure of the data.  The Mapper graph is a topological representation, where the placement of individual vertices and edges is not important, while geometric features such as loops and flares are revealed.

 

However, Mappers method is rather ad hoc, and would therefore benefit from a formal approach governing how to make the necessary choices. In this talk I will present joint work with Francisco Belchì, Jacek Brodzki, and Mahesan Niranjan. We study how sensitive to perturbations of the data the graph returned by the Mapper algorithm is given a particular tuning of parameters and how this depend on the choice of those parameters. Treating Mapper as a clustering generalisation, we develop a notion of instability of Mapper and study how it is affected by the choices. In particular, we obtain concrete reasons for high values of Mapper instability and experimentally demonstrate how Mapper instability can be used to determine good Mapper outputs.

 

Our approach tackles directly the inherent instability of the choice of clustering procedure and requires very few assumption on the specifics of the data or chosen Mapper construction, making it applicable to any Mapper-type algorithm.

Mon, 04 Mar 2019
15:45
L6

Acylindrically hyperbolic groups with strong fixed point properties

Ashot Minasyan
(University of Southampton)
Abstract


The concept of an acylindrically hyperbolic group, introduced by D. Osin, generalizes hyperbolic and relatively hyperbolic groups, and includes many other groups of interest: Out(F_n), n>1, most mapping class groups, directly indecomposable non-cyclic right angled Artin groups, most graph products, groups of deficiency at least 2, etc. Roughly speaking, a group G is acylindrically hyperbolic if there is a (possibly infinite) generating set X of G such that the Cayley graph \Gamma(G,X) is hyperbolic and the action of G on it is "sufficiently nice". Many global properties of hyperbolic/relatively hyperbolic groups have been also proved for acylindrically hyperbolic groups. 
In the talk I will discuss a method which allows to construct a common acylindrically hyperbolic quotient for any countable family of countable acylindrically hyperbolic groups. This allows us to produce acylindrically hyperbolic groups with many unexpected properties.(The talk will be based on joint work with Denis Osin.)
 

Thu, 27 Feb 2014

14:00 - 15:00
Rutherford Appleton Laboratory, nr Didcot

Alternating minimal energy methods for linear systems in higher dimensions

Dr Dmitry Savostyanov
(University of Southampton)
Abstract

When high-dimensional problems are concerned, not much algorithms can break the curse of dimensionality, and solve them efficiently and reliably. Among those, tensor product algorithms, which implement the idea of separation of variables for multi-index arrays (tensors), seem to be the most general and also very promising. They originated in quantum physics and chemistry and descent broadly from the density matrix renormalization group (DMRG) and matrix product states (MPS) formalisms. The same tensor formats were recently re-discovered in the numerical linear algebra (NLA) community as the tensor train (TT) format.

Algorithms developed in the quantum physics community are based on the optimisation in tensor formats, that is performed subsequently for all components of a tensor format (i.e. all sites or modes).
The DMRG/MPS schemes are very efficient but very difficult to analyse, and at the moment only local convergence results for the simplest algorithm are available. In the NLA community, a common approach is to use a classical iterative scheme (e.g. GMRES) and enforce the compression to a tensor format at every step. The formal analysis is quite straightforward, but tensor ranks of the vectors which span the Krylov subspace grow rapidly with iterations, and the methods are struggling in practice.

The first attempt to merge classical iterative algorithms and DMRG/MPS methods was made by White (2005), where the second Krylov vector is used to expand the search space on the optimisation step.
The idea proved to be useful, but the implementation was based on the fair amount of physical intuition, and the algorithm is not completely justified.

We have recently proposed the AMEn algorithm for linear systems, that also injects the gradient direction in the optimisation step, but in a way that allows to prove the global convergence of the resulted scheme. The scheme can be easily applied for the computation of the ground state --- the differences to the algorithm of S. White are emphasized in Dolgov and Savostyanov (2013).
The AMEn scheme is already acknowledged in the NLA community --- for example it was recently applied for the computation of extreme eigenstates by Kressner, Steinlechner and Uschmajew (2013), using the block-TT format proposed by in Dolgov, Khoromskij, Oseledets and Savostyanov (2014).

At the moment, AMEn algorithm was applied
 - to simulate the NMR spectra of large molecules (such as ubiquitin),
 - to solve the Fokker-Planck equation for the non-Newtonian polymeric flows,
 - to the chemical master equation describing the mesoscopic model of gene regulative networks,
 - to solve the Heisenberg model problem for a periodic spin chain.
We aim to extend this framework and the analysis to other problems of NLA: eigenproblems, time-dependent problems, high-dimensional interpolation, and matrix functions;  as well as to a wider list of high-dimensional problems.

This is a joint work with Sergey Dolgov the from Max-Planck Institute for Mathematics in the Sciences, Leipzig, Germany.

Tue, 22 Oct 2013

14:30 - 15:00
L5

Alternating minimal energy methods for linear systems in higher dimensions.

Dmitry Savostyanov
(University of Southampton)
Abstract

We propose a new algorithm for the approximate solution of large-scale high-dimensional tensor-structured linear systems. It can be applied to high-dimensional differential equations, which allow a low-parametric approximation of the multilevel matrix, right-hand side and solution in a tensor product format. We apply standard one-site tensor optimisation algorithm (ALS), but expand the tensor manifolds using the classical iterative schemes (e.g. steepest descent).  We obtain the rank--adaptive algorithm with the theoretical convergence estimate not worse than the one of the steepest descent, and fast practical convergence, comparable or even better than the convergence of more expensive two-site optimisation algorithm (DMRG).
The method is successfully applied for a high--dimensional problem of quantum chemistry, namely the NMR simulation of a large peptide.

This is a joint work with S.Dolgov (Max-Planck Institute, Leipzig, Germany), supported by RFBR and EPSRC grants.

Keywords: high--dimensional problems, tensor train format, ALS, DMRG, steepest descent, convergence rate, superfast algorithms, NMR.

Wed, 15 May 2013

16:00 - 17:00
SR2

Partial actions of Groups in Coarse Geometry

Martin Finn-Sell
(University of Southampton)
Abstract

Group actions play an important role in both topological problems and coarse geometric conjectures. I will introduce the idea of a partial action of a group on a metric space and explain, in the case of certain classes of coarsely disconnected spaces, how partial actions can be used to give a geometric proof of a result of Willett and Yu concerning the coarse Baum-Connes conjecture.

Tue, 28 Feb 2012
17:00
L2

"Tits alternatives for graph products of groups".

Ashot Minasyan
(University of Southampton)
Abstract

 Graph products of groups naturally generalize direct and free products and have a rich subgroup structure. Basic examples of graph products are right angled Coxeter and Artin groups. I will discuss various forms of Tits Alternative for subgroups and
their stability under graph products. The talk will be based on a joint work with Yago Antolin Pichel.

Thu, 27 Jan 2000

14:00 - 15:00
Comlab

Entropy Splitting for High-Order Numerical Simulation of Compressible Turbulence

Prof Neil Sandham
(University of Southampton)
Abstract

This work forms part of a larger research project to develop efficient

low-dissipative high-order numerical techniques for high-speed

turbulent flow simulation, including shock wave interactions with

turbulence. The requirements on a numerical method are stringent.For

the turbulence the method must be capable of resolving accurately a

wide range of length scales, whilst for shock waves the method must be

stable and not generate excessive local oscillations. Conventional

methods are either too dissipative, or incapable of shock capturing.

Higher-order ENO, WENO or hybrid schemes are too expensive for

practical computations. Previous work of Yee, Sandham & Djomehri

(1999) developed high-order shock-capturing schemes which minimize the

use of numerical dissipation away from shock

waves. The objective of the present study is to further minimize the

use of numerical dissipation for shock-free compressible turbulence

simulations.

Subscribe to University of Southampton