MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Average-case complexity without the black swans
Get PDFWe introduce the concept of weak average-case analysis as an attempt to achieve theoretical complexity results that are closer to practical experience than those resulting from traditional approaches. This concept is accepted in other areas such as non-asymptotic random matrix theory and compressive sensing, and has a particularly convincing interpretation in the most common situation encountered for condition numbers, where it amounts to replacing a null set of ill-posed inputs by a ``numerical null set''.
We illustrate the usefulness of these notions by considering three settings: (1) condition numbers that are inversely proportional to a distance of a homogeneous algebraic set of ill-posed inputs; (2) the running time of power iteration for computing a leading eigenvector of a Hermitian matrix; (3) Renegar's condition number for conic optimisation
The Right Way to Search Evolving Graphs
Get PDFEvolving graphs arise in many different contexts
where the interrelations between data elements change over
time. We present a breadth first search (BFS) algorithm for
evolving graphs that can track (active) nodes correctly. Using
simple examples, we show na �ıve matrix-matrix multiplication
on time-dependent adjacency matrices miscounts the number
of temporal paths. By mapping an evolving graph to an
adjacency matrix of the equivalent static graph, we prove
the properties of the BFS algorithm using the properties of
the adjacency matrix. Finally, demonstrate how the BFS over
evolving graphs can be applied to mining citation network
The Indian Schema as Analogical Reasoning
Get PDFWe investigate the validity of a reading of the Hindu Syllogism as presented within Gotama's Nyāya-Sūtra as Analogical Reasoning within the framework of Pure Inductive Logic
Efficient reduced basis methods for saddle point problems with applications in groundwater flow
Get PDFReduced basis methods (RBMs) are recommended to reduce the computational cost of solving parameter-dependent PDEs in scenarios where many choices of parameters need to be considered, for example in uncertainty quantification (UQ). A reduced basis is constructed during a computationally demanding offline (or set-up) stage that allows the user to obtain cheap approximations for parameters choices of interest, online. In this paper we consider RBMs for parameter-dependent saddle point problems, in particular the one that arises in the mixed formulation of the Darcy flow problem in groundwater flow modelling. We apply a discrete empirical interpolation method (DEIM) to approximate the inverse of the diffusion coefficient, which depends non-affinely on the system parameters. We develop an efficient RBM that exploits the DEIM approximation and combine it with a sparse grid stochastic collocation mixed finite element method (SCMFEM) to construct a surrogate solution, which then allows for efficient forward UQ. Through numerical experiments we demonstrate that significant computational savings can be made when we use the RB-DEIM-SCMFEM scheme over standard high fidelity methods. For groundwater flow problems, we provide a thorough cost assessment of the new method and show how the size of the reduced basis, and hence, the extent of the savings, depends on the statistical properties of the input parameters
Electrical Impedance tomography
Get PDFElectrical Impedance Tomography (EIT) is the recovery of the
conductivity (or conductivity and permittivity) of the interior ofa body from a knowledge of currents and voltages applied to its surface
Efficient block preconditioning for a C1 finite element discretisation of the Dirichlet biharmonic problem
Get PDFWe present an efficient block preconditioner for the two-dimensional biharmonic Dirichlet problem discretised by C1 bicubic Hermite finite elements. In this formulation each node in the mesh has four different degrees of freedom (DOFs). Grouping DOFs of the same type together leads to a natural blocking of the Galerkin coefficient matrix. Based on this block structure, we develop two preconditioners: a 2�2 block diagonal preconditioner (BD) and a block bordered diagonal (BBD) preconditioner. We prove mesh independent bounds for the spectra of the BD- preconditioned Galerkin matrix under certain conditions. The eigenvalue analysis is based on the fact that the proposed preconditioner, like the coefficient matrix itself, is symmetric positive definite and is assembled from element matrices. We demonstrate the effectiveness of the inexact version of the BBD preconditioner, which exhibits near-optimal scaling in terms of computational cost with respect to the discrete problem size. Finally, we study robustness of this preconditioner with respect to domain distortion and element stretching
Geometric structure for the principal series of a split reductive p-adic group with connected centre
Get PDFLet G be a split reductive p-adic group with connected centre. We show that each Bernstein block in the principal series of G admits a definite geometric structure, namely that of an extended quotient. For the Iwahori-spherical block, this extended quotient has the form T//W where T is a maximal torus in the Langlands dual group of G and W is the Weyl group of G
Transformations of Feynman path integrals and the generalized densities of Feynman pseudomeasures
Get PDFWe consider the application of transformations of Feynman path integralsand Feynman pseudomeasures to problems of quantum anomalies. With our method we resolve a standing controversy in the literature
Modelling and controlling risk in energy systems
Get PDFThe Autonomic Power System (APS) grand challenge was a multi-disciplinary EPSRC-funded research project that examined novel techniques that would enable the transition between today's and 2050's highly uncertain and complex energy network. Being part of the APS, this thesis reports on the sub-project `RR2: Avoiding High-Impact Low Probability events'. The goal of RR2 is to develop new algorithms for controlling risk exposure to high-impact low probability (Hi-Lo) events through the provision of appropriate risk-sensitive control strategies. Additionally, RR2 is concerned with new techniques for identifying and modelling risk in future energy networks, in particular, the risk of Hi-Lo events.
In this context, this thesis investigates two distinct problems arising from energy risk management. On the one hand, we examine the problem of finding managerial strategies for exercising the operational flexibility of energy assets. We look at this problem from a risk perspective taking into account non-linear risk preferences of energy asset managers. Our main contribution is the development of a risk-sensitive approach to the class of optimal switching problems. By recasting the problem as an iterative optimal stopping problem, we are able to characterise the optimal risk-sensitive switching strategies. As byproduct, we obtain a multiplicative dynamic programming equation for the value function, upon which we propose a numerical algorithm based on least squares Monte Carlo regression.
On the other hand, we develop tools to identify and model the risk factors faced by energy asset managers. For this, we consider a class of models consisting of superposition of Gaussian and non-Gaussian Ornstein-Uhlenbeck processes. Our main contribution is the development of a Bayesian methodology based on Markov chain Monte Carlo (MCMC) algorithms to make inference into this class of models. On extensive simulations, we demonstrate the robustness and efficiency of the algorithms to different data features. Furthermore, we construct a diagnostic tool based on Bayesian p-values to check goodness-of-fit of the models on a Bayesian framework. We apply this tool to MCMC results from fitting historical electricity and gas spot price datasets corresponding to the UK and German energy markets. Our analysis demonstrates that the MCMC-estimated models are able to capture not only long- and short-lived positive price spikes, but also short-lived negative price spikes which are typical of UK gas prices and German electricity prices.
Combining together the solutions to the two problems above, we strive to capture the interplay between risk, uncertainty, flexibility and performance in various applications to energy systems. In these applications, which include power stations, energy storage and district energy systems, we consistently show that our risk management methodology offers a tradeoff between maximising average performance and minimising risk, while accounting for the jump dynamics of energy prices. Moreover, the tradeoff is achieved in such way that the benefits in terms of risk reduction outweigh the loss in average performance
Bounds for the Distance to the Nearest Correlation Matrix
Get PDFIn a wide range of practical problems correlation matrices are formed in such a way that, while symmetry and a unit diagonal are assured, they may lack semidefiniteness. We derive a variety of new upper bounds for the distance from an arbitrary symmetric matrix to the nearest correlation matrix. The bounds are of two main classes: those based on the eigensystem and those based on a modified Cholesky factorization. Bounds from both classes have a computational cost of flops for a matrix of order but are much less expensive to evaluate than the nearest correlation matrix itself. For unit diagonal with for all the eigensystem bounds are shown to overestimate the distance by a factor at most . We show that for a collection of matrices from the literature and from practical applications the eigensystem-based bounds are often good order of magnitude estimates of the actual distance; indeed the best upper bound is never more than a factor larger than a related lower bound. The modified Cholesky bounds are less sharp but also less expensive, and they provide an efficient way to test for definiteness of the putative correlation matrix. Both classes of bounds enable a user to identify an invalid correlation matrix relatively cheaply and to decide whether to revisit its construction or to compute a replacement, such as the nearest correlation matrix