Mathematics thesis and dissertation collectionhttps://hdl.handle.net/1842/22842020-02-23T05:34:27Z2020-02-23T05:34:27ZDerived contraction algebraBooth, Matt Paulhttps://hdl.handle.net/1842/366702019-12-20T14:21:25Z2019-11-25T00:00:00ZDerived contraction algebra
Booth, Matt Paul
All minimal models of a given variety are linked by special birational maps called flops, which
are a type of codimension two surgery. A version of the Bondal–Orlov conjecture, proved by
Bridgeland, states that if X and Y are smooth complex projective threefolds linked by a flop,
then they are derived equivalent (i.e. their bounded derived categories of coherent sheaves are
equivalent). Van den Bergh was able to give a new proof of Bridgeland’s theorem using the
notion of a noncommutative crepant resolution, which is in particular a ring A together with
a derived equivalence between X and A. The ring A is constructed as an endomorphism ring
of a decomposable module, and hence admits an idempotent e. Donovan and Wemyss define
the contraction algebra to be the quotient of A by e; it is a finite-dimensional noncommutative
algebra that is conjectured to completely recover the geometry of the base of the flop. They
show that it represents the noncommutative deformation theory of the flopping curves, as well
as controlling the flop-flop autoequivalence of the derived category of X (which, for the algebraic
model A, is the mutation-mutation autoequivalence).
In this thesis, I construct and prove properties of a new invariant, the derived contraction
algebra, which I define to be Braun–Chuang–Lazarev’s derived quotient of A by e. A priori, the
derived contraction algebra – which is a dga, rather than just an algebra – is a finer invariant
than the classical contraction algebra. I prove (using recent results of Hua and Keller) a derived
version of the Donovan–Wemyss conjecture, a suitable phrasing of which is true in all dimensions.
I prove that the derived quotient admits a deformation-theoretic interpretation; the proof
is purely homotopical algebra and relies at heart on a Koszul duality result. I moreover prove
that in an appropriate sense, the derived contraction algebra controls the mutation-mutation
autoequivalence. These results both recover and extend Donovan–Wemyss’s. I give concrete
applications and computations in the case of partial resolutions of Kleinian singularities, where
the classical contraction algebra becomes inadequate.
2019-11-25T00:00:00ZMonte-Carlo based numerical methods for a class of non-local deterministic PDEs and several random PDE systemsTan, Shurenhttps://hdl.handle.net/1842/365392019-11-26T15:28:13Z2019-11-28T00:00:00ZMonte-Carlo based numerical methods for a class of non-local deterministic PDEs and several random PDE systems
Tan, Shuren
In this thesis, we will investigate McKean-Vlasov SDEs (McKV-SDEs) on Rd,:
; where coefficient functions b and σ satisfy sufficient regularity conditions and
fWtgt2[0;T ] is a Wiener process. These SDEs correspond to a class of deterministic
non-local PDEs.
The principal aim of the first part is to present Multilevel Monte Carlo (MLMC)
schemes for the McKV-SDEs. To overcome challenges due to the dependence
of coefficients on the measure, we work with Picard iteration. There are two
different ways to proceed. The first way is to address the McKV-SDEs with
interacting kernels directly by combining MLMC and Picard. The MLMC is used
to represent the empirical densities of the mean-fields at each Picard step. This
iterative MLMC approach reduces the computational complexity of calculating
expectations by an order of magnitude.However, we can also link the McKV-SDEs with interacting kernels to that with
non-interacting kernels by projection and then iteratively solve the simpler by
MLMC method. In each Picard iteration, the MLMC estimator can approximate
a few mean-fields directly. This iterative MLMC approach via projection reduces
the computational complexity of calculating expectations hugely by three orders
of magnitude.
In the second part, the main purpose is to demonstrate the plausibility of applying
deep learning technique to several types of random linear PDE systems. We
design learning algorithms by using probabilistic representation and Feynman-
Kac formula is crucial for deriving the recursive relationships on constructing the
loss function in each training session.
2019-11-28T00:00:00ZLandscape of Hamiltonian phase spaces: on the foundations and generalizations of one of the most powerful ideas of modern scienceZapata-Carratala, Carloshttps://hdl.handle.net/1842/362292019-10-23T13:05:10Z2019-11-28T00:00:00ZLandscape of Hamiltonian phase spaces: on the foundations and generalizations of one of the most powerful ideas of modern science
Zapata-Carratala, Carlos
In this thesis we aim to revise the fundamental concept of phase space in modern physics and to devise a way
to explicitly incorporate physical dimension into geometric mechanics. To this end we begin with a nearly
self-contained presentation of local Lie algebras, Lie algebroids, Poisson and symplectic manifolds, line bundles
and Jacobi and contact manifolds, that elaborates on the existing literature on the subject by introducing the
notion of unit-free manifold.
We give a historical account of the evolution of metrology and the notion of phase space in order to illustrate the
disconnect between the theoretical models in use today and the formal treatment of physical dimension and units
of measurement.
A unit-free manifold is, mathematically, simply a generic line bundle over a smooth manifold but our interpretation,
that will drive several conjectures and that will allow us to argue in favor of its use for the problem of implementing
physical dimension in geometric mechanics, is that of a manifold whose ring of functions no longer has a preferred
choice of a unit.
We prove a breadth of results for unit-free manifolds in analogy with ordinary manifolds: existence of Cartesian
products, derivations as tangent vectors, jets as cotangent vectors, submanifolds and quotients by group actions.
This allows to reinterpret the notion of Jacobi manifold found in the literature as the unit-free analogue of Poisson
manifolds. With this new language we provide some new proofs for Jacobi maps, coisotropic submanifolds, Jacobi
products and Jacobi reduction.
We give a precise categorical formulation of the loose term 'canonical Hamiltonian mechanics' by defining the
precise notions of theory of phase spaces and Hamiltonian functor, which in the case of conventional symplectic
Hamiltonian mechanics corresponds to the cotangent functor. Conventional configuration spaces are then replaced
by line bundles, what we call unit-free configuration spaces, and, after proving some specific results about the
contact geometry of jet bundles, they are shown to fit into a theory of phase spaces with a Hamiltonian functor
given by the jet functor. We thus find canonical contact Hamiltonian mechanics.
Motivated by the algebraic structure of physical quantities in dimensional analysis, we redevelop the elementary
notions of the theory of groups, rings, modules and algebras by implementing an addition operation that is only
defined partially. In this formalism, the notions of dimensioned ring and dimensioned Poisson algebra appear
naturally and we show that Jacobi manifolds provide a prime example. Furthermore, this correspondence allows
to recover an explicit Leibniz rule for the Jacobi bracket, Jacobi maps, coisotropic submanifolds, and Jacobi
reduction as their dimensioned Poisson analogues thus completing the picture that Jacobi manifolds are the
direct unit-free analogue of ordinary Poisson manifolds.
2019-11-28T00:00:00ZRandomized iterative methods for linear systems: momentum, inexactness and gossipLoizou, Nicolashttps://hdl.handle.net/1842/362032019-09-25T11:00:20Z2019-11-28T00:00:00ZRandomized iterative methods for linear systems: momentum, inexactness and gossip
Loizou, Nicolas
In the era of big data, one of the key challenges is the development of novel optimization
algorithms that can accommodate vast amounts of data while at the same time satisfying
constraints and limitations of the problem under study. The need to solve optimization problems
is ubiquitous in essentially all quantitative areas of human endeavour, including industry and
science. In the last decade there has been a surge in the demand from practitioners, in fields
such as machine learning, computer vision, artificial intelligence, signal processing and data
science, for new methods able to cope with these new large scale problems.
In this thesis we are focusing on the design, complexity analysis and efficient implementations
of such algorithms. In particular, we are interested in the development of randomized first
order iterative methods for solving large scale linear systems, stochastic quadratic optimization
problems and the distributed average consensus problem.
In Chapter 2, we study several classes of stochastic optimization algorithms enriched with
heavy ball momentum. Among the methods studied are: stochastic gradient descent, stochastic
Newton, stochastic proximal point and stochastic dual subspace ascent. This is the first time
momentum variants of several of these methods are studied. We choose to perform our analysis
in a setting in which all of the above methods are equivalent: convex quadratic problems. We
prove global non-asymptotic linear convergence rates for all methods and various measures of
success, including primal function values, primal iterates, and dual function values. We also
show that the primal iterates converge at an accelerated linear rate in a somewhat weaker sense.
This is the first time a linear rate is shown for the stochastic heavy ball method (i.e., stochastic
gradient descent method with momentum). Under somewhat weaker conditions, we establish
a sublinear convergence rate for Cesaro averages of primal iterates. Moreover, we propose a
novel concept, which we call stochastic momentum, aimed at decreasing the cost of performing
the momentum step. We prove linear convergence of several stochastic methods with stochastic
momentum, and show that in some sparse data regimes and for sufficiently small momentum
parameters, these methods enjoy better overall complexity than methods with deterministic
momentum. Finally, we perform extensive numerical testing on artificial and real datasets.
In Chapter 3, we present a convergence rate analysis of inexact variants of stochastic gradient
descent, stochastic Newton, stochastic proximal point and stochastic subspace ascent.
A common feature of these methods is that in their update rule a certain sub-problem needs
to be solved exactly. We relax this requirement by allowing for the sub-problem to be solved
inexactly. In particular, we propose and analyze inexact randomized iterative methods for
solving three closely related problems: a convex stochastic quadratic optimization problem, a
best approximation problem and its dual { a concave quadratic maximization problem. We
provide iteration complexity results under several assumptions on the inexactness error. Inexact
variants of many popular and some more exotic methods, including randomized block
Kaczmarz, randomized Gaussian Kaczmarz and randomized block coordinate descent, can be
cast as special cases. Finally, we present numerical experiments which demonstrate the benefits
of allowing inexactness.
When the data describing a given optimization problem is big enough, it becomes impossible
to store it on a single machine. In such situations, it is usually preferable to distribute the data
among the nodes of a cluster or a supercomputer. In one such setting the nodes cooperate
to minimize the sum (or average) of private functions (convex or non-convex) stored at the
nodes. Among the most popular protocols for solving this problem in a decentralized fashion
(communication is allowed only between neighbours) are randomized gossip algorithms.
In Chapter 4 we propose a new approach for the design and analysis of randomized gossip
algorithms which can be used to solve the distributed average consensus problem, a fundamental
problem in distributed computing, where each node of a network initially holds a number or
vector, and the aim is to calculate the average of these objects by communicating only with
its neighbours (connected nodes). The new approach consists in establishing new connections to
recent literature on randomized iterative methods for solving large-scale linear systems. Our
general framework recovers a comprehensive array of well-known gossip protocols as special
cases and allow for the development of block and arbitrary sampling variants of all of these
methods. In addition, we present novel and provably accelerated randomized gossip protocols
where in each step all nodes of the network update their values using their own information but
only a subset of them exchange messages. The accelerated protocols are the first randomized
gossip algorithms that converge to consensus with a provably accelerated linear rate. The
theoretical results are validated via computational testing on typical wireless sensor network
topologies.
Finally, in Chapter 5, we move towards a different direction and present the first randomized
gossip algorithms for solving the average consensus problem while at the same time protecting
the private values stored at the nodes as these may be sensitive. In particular, we develop
and analyze three privacy preserving variants of the randomized pairwise gossip algorithm
("randomly pick an edge of the network and then replace the values stored at vertices of this
edge by their average") first proposed by Boyd et al. [16] for solving the average consensus
problem. The randomized methods we propose are all dual in nature. That is, they are designed
to solve the dual of the best approximation optimization formulation of the average consensus
problem. We call our three privacy preservation techniques "Binary Oracle", "ε -Gap Oracle"
and "Controlled Noise Insertion". We give iteration complexity bounds for the proposed privacy
preserving randomized gossip protocols and perform extensive numerical experiments.
2019-11-28T00:00:00Z