DSpace Collection:
http://hdl.handle.net/2381/4137
Thu, 08 Oct 2015 20:10:26 GMT2015-10-08T20:10:26ZAdaptive radial basis functions for option pricing
http://hdl.handle.net/2381/32527
Title: Adaptive radial basis functions for option pricing
Authors: Li, Juxi
Abstract: In this thesis, we have developed meshless adaptive radial basis functions (RBFs)
method for the pricing of financial contracts by solving the Black-Scholes partial
differential equation (PDE). In the 1-D problem, we priced the financial contracts
of a European call option, Greeks (Delta, Gamma and Vega), an American put
option and a barrier up and out call option with this method. In the BENCHOP
project with Challenge Parameter Set (Parameter Set 2) [97], we have shown
that our adaptive method is highly accurate and with less computational cost in
comparison with the finite difference method for the European call option and
barrier up and out call option. And also we have presented the numerical result of
the equally spaced RBF method for both Parameter Set 1 and 2. In our numerical
simulations with Parameter Set 2, we note that our adaptive method is more
accurate and faster than the equally spaced RBF method. For example for the
barrier up and out call option, the equally spaced method (MQ) with 3000 uniform
nodes has the maximum error of 1.30e-02 at three evaluation points, but our
adaptive method (101 nodes) has maximum error of 9.98e-05 at the same three
points. This is about 100 times better than the equally spaced method with about
30 times less CPU time. Since our adaptive strategy is accurate and efficient, we
substantially increase the accuracy with fewer number of nodes.
We also developed an adaptive algorithm for the 2 assets Black-Scholes problem,
in this algorithm we used the rectangular Voronoi points for the refinement, and
the thin plate spline is used for the local approximation in order to assess the
error. The numerical results of pricing a Margrabe call option are presented for
both adaptive and non-adaptive methods. The adaptive method is more accurate
and requires fewer nodes when compared to the equally spaced RBF method.Thu, 09 Jul 2015 09:26:08 GMThttp://hdl.handle.net/2381/325272015-07-09T09:26:08ZModel Reductions in Biochemical Reaction Networks
http://hdl.handle.net/2381/32442
Title: Model Reductions in Biochemical Reaction Networks
Authors: Khoshnaw, Sarbaz Hamza Abdullah
Abstract: Many complex kinetic models in the field of biochemical reactions
contain a large number of species and reactions. These models often require a
huge array of computational tools to analyse. Techniques of model reduction,
which arise in various theoretical and practical applications in systems biology,
represent key critical elements (variables and parameters) and substructures of
the original system. This thesis aims to study methods of model reduction for
biochemical reaction networks. It has three goals related to techniques of model
reduction. The primary goal provides analytical approximate solutions of such
models. In order to have this set of solutions, we propose an algorithm based on
the Duhamel iterates. This algorithm is an explicit formula that can be studied in
detail for wide regions of concentrations for optimization and parameter identification
purposes. Another goal is to simplify high dimensional models to smaller
sizes in which the dynamics of original models and reduced models should be
similar. Therefore, we have developed some techniques of model reduction such
as geometric singular perturbation method for slow and fast subsystems, and
entropy production analysis for identifying non–important reactions. The suggested
techniques can be applied to some models in systems biology including
enzymatic reactions, elongation factors EF–Tu and EF–Ts signalling pathways,
and nuclear receptor signalling. Calculating the value of deviation at each reduction
stage helps to check that the approximation of concentrations is still within
the allowable limits. The final goal is to identify critical model parameters and
variables for reduced models. We study the methods of local sensitivity in order
to find the critical model elements. The results are obtained in numerical simulations
based on Systems Biology Toolbox (SBToolbox) and SimBiology Toolbox for
Matlab. The simplified models would be accurate, robust, and easily applied by
biologists for various purposes such as reproducing biological data and functions
for the full models.Mon, 29 Jun 2015 14:29:24 GMThttp://hdl.handle.net/2381/324422015-06-29T14:29:24ZDerivative pricing in lévy driven models
http://hdl.handle.net/2381/32222
Title: Derivative pricing in lévy driven models
Authors: Kushpel, Alexander
Abstract: We consider an important class of derivative contracts written on multiple assets
which are traded on a wide range of financial markets. More specifically, we are
interested in developing novel methods for pricing financial derivatives using approximation
theoretic methods which are not well-known to the financial engineering
community. The problem of pricing of such contracts splits into two parts.
First, we need to approximate the respective density function which depends on the
adapted jump-diffusion model. Second, we need to construct a sequence of approximation
formulas for the price. These two parts are connected with the problem of
optimal approximation of infinitely differentiable, analytic or entire functions on
noncompact domains. We develop new methods of recovery of density functions
using sk-splines (in particular, radial basis functions), Wiener spaces and complex
exponents with frequencies from special domains. The respective lower bounds obtained
show that the methods developed have almost optimal rate of convergence
in the sense of n-widths. On the basis of results obtained we develop a new theory
of pricing of basket options under Lévy processess. In particular, we introduce
and study a class of stochastic systems to model multidimensional return process,
construct a sequence of approximation formulas for the price and establish the
respective rates of convergence.Thu, 07 May 2015 13:45:04 GMThttp://hdl.handle.net/2381/322222015-05-07T13:45:04ZAdaptive discontinuous Galerkin methods for nonlinear parabolic problems
http://hdl.handle.net/2381/32041
Title: Adaptive discontinuous Galerkin methods for nonlinear parabolic problems
Authors: Metcalfe, Stephen Arthur
Abstract: This work is devoted to the study of a posteriori error estimation and adaptivity
in parabolic problems with a particular focus on spatial discontinuous Galerkin
(dG) discretisations.
We begin by deriving an a posteriori error estimator for a linear non-stationary
convection-diffusion problem that is discretised with a backward Euler dG method.
An adaptive algorithm is then proposed to utilise the error estimator. The
effectiveness of both the error estimator and the proposed algorithm is shown
through a series of numerical experiments.
Moving on to nonlinear problems, we investigate the numerical approximation
of blow-up. To begin this study, we first look at the numerical approximation
of blow-up in nonlinear ODEs through standard time stepping schemes. We
then derive an a posteriori error estimator for an implicit-explicit (IMEX) dG
discretisation of a semilinear parabolic PDE with quadratic nonlinearity. An
adaptive algorithm is proposed that uses the error estimator to approach the
blow-up time. The adaptive algorithm is then applied in a series of test cases to
gauge the effectiveness of the error estimator.
Finally, we consider the adaptive numerical approximation of a nonlinear
interface problem that is used to model the mass transfer of solutes through
semi-permiable membranes. An a posteriori error estimator is proposed for the
IMEX dG discretisation of the model and its effectiveness tested through a series
of numerical experiments.Wed, 22 Apr 2015 14:56:10 GMThttp://hdl.handle.net/2381/320412015-04-22T14:56:10ZModelling biological invasions : population cycles, waves and time delays
http://hdl.handle.net/2381/31392
Title: Modelling biological invasions : population cycles, waves and time delays
Authors: Jankovic, Masha
Abstract: Biological invasions are rapidly gaining importance due to the ever-increasing number
of introduced species. Alongside the plenitude of empirical data on invasive
species there exists an equally broad range of mathematical models that might be
of use in understanding biological invasions.
This thesis aims to address several issues related to modelling invasive species
and provide insight into their dynamics. Part I (Chapter 2) documents a case
study of the gypsy moth, Lymantria dispar, invasion in the US. We propose an
alternative hypothesis to explain the patchiness of gypsy moth spread entailing
the interplay between dispersal, predation or a viral infection and the Allee effect.
Using a reaction-diffusion framework we test the two models (prey-predator and
susceptible-infected) and predict qualitatively similar patterns as are observed in
natural populations. As high density gypsy moth populations cause the most
damage, estimating the spread rate would be of help in any suppression strategy.
Correspondingly, using a diffusive SI model we are able to obtain estimates of the
rate of spread comparable to historical data.
Part II (Chapters 3, 4 and 5) is more methodological in nature, and in a single
species context we examine the effect of an ubiquitous phenomenon influencing
population dynamics time delay. In Chapter 3 we show that contrary to the
general opinion, time delays are not always destabilising, using a delay differential
equation with discrete time delay. The concept of distributed delay is introduced
in Chapter 4 and studied through an integrodifferential model. Both Chapters 3
and 4 focus on temporal dynamics of populations, so we further this consideration
to include spatial effects in Chapter 5. Using two different representations of movement,
we show that the onset of spatiotemporal chaos in the wake of population
fronts is possible in a single species model.Thu, 08 Jan 2015 12:53:35 GMThttp://hdl.handle.net/2381/313922015-01-08T12:53:35ZSpecial functions and generalized functions
http://hdl.handle.net/2381/30544
Title: Special functions and generalized functions
Authors: Al-Sirehy, Fatma.
Abstract: In 1950, Laurent Schwartz marked a convenient starting point for the theory of generalized functions as a subject in its own right. He developed and unified much of the earlier work by Hadamard, Bochner, Sobolev and others. Since then an enormous literature dealing with both theory and applications has grown up, and the subject has undergone extensive further development. The original Schwartz treatment defined a distribution as a linear continuous functional on a space of test functions.;This thesis can be considered a part of the development going in that direction. It is partly an extension of earlier contributions by Fisher, Kuribayashi, Itano and others.;After introducing the background and basic definitions in Chapter One, we developed some basic results concerning the cosine integral Ci(lambda x) and its associated functions Ci+(lambda x) and Ci-(lambdax) as well as the neutrix convolution products of the cosine integral.;Chapter Three is devoted to similar results concerning the sine integral Si(lambdax).;In Chapter Four, we generalize some earlier results by Fisher and Kuribayashi concerning the product of the two dimensions xl+ and x-l-r+ . Moreover, other results are obtained concerning the neutrix product of |x|lambda-r lnp |x| and sgn x| x|lambda-r. Other theorems are proved about the matrix product of some other distributions such as xl+ ln x+ and x-l-r- .;Chapter Five contains new results about the composition of distributions. It involves the applications of the neutrix limit to establish such relationships between different distributions.Mon, 15 Dec 2014 10:40:16 GMThttp://hdl.handle.net/2381/305442014-12-15T10:40:16ZAncient Egyptian astronomy : timekeeping and cosmography in the New Kingdom
http://hdl.handle.net/2381/30543
Title: Ancient Egyptian astronomy : timekeeping and cosmography in the New Kingdom
Authors: Symons, Sarah.
Abstract: The first part of this study analyses and discusses astronomical timekeeping methods used in the New Kingdom. Diagonal star clocks are examined first, looking at classification of sources, decan lists, and the updating of the tables over time. The date list in the Osireion at Abydos is discussed, and issues concerning its place in the history of astronomical timekeeping are raised. The final stellar timekeeping method, the Ramesside star clock, is then examined. The conventional interpretation of the observational method behind the tables is challenged by a new theory, and a system of analysing the tables is introduced. The conclusions of the previous sections are then gathered together in a discussion of the development of stellar timekeeping methods.;The small instruments known as shadow clocks, and their later relatives the sloping sundials, are also examined. The established hypothesis that the shadow clock was completed by the addition of a crossbar is challenged and refuted.;The second part of this study is based on New Kingdom representations of the sky. Two major texts and several celestial diagrams are discussed in detail, beginning with the Book of Nut, which describes the motions of the sun and stars. New translations of the vignette and dramatic text are presented and discussed. Portions of the Book of the Day describing the behaviour of the sun and circumpolar group of stars are analysed.;Finally, celestial diagrams dating from the New Kingdom are discussed. Their composition and significance is discussed and the conceptual framework behind the diagrams is recreated. By introducing new theories and analysis methods, and using a modern but sympathetic approach to the original sources, this study attempts to update and extend our knowledge of these areas of ancient astronomy..Mon, 15 Dec 2014 10:40:15 GMThttp://hdl.handle.net/2381/305432014-12-15T10:40:15ZData structures and implementation of an adaptive hp finite element method
http://hdl.handle.net/2381/30541
Title: Data structures and implementation of an adaptive hp finite element method
Authors: Senior, Bill.
Abstract: For a fully adaptive hp finite element programme to be implemented it is necessary to implement n-irregular meshes efficiently. This requires a sufficiently flexible data structure to be implemented. Because such flexibility is required, the traditional array based approach cannot be used because of its limited applicability. In this thesis this traditional approach has been replaced by an object orientated design and implementation. This leads to an implementation that can be extended easily and safely to include other problems for which it was not originally designed.;The problems with maintaining continuity on such a diverse variety of meshes and how continuity is maintained are discussed. Then the main structure of the mesh is described in the form of domain, subdomains and elements. These are used in conjunction with constraint mappings to give a conforming approximation even with the most irregular of meshes.;There are several varieties of matrix generated by the method each with its own problems of storage. Sparse matrices, with perhaps more than 95% of zero entries, need to be used along side dense matrices. In this thesis an object oriented matrix library is implemented that enables this variety of matrices to be used.;An hp finite element algorithm is then implemented using the data structures, and is tested on a range of test problems. The method is shown to be effective on these problems.Mon, 15 Dec 2014 10:40:15 GMThttp://hdl.handle.net/2381/305412014-12-15T10:40:15ZOn finite groups of p-local rank one and a conjecture of Robinson
http://hdl.handle.net/2381/30542
Title: On finite groups of p-local rank one and a conjecture of Robinson
Authors: Eaton, Charles.
Abstract: We use the classification of finite simple groups to verify a conjecture of Robinson for finite groups G where G/Op(G) has trivial intersection Sylow p-subgroups. Groups of this type are said to have p-local rank one, and it is hoped that this invariant will eventually form the basis for inductive arguments, providing reductions for the conjecture, or even a proof using the results presented here as a base. A positive outcome for Robinson's conjecture would imply Alperin's weight conjecture.;It is shown that in proving Robinson's conjecture it suffices to demonstrate only that it holds for finite groups in which Op(G) is both cyclic and central.;Part of the proof of the former result is used to complete the verification of Dade's inductive conjecture for the Ree groups of type G2.;.Mon, 15 Dec 2014 10:40:15 GMThttp://hdl.handle.net/2381/305422014-12-15T10:40:15ZA special numerical method for solving Hamiltonian eigenproblems
http://hdl.handle.net/2381/30540
Title: A special numerical method for solving Hamiltonian eigenproblems
Authors: Maple, Carsten R.
Abstract: In this thesis we develop and implement a new algorithm for finding the solutions of linear Hamiltonian systems arising from ordinary differential equation (ODE) eigenproblems; a large source of these systems is Sturm-Liouville problems, and these will provide the angle of approach. The convergence properties of the algorithm will be analysed, as will the performance of the algorithm for large values of eigenparameter.;An algorithm is also proposed to find high-index eigenvalues of general Sturm-Liouville problems.Mon, 15 Dec 2014 10:40:15 GMThttp://hdl.handle.net/2381/305402014-12-15T10:40:15ZMultivariate hermite interpolation in euclidean space and its unit sphere by radial basis functions
http://hdl.handle.net/2381/30539
Title: Multivariate hermite interpolation in euclidean space and its unit sphere by radial basis functions
Authors: Luo, Zuhua.
Abstract: In this thesis, we consider radial basis function interpolations in d-dimensional Euclidean space Hd and the unit sphere 5d_1, where the data is generated not only by point-evaluations, but also by the derivatives, or differential/pseudo-differential operators. Some sufficient and necessary conditions for the well-posedness of the interpolations are given. The results on sensitivity and sta bility of the interpolation systems are obtained. The optimal properties of the interpolants are analysed through the variational framework and reproducing kernel Hilbert space property, the error bounds and convergence rates of the interpolants are derived. The admissible reproducing kernel Hilbert spaces are also characterised.Mon, 15 Dec 2014 10:40:14 GMThttp://hdl.handle.net/2381/305392014-12-15T10:40:14ZOn indecomposable modules over cluster-tilted algebras of type A
http://hdl.handle.net/2381/30538
Title: On indecomposable modules over cluster-tilted algebras of type A
Authors: Parsons, Mark James
Abstract: Gabriel's Theorem describes the dimension vectors of the finitely generated indecomposable modules over the path algebra of a simply-laced Dynkin quiver. It shows that they can be obtained from the expressions for the positive roots of the corresponding root system in terms of the simple roots. Here, we present a method for finding the dimension vectors of the finitely generated indecomposable modules over a cluster-tilted algebra of Dynkin type A.;It is known that the quiver of a cluster-tilted algebra of Dynkin type A is given by an exchange matrix of the corresponding cluster algebra. We define a companion basis for such a quiver to be a Z -basis of roots of the integral root lattice of the corresponding root system whose associated matrix of inner products is a positive quasi-Cartan companion of the corresponding exchange matrix.;Our main result establishes that the dimension vectors of the finitely generated indecomposable modules over a cluster-tilted algebra of Dynkin type A arise from expressions for the positive roots of the corresponding root system in terms of a companion basis (for the quiver of that algebra). This can be regarded as a generalisation of part of Gabriel's Theorem in the Dynkin type A case. The proof uses the fact that the quivers of the cluster-tilted algebras of Dynkin type A have a particularly nice description in terms of triangulation of regular polygons.Mon, 15 Dec 2014 10:40:14 GMThttp://hdl.handle.net/2381/305382014-12-15T10:40:14ZAnisotropic adaptive refinement for discontinuous galerkin methods
http://hdl.handle.net/2381/30536
Title: Anisotropic adaptive refinement for discontinuous galerkin methods
Authors: Hall, Edward John Cumes
Abstract: We consider both the a priori and a posteriori error analysis and hp-adaptation strategies for discontinuous Galerkin interior penalty methods for second-order partial differential equations with nonnegative characteristic form on anisotropically refined computational meshes with anisotropically enriched polynomial degrees. In particular, we discuss the question of error estimation for linear target functionals, such as the outflow flux and the local average of the solution, exploiting duality based arguments.;The a priori error analysis is carried out in two settings. In the first, full orientation of elements is allowed but only (possibly high-order) isotropic polynomial degrees considered; our analysis, therefore, extends previous results, where only finite element spaces comprising piecewise linear polynomials were considered, by utilizing techniques from tensor analysis. In the second case, anisotropic polynomial degrees are allowed, but the elements are assumed to be axiparallel; we thus apply previously known interpolation error results to the goal-oriented setting.;Based on our a posteriori error bound we first design and implement an adaptive anisotropic h-refinement algorithm to ensure reliable and efficient control of the error in the prescribed functional to within a given tolerance. This involves exploiting both local isotropic and anisotropic mesh refinement, chosen on a competitive basis requiring the solution of local problems. The superiority of the proposed algorithm in comparison with a standard h-isotropic mesh refinement algorithm and a Hessian based h-anisotropic adaptive procedure is illustrated by a series of numerical experiments. We then describe a fully hp -adaptive algorithm, once again using a competitive refinement approach, which, numerical experiments reveal, offers considerable improvements over both a standard hp-isotropic refinement algorithm and an h-anisotropic/p-isotropic adaptive procedure.Mon, 15 Dec 2014 10:40:14 GMThttp://hdl.handle.net/2381/305362014-12-15T10:40:14ZOn the quiver and relations of the Borel Schur algebras
http://hdl.handle.net/2381/30537
Title: On the quiver and relations of the Borel Schur algebras
Authors: Liang, Degang
Abstract: Let K be an infinite field of characteristic p â‰¥ 0 and let n, r be positive integers. Let S+(n, r) be the Borel Schur algebra over K, which is a sub-algebra of the Schur algebra S(n, r). We aim to give a description of the Borel Schur algebra S+ (n, r) by finding its quiver and relations. We give a complete description of the quiver and relations for S+(2, r). We also construct a family of embedding from S+(2, r) to S+(n, r + s) which induce embeddings of the corresponding quivers. This gives us some relations for S+(n, r) for n > 2.;We describe the quiver of S+( n, r) for both p = 0 and p > 0. We also describe some relations of special type for p > 0 and find all relations for p = 0.Mon, 15 Dec 2014 10:40:14 GMThttp://hdl.handle.net/2381/305372014-12-15T10:40:14ZUncertainty propagation and reduction in reservoir forecasting
http://hdl.handle.net/2381/30534
Title: Uncertainty propagation and reduction in reservoir forecasting
Authors: Busby, Daniel
Abstract: In this work we focus on nonparametric regression techniques based on Gaussian process, considering both the frequentist and the Bayesian approach. A new sequential experimental design strategy referred to as hierarchical adaptive experimental design is proposed and tested on synthetic functions and on realistic reservoir models using a commercial oil reservoir multiphase flow simulator. Our numerical results show that the method effectively approximate the simulators output with the required approximation accuracy using an affordable number of simulator runs. Moreover, the number of simulations necessary to reach a given approximation accuracy is sensibly reduced respect to other existing experimental designs such as maximin latin hypercubes, or other classical designs used in commercial softwares.;Once an accurate emulator of the simulator output is obtained, it can be also used to calibrate the simulator model using data observed on the real physical system. This process, referred to as history matching in reservoir forecasting, is fundamental to tune input parameters and to consequently reduce output uncertainty. An approach to model calibration using Bayesian inversion is proposed in the last part of this work. Here again a hierarchical emulator is adopted. An innovative sequential design is proposed with the objective of increasing the emulator accuracy around possible history matching solutions. The excellent performances obtained on a very complicated reservoir test case, suggest the high potential of the method to solve complicated inverse problems. The proposed methodology is about to be commercialized in an industrial environment to assist reservoir engineers in uncertainty analysis and history matching.Mon, 15 Dec 2014 10:40:13 GMThttp://hdl.handle.net/2381/305342014-12-15T10:40:13ZEuler characteristics and cohomology for quasiperiodic projection patterns
http://hdl.handle.net/2381/30533
Title: Euler characteristics and cohomology for quasiperiodic projection patterns
Authors: Irving, Claire Louise
Abstract: This thesis investigates quasiperiodic patterns and, in particular, polytopal projection patterns, which are produced using the projection method by choosing the acceptance domain to be a polytope. Cohomology theories applicable in this setting are defined, together with the Euler characteristic.;Formulae for the Cech cohomology Hˇ* ( M P ) and Euler characteristic eP are determined for polytopal projection patterns of codimension 2 and calculations are carried out for several examples. The Euler characteristic is shown to be undefined for certain codimension 3 polytopal projection patterns. The Euler characteristic eP is proved to be always defined for a particular class of codimension n polytopal projection patterns P and a formula for eP for such patterns is given. The finiteness or otherwise of the rank of Hˇm(M P ) âŠ— Q for m â‰¥ 0 is also discussed for various classes of polytopal projection patterns. Lastly, a model for M P is considered which leads to an alternative method for computing the rank of Hˇm(M P ) âŠ— Q for P a d-dimensional codimension n polytopal projection pattern with d > n..Mon, 15 Dec 2014 10:40:13 GMThttp://hdl.handle.net/2381/305332014-12-15T10:40:13ZEfficient method for detection of periodic orbits in chaotic maps and flows
http://hdl.handle.net/2381/30535
Title: Efficient method for detection of periodic orbits in chaotic maps and flows
Authors: Crofts, Jonathan J.
Abstract: An algorithm for detecting unstable periodic orbits in chaotic systems [Phys. Rev. E, 60 (1999), pp. 6172-6175] which combines the set of stabilising transformations proposed by Schmelcher and Diakonos [Phys. Rev. Lett., 78 (1997), pp. 4733-4736] with a modified semi-implicit Euler iterative scheme and seeding with periodic orbits of neighbouring periods, has been shown to be highly efficient when applied to low-dimensional system. The difficulty in applying the algorithm to higher dimensional systems is mainly due to the fact that the number of stabilising transformations grows extremely fast with increasing system dimension. in this thesis, we propose to construct stabilising transformations based on the knowledge of the stability matrices of already detected periodic orbits (used as seeds). The advantage of our approach is in a substantial reduction of the number of transformations, which increases the efficiency of the detection algorithm, especially in the case of high-dimensional systems. The dependence of the number of transformations on the dimensionality of the unstable manifold rather than on system size enables us to apply, for the first time, the method of stabilising transformations to high-dimensional systems. Another important aspect of our treatment of high-dimensional flows is that we do not restrict to a Poincare surface of section. This is a particularly nice feature, since the correct placement of such a section in a high-dimensional phase space is a challenging problem in itself. The performance of the new approach is illustrated by its application to the four-dimensional kicked double rotor map, a six-dimensional system of three coupled Henon maps and to the Kuramoto-Sivashinsky system in the weakly turbulent regime.Mon, 15 Dec 2014 10:40:13 GMThttp://hdl.handle.net/2381/305352014-12-15T10:40:13ZLogic, computation and constraint satisfaction
http://hdl.handle.net/2381/30530
Title: Logic, computation and constraint satisfaction
Authors: Martin, Barnaby D.
Abstract: We study a class of non-deterministic program schemes with while loops: firstly, augmented with a priority queue for memory; secondly, augmented with universal quantification; and, thirdly, augmented with universal quantification and a stack for memory. We try to relate these respective classes of program schemes to well-known complexity classes and logics.;We study classes of structure on which path system logic coincides with polynomial time P.;We examine the complexity of generalisations of non-uniform boolean constraint satisfaction problems, where the inputs may have a bounded number of quantifier alternations (as opposed to the purely existential quantification of the CSP). We prove, for all bounded-alternation prefixes that have some universal quantifiers to the outside of some existential quantifiers (i.e. 2 and above), that this generalisation of boolean CSP respects the same dichotomy as that for the non-uniform boolean quantified constraint satisfaction problem.;We study the non-uniform QCSP, especially on digraghs, through a combinatorial analog - the alternating-homomorphism problem - that sits in relation to the QCSP exactly as the homomorphism problem sits with the CSP. We establish a trichotomy theorem for the non-uniform QCSP when the template is restricted to antireflexive, undirected graphs with at most one cycle. Specifically, such templates give rise to QCSPs that are either tractable, NP-complete or Pspace-complete.;We study closure properties on templates that respect QCSP hardness or QCSP equality. Our investigation leads us to examine the properties of first-order logic when deprived of the equality relation.;We study the non-uniform QCSP on tournament templates, deriving sufficient conditions for tractablity, NP-completeness and Pspace-completeness. In particular, we prove that those tournament templates that give rise to tractable CSP also give rise to tractable QCSP.Mon, 15 Dec 2014 10:40:12 GMThttp://hdl.handle.net/2381/305302014-12-15T10:40:12ZEmbeddings, fault tolerance and communication strategies in k-ary n-cube interconnection networks
http://hdl.handle.net/2381/30532
Title: Embeddings, fault tolerance and communication strategies in k-ary n-cube interconnection networks
Authors: Ashir, Yaagoub A.
Abstract: The k-ary n-cube interconnection network Qkn, for k 3 and n 2, is n-dimensional network with k processors in each dimension. A k-ary n-cube parallel computer consists of kn identical processors, each provided with its own sizeable memory and interconnected with 2n other processors. The k-ary n-cube has some attractive features like symmetry, high level of concurrency and efficiency, regularity and high potential for the parallel execution of various algorithms. It can efficiently simulate other network topologies. The k-ary n-cube has a smaller degree than that of its equivalent hypercube (the one with at least as many nodes) and it has a smaller diameter than its equivalent mesh of processors.;In this thesis, we review some topological properties of the k-ary n-cube Qkn and show how a Hamiltonian cycle can be embedded in Qkn using the Gray codes strategy. We also completely classify when a Qkn contains a cycle of some given length.;The problem of embedding a large cycle in a Qkn with both faulty nodes and faulty links is considered. We describe a technique for embedding a large cycle in a k-ary n-cube Qkn with at most n faults and show how this result can be extended to obtain embeddings of meshes and tori in such a faulty k-ary n-cube.;Embeddings of Hamiltonian cycles in faulty k-ary n-cubes is also studied. We develop a technique for embedding a Hamiltonian cycle in a k-ary n-cube with at most 4n-5 faulty links where every node is incident with at least two healthy links. Our result is optimal as there exist k-ary n-cubes with 4n - 4 faults (and where every node is incident with at least two healthy links) not containing a Hamiltonian cycle. We show that the same technique can be easily applied to the hypercube. We also show that the general problem of deciding whether a faulty k-ary n-cube contains a Hamiltonian cycle is NP-complete, for all (fixed) k 3.Mon, 15 Dec 2014 10:40:12 GMThttp://hdl.handle.net/2381/305322014-12-15T10:40:12ZOn a construction of young modules
http://hdl.handle.net/2381/30531
Title: On a construction of young modules
Authors: Vernon, Marie
Abstract: Let n be a natural number and E an n-dimensional vector space over a field K. The symmetric group acts by place permutation on the tensor space E âŠ—r. The Sigmar-module EâŠ—r can be decomposed into a direct sum of permutation modules Mlambda where lambda is a composition of r into at most n parts.;Each permutation module labelled by such a composition is isomorphic to one labelled be a partition of r into at most n parts, and therefore we assume that lambda is such a partition. The indecomposable direct summands of the permutation module M lambda are called Young modules, and they are labelled by partitions of r into at most n parts.;Throughout this thesis we consider the case where E has dimension two. For lambda a two-part partition of r, we explicitly decompose the module M lambda into a direct sum of Young modules by providing spanning sets for the Young modules.;Moreover, we consider the problem of finding a basis or an algorithm for a basis for the Young modules in this case and, although we have not been able to solve this in general, we give some conjectures and examples showing in which cases we can find a basis.Mon, 15 Dec 2014 10:40:12 GMThttp://hdl.handle.net/2381/305312014-12-15T10:40:12ZMesh-free radical basis function methods for advection-dominated diffusion problems
http://hdl.handle.net/2381/30529
Title: Mesh-free radical basis function methods for advection-dominated diffusion problems
Authors: Hunt, David Patrick
Abstract: This thesis is concerned with the numerical solution of advection-dominated diffusion problems. There are essentially two key aspects to this work: the derivatives of an a priori error estimate for a semi-Lagrangian mesh-free method using radial basis function interpolation to numerically approximate the first-order linear transport problem; and the design and testing of a semi-Lagrangian mesh-less method to numerically solve the full parabolic advection-diffusion problem, using radial basis function Hermite interpolation. We begin by establishing the theory of radical basis function interpolation, including new results for the stability of interpolation via the class of radial basis functions known as polyharmonic splines, as well as error estimates for interpolation by the same class of function. These results provide us with the necessary tools to prove the a priori error estimate for the semi-Lagrangian advection scheme, given certain assumptions on the smoothness of the solution. We then validate both the scheme and the analysis with a series of numerical experiments. By introducing the concept of Hermite interpolation, we develop and implement a new semi-Lagrangian method for the numerical approximation of advection-dominated diffusion problems, which is validated through two numerical experiments..Mon, 15 Dec 2014 10:40:11 GMThttp://hdl.handle.net/2381/305292014-12-15T10:40:11ZSelf-injective algebras and the second Hochschild cohomology group
http://hdl.handle.net/2381/30528
Title: Self-injective algebras and the second Hochschild cohomology group
Authors: Al-Kadi, Deena
Abstract: In this thesis we study the second Hochschild cohomology group HH 2(Lambda) of a finite dimensional algebra Lambda. In particular, we determine HH2(Lambda) where Lambda is a finite dimensional self-injective algebra of finite representation type over an algebraically closed field K and show that this group is zero for most such Lambda; we give a basis for HH2(Lambda) in the few cases where it is not zero.;Then we consider algebras of tame representation type; more specifically, we study finite dimensional self-injective one parametric tame algebras which are not weakly symmetric. Here we show that HH2(Lambda) is non-zero and find a non-zero element eta in HH2(Lambda) and an associative deformation Lambdaeta of Lambda.Mon, 15 Dec 2014 10:40:11 GMThttp://hdl.handle.net/2381/305282014-12-15T10:40:11ZFiniteness conditions on the Ext-algebra
http://hdl.handle.net/2381/30527
Title: Finiteness conditions on the Ext-algebra
Authors: Davis, Gabriel.
Abstract: Let A be a finite-dimensional algebra given by quiver and monomial relations. In [18] we see that the Ext-algebra of A is finitely generated only if all the Ext-algebras of certain cycle algebras overlying A are finitely generated. Here a cycle algebra Lambda is a finite-dimensional algebra given by quiver and monomial relations where the quiver is an oriented cycle. The main result of this thesis gives necessary and sufficient conditions for the Ext-algebra of such a Lambda to be finitely generated; this is achieved by defining a computable invariant of Lambda, the smo-tube. We also give necessary and sufficient conditions for the Ext-algebra of Lambda to be Noetherian.;Let Lambda be a triangular matrix algebra, defined by algebras T and U and a T-U-bimodule M. Under certain conditions we show that if the Ext-algebras of T and U are right (respectively left) Noetherian rings, then the Ext-algebra of Lambda is a right (respectively left) Noetherian ring. An example shows the hypotheses used cannot be improved. We also specialise to the case where Lambda is a one-point extension: we give a specific presentation of a result that parallels a similar theorem for the more general case above.Mon, 15 Dec 2014 10:40:11 GMThttp://hdl.handle.net/2381/305272014-12-15T10:40:11ZHamilton thermostatting techniques for molecular dynamics simulation
http://hdl.handle.net/2381/30526
Title: Hamilton thermostatting techniques for molecular dynamics simulation
Authors: Sweet, Christopher Richard
Abstract: Molecular dynamics trajectories that sample from a Gibbs, or canonical, distribution can be generated by introducing a modified Hamiltonian with additional degrees of freedom as described by Nose [46]. Although this method has found widespread use in its time re-parameterized Nose-Hoover form, the lack of a Hamiltonian, and the need to 'tune' thermostatting parameters has limited, its use compared to stochastic methods. In addition, since the proof of the correct sampling is based on an ergodic assumption, thermostatting small of stiff systems often does not given the correct distributions unless the Nose-Hoover chains [43] method is used, which inherits the Nose-Hoover deficiencies noted above. More recently the introduction of the Hamiltonian Nose-Poincare method [11], where symplectic integrators can be used for improved long term stability, has renewed interest in the possibility of Hamiltonian methods which can improve dynamical sampling. This class of methods, although applicable to small systems, has applications in large scale systems with complex chemical structure, such as protein-bath and quantum-classical models.;For Nose dynamics, it is often stated that the system is driven to equilibrium through a resonant interaction between the self-oscillation frequency of the thermostat variable and a natural frequency of the underlying system. By the introduction of multiple thermostat Hamiltonian formulations, which are not restricted to chains, it has been possible to clarify this perspective, using harmonic models, and exhibit practical deficiencies of the standard Nose-chain approach. This has led to the introduction of two Hamiltonian schemes, the Nose-Poincare chains method and the Recursive Multiple Thermostat (RMT) method. The RMT method obtains canonical sampling without the stability problems encountered with chains with the advantage that the choice of Nose mass is independent of the underlying system.Mon, 15 Dec 2014 10:40:11 GMThttp://hdl.handle.net/2381/305262014-12-15T10:40:11ZBlocks of fat category O
http://hdl.handle.net/2381/30525
Title: Blocks of fat category O
Authors: Fonseca, Andre
Abstract: We generalize the category O of Bernstein, Gelfand and Gelfand to the so called fat category O, On and derive some of its properties. From a Lie theoretic point of view, contains a significant amount of indecomposable representations that do not belong to O (although it fails to add new simple ones) such as the fat Verma modules. These modules have simple top and socle and may be viewed as standard objects once a block decomposition of is obtained and each block is seen to be equivalent to a category of finite dimensional modules over a finite dimensional standardly stratified algebra. We describe the Ringel dual of these algebras (concluding that principal blocks are self dual) and we obtain the character formulae for their tilting modules. Furthermore, a double centralizer property is proved, relating each block with the corresponding fat algebra of coinvariants. As a byproduct we obtain a classification of all blocks of in terms of their representation type. In the process of determining the quiver and relations which characterize the basic algebras associated to each block of On we prove (for root systems of small rank) a formula establishing the dimension of the Ext1 spaces between simple modules. By borrowing from Soergel some results describing the behaviour of the combinatorial functor V, we are able to compute examples.Mon, 15 Dec 2014 10:40:11 GMThttp://hdl.handle.net/2381/305252014-12-15T10:40:11ZConstraint satisfaction problems and related logic
http://hdl.handle.net/2381/30524
Title: Constraint satisfaction problems and related logic
Authors: Madelaine, Florent
Abstract: Feder and Vardi have proved that the class captured by a monadic fragment of existential second-order logic, MMSNP, is computationally equivalent (via randomised reductions) to the class of constraint satisfaction problems (CSP) while the latter is strictly included in the former. I introduce a new class of combinatorial problems, the so-called forbidden patterns problems (FP), that correspond exactly to the logic MMSNP and introduce some novel algebraic tools like the re-colouring that allow me to construct a normal form. This leads to a constructive characterisation of the borderline of CSP within FP: a given problem in FP is either given as a problem in CSP or we build counter-examples. I relate this result to a recent and independent work by Tardif and Nesetril which relies heavily on a correspondence between duality and density. I generalise this approach to FP. Finally, I investigate homomorphism problems for unary algebras.Mon, 15 Dec 2014 10:40:10 GMThttp://hdl.handle.net/2381/305242014-12-15T10:40:10ZMonads in coalgebra
http://hdl.handle.net/2381/30522
Title: Monads in coalgebra
Authors: Di Marchi, Federico
Abstract: Universal algebra has long been regarded as a fundamental tool in studying semantics of programming languages. Within this paradigm, one can formulate statements regarding the correctness of a program by looking at the interpretations of the code in any model for the language.;While this provides a description of finite computations, other models have to be introduced in order to provide a semantics for recursion and infinite computations in general. This leads to a study of rational and infinite terms. Such terms arise by a dual construction to that of the finite ones. namely, while the latter form an initial algebra, the former are a final coalgebra.;For this reason, it is natural to approach the study of infinite terms by dualising the categorical model of universal algebra. This leads to various different constructions, which are worth of investigation. In this thesis we approach two of them. In one case, we introduce the notions of cosignature, coequation and comodel, in the spirit of the theory of coalgebraic specification. In the second we focus on the properties of monads which can model infinitary computations. Such monads we call guarded, and include, amongst others, the monads of finite terms, infinite terms, rational terms and term graphs. As a byproduct of identifying this notion, we can solve algebraic systems of equation, which are an abstract counterpart to the notion of a recursive program scheme.;Many guarded monads we encounter are obtained by collecting, in an appropriate sense, a suitable family of coagebras. These examples are all instances of a general theorem we present, which tells under which conditions we can define a monad by a colimit operation, and when such comonads are guarded.;The level of abstraction allowed by the use of the categorical formalism allows us to instantiate some of the results in different categories, obtaining a monadic semantics for rational and infinite parallel term rewriting.Mon, 15 Dec 2014 10:40:10 GMThttp://hdl.handle.net/2381/305222014-12-15T10:40:10ZHierarchic modelling of separable elliptic boundary value problems on thin domains
http://hdl.handle.net/2381/30521
Title: Hierarchic modelling of separable elliptic boundary value problems on thin domains
Authors: Arnold, Mark Edward.
Abstract: The dimensional reduction method for solving Laplace's equation on a flat plate, an arch and a spherical shell is investigated, extending previous work on laminated plates by Vogelius and Babuska (1981). Convergence rates for the error in energy are obtained, extending previous results by deriving explicit values for the constant of approximation and its dependence on the thickness of the domain and the model order. The framework for laminated plates is shown to easily extend to other geometries. Numerical results are given which verify the convergence rates in terms of the thickness. Details are given as to how to implement the dimensional reduction technique and in particular, for a spherical shell, a method is given which reduces the problem to that of inverting relatively small matrices.;A posteriori error estimators are given for each of the geometries under consideration. Error estimators are already known for flat plates. It is shown how the estimators for flat plates can be modified for use in the arch case, and for shells, techniques for estimating the discretization error and modelling error are presented. The a posteriori estimators are then used to derive a refinement algorithm for adaptively constructing hierarchic models for representative problems on each of the geometries under consideration.Mon, 15 Dec 2014 10:40:10 GMThttp://hdl.handle.net/2381/305212014-12-15T10:40:10ZNormal and characteristic structure in quasigroups and loops
http://hdl.handle.net/2381/30523
Title: Normal and characteristic structure in quasigroups and loops
Authors: Hardcastle, Tim.
Abstract: In this thesis I shall be exploring the normal and characteristic structure of quasigroups and loops. In recent years there has been a revival of interest in the theory of loops and in particular in the relationship between the properties of a loop and the properties of its multiplication group; and several powerful new theorems have emerged which allow the structural properties of a loop to be related to its multiplication group. I shall combine these ideas with tools developed at the beginning of loop theory to produce some interesting new theorems, principally relating the order of a finite multiplication group to the structure of its loop.Mon, 15 Dec 2014 10:40:10 GMThttp://hdl.handle.net/2381/305232014-12-15T10:40:10ZAlgorithmic problems in mobile computing environments
http://hdl.handle.net/2381/30520
Title: Algorithmic problems in mobile computing environments
Authors: Bruce, Richard James
Abstract: A mobile computer has become a powerful tool. From laptop computers to cellular phones, in the past decade mobile computers have become prevalent in society. In this thesis we shall review and present various algorithms for use with mobile computers; in particular algorithms for mobile ad hoc wireless networks.;Routing problems in ad hoc wireless networks have been one of the most intensely studied areas of research. We shall review various routing algorithms presented by others, verify some of their results, and present our own algorithms for a particular type of routing called fan routing, along with statistical analysis.;The frequency assignment problem has been investigated for many years. We shall investigate two frequency assignment problems for mobile networks. The first uses a limited amount of information to compute an assignment for a host when it is added to a network, where the remainder of the hosts have already been assigned frequencies. We shall present our algorithms and compare them. The second looks at particular graphs, known as outerplanar graphs, and how to use the minimal amount of frequencies for these graphs.;The final area we shall investigate is efficient update strategies for geometric computing with uncertainty. That is, if you know a property of some objects is true; after some time, is this property still true even if the objects have moved? We present a generalised algorithm for verifying any given property and use this generalised algorithm for the maximal points problem.Mon, 15 Dec 2014 10:40:09 GMThttp://hdl.handle.net/2381/305202014-12-15T10:40:09ZContext-sensitive decision problems in groups
http://hdl.handle.net/2381/30517
Title: Context-sensitive decision problems in groups
Authors: Lakin, Steve.
Abstract: The seemingly distinct areas of group theory, formal language theory and complexity theory interact in an important way when one considers decision problems in groups, such as the question of whether a word in the generators of the group represents the identity or not. In general, these problems are known to be undecidable. Much work has been done on the solvability of these problems in certain groups, however less has been done on the resource bounds needed to solve them, in particular with regard to space considerations. The focus of the work presented here is that of groups with (deterministic) context-sensitive decision problems, that is those that have such problems decidable in (deterministic) linear space. A classification of such groups (similarly to the way that the groups with, for example, regular or context-free word problem, have been classified) seems untenable at present. However, we present a series of interesting results with regard to such groups, with the intentions that this will lead to a better understanding of this area. Amongst these results, we emphasise the difficulty of the conjugacy problem by showing that a group may have unsolvable conjugacy problem, even if it has a subgroup of finite index with context-sensitive conjugacy problem. Our main result eliminates the previously-considered possibility that the groups with context-sensitive word problem could be classified as the set of groups which are subgroups of automatic groups, by constructing a group with context-sensitive word problem which is not a subgroup of an automatic group. We also consider a range of other issues in this area, in an attempt to increase the understanding of the sort of groups under consideration.Mon, 15 Dec 2014 10:40:09 GMThttp://hdl.handle.net/2381/305172014-12-15T10:40:09ZThe complexity of greedy algorithms on ordered graphs
http://hdl.handle.net/2381/30518
Title: The complexity of greedy algorithms on ordered graphs
Authors: Puricella, Antonio.
Abstract: Let p be any fixed polynomial time testable, non-trivial, hereditary property of graphs. Suppose that the vertices of a graph G are not necessarily linearly ordered but partially ordered, where we think of this partial order as a collection of (possibly exponentially many) linear orders in the natural way. In the first part of this thesis, we prove that the problem of deciding whether a lexicographically first maximal (with respect to one of these linear orders) subgraph of G satisfying p, contains a specified vertex is NP-complete. For some of these properties p we then show that by applying certain restrictions the problem still remains NP-complete, and show how the problem can be solved in deterministic polynomial time if the restrictions imposed become more severe.;Let H be a fixed undirected graph. An H-colouring of an undirected graph G is a homomorphism from G to H. In the second part of the thesis, we show that, if the vertices of G are partially ordered then the complexity of deciding whether a given vertex of G is in a lexicographically first maximal H-colourable subgraph of G is NP-complete, if H is bipartite, and Sp2-complete, if H is non-bipartite. We then show that if the vertices of G are linearly, as opposed to partially, ordered then the complexity of deciding whether a given vertex of G is in the lexicographically first maximal H-colourable subgraph of G is P-complete, if H is bipartite, and DP2-complete, if H is non-bipartite.;In the final part of the thesis we show that the results obtained can be paralleled in the setting of graphs where orders are given by degrees of the vertices.Mon, 15 Dec 2014 10:40:09 GMThttp://hdl.handle.net/2381/305182014-12-15T10:40:09ZError estimates for spaces arising from approximation by translates of a basic function
http://hdl.handle.net/2381/30519
Title: Error estimates for spaces arising from approximation by translates of a basic function
Authors: Vail, Michelle Louise.
Abstract: We look at aspects of error analysis for interpolation by translates of a basic function. In particular, we consider ideas of localisation and how they can be used to obtain improved error estimates. We shall consider certain seminorms and associated spaces of functions which arise in the study of such interpolation methods. These seminorms are naturally given in an indirect form, that is in terms of the Fourier Transform of the function rather than the function itself. Thus, they do not lend themselves to localisation. However, work by Levesley and Light [17] rewrites these seminorms in a direct form and thus gives a natural way of defining a local seminorm. Using this form of local seminorm we construct associated local spaces. We develop bounded, linear extension operators for these spaces and demonstrate how such extension operators can be used in developing improved error estimates. Specifically, we obtain improved L2 estimates for these spaces in terms of the spacing of the interpolation points. Finally, we begin a discussion of how this approach to localisation compares with alternatives.Mon, 15 Dec 2014 10:40:09 GMThttp://hdl.handle.net/2381/305192014-12-15T10:40:09ZA CSP approach to the analysis of security protocols
http://hdl.handle.net/2381/30516
Title: A CSP approach to the analysis of security protocols
Authors: Hui, Mei Lin.
Abstract: Security protocols involve an exchange of messages in order to achieve a goal such as authentication of a user or secrecy of a session key. Many established protocols have been found to be flawed using protocol analysis techniques. In this thesis we will be extending current CSP-based protocol modelling techniques.;Recent techniques for analyzing security protocols have tended to concentrate upon the small protocols that are typically found in the academic literature. However, there is a huge gulf between these and most large commercial protocols. As a result, existing techniques are difficult to apply directly to these large protocols.;In this thesis we develop the notion of safe simplifying transformations: transformations that have the property of preserving insecurities; the effect of such transformations is that if we can verify the transformed protocol, then we will have verified the original protocol. We identify a number of safe simplifying transformations, and use them in the analysis of two commercial protocols, the CyberCash Main Sequence protocol and SET.;We extend the CSP-based analysis technique to model the property of non-repudiation and give a formal generalized definition. Our definition of non-repudiation is tested against our two case studies.;Another property we model is that of key compromise: the reuse of a compromised session key that might lead to an authentication or secrecy attack. We look at how to model the intruder learning the value of a key and then using it in an attack. We apply this technique to our case studies, looking for key compromise attacks using the session keys.Mon, 15 Dec 2014 10:40:08 GMThttp://hdl.handle.net/2381/305162014-12-15T10:40:08ZFormal languages and the word problem in groups
http://hdl.handle.net/2381/30514
Title: Formal languages and the word problem in groups
Authors: Parkes, Duncan W.
Abstract: For any group G and generating set X we shall be primarily concerned with three sets of words over X: the word problem, the reduced word problem, and the irreducible word problem. We explain the relationships between these three sets of words and give necessary and sufficient conditions for a language to be the word problem (or the reduced word problem) of a group.;We prove that the groups which have context-free reduced word problem with respect to some finite monoid generating set are exactly the context-free groups, thus proving a conjecture of Haring-Smith. We also show that, if a group G has finite irreducible word problem with respect to a monoid generating set X, then the reduced word problem of G with respect to X is simple. In addition, we show that the reduced word problem is recursive (or recursively enumerable) precisely when the word problem is recursive.;The irreducible word problem corresponds to the set of words on the left hand side of a special rewriting system which is confluent on the equivalence class containing the identity. We show that the class of groups which have monoid presentations by means of finite special []-confluent string-rewriting systems strictly contains the class of plain groups (the groups which are free products of a finitely generated free group and finitely many finite groups), and that any group which has an infinite cyclic central subgroup can be presented by such a string-rewriting system if and only if it is the direct product of an infinite cyclic group and a finite cyclic group.Mon, 15 Dec 2014 10:40:08 GMThttp://hdl.handle.net/2381/305142014-12-15T10:40:08ZPerturbations of black holes in Einstein-Cartan theory
http://hdl.handle.net/2381/30515
Title: Perturbations of black holes in Einstein-Cartan theory
Authors: White, Andrew.
Abstract: Torsion is a property of space-time which is not incorporated into the standard formulation of general relativity but which appears as a consequence of unification schemes for fundamental forces. It is, therefore, important to understand its physical consequence. This thesis begins with an introduction to a non-propagating version of torsion theory as an extension to general relativity. The theory can be described in terms of a pair coupled field equations with torsion algebraically linked to elementary particle spin. In order to develop the theory it is necessary to postulate a form for the energy-momentum tensor of spinning matter which is not prescribed in the classical domain. The two main candidates that have been proposed for a spinning fluid are considered. Chapter two contains an independent reworking of Zerilli's [1] perturbation calculation of a particle falling into a Schwarzschild black hole. The perturbation equations are found and the resulting wave equations are derived. The special case of a particle falling radially is considered in detail. Chapter three contains new work which employs the method of Zerilli in torsion theory to consider a particle with spin falling radially into a black hole. The changes to the black hole are found for each of the two energy-momentum tensors of Chapter one. This enables us to discount one of these as unphysical. The differential equations describing the gravitational radiation released by this system are derived. Finally in Chapter four these equations are solved to find the gravitational radiation from a spinning particle falling radially. These may be significant for observational assessments of torsion theory.Mon, 15 Dec 2014 10:40:08 GMThttp://hdl.handle.net/2381/305152014-12-15T10:40:08ZApproximation by tranlates of a radial basis function
http://hdl.handle.net/2381/30513
Title: Approximation by tranlates of a radial basis function
Authors: Hales, Stephen.
Abstract: The aim of this work is to investigate the properties of approximations obtained by translates of radial basis functions. A natural progression in the discussion starts with an iterative refinement scheme using a strictly positive definite inverse multiquadric. Error estimates for this method are greatly simplified if the inverse multiquadric is replaced by a strictly conditionally positive definite polyharmonic spline. Such error analysis is conducted in a native space generated by the Fourier transform of the basis function. This space can be restrictive when using very smooth basis functions. Some instances are discussed where the native space of can be enlarged by creating a strictly positive definite basis function with comparable approximating properties to , but with a significantly different Fourier transform to . Before such a construction is possible however, strictly positive definite functions in d for d < with compact support must be examined in some detail. It is demonstrated that the dimension in which a function is positive definite can be determined from its univariate Fourier transform.;This work is biased towards the computational aspects of interpolation, and the theory is always given with a view to explaining observable phenomena.Mon, 15 Dec 2014 10:40:08 GMThttp://hdl.handle.net/2381/305132014-12-15T10:40:08ZExpressibility and tractability
http://hdl.handle.net/2381/30512
Title: Expressibility and tractability
Authors: Gault, Richard.
Abstract: This thesis is composed of three separate, yet related strands. They have in common the notion that computational problems are regarded not as sets of strings, but as classes of finite structures. Our "computing devices", be they of a logical, traditionally computational, or algebraic nature, all work directly upon such structures. This is in contrast to traditional computability and complexity theory, where machines act instead upon some encoding of structures.;We begin by investigating a restriction of the question of whether or not NP = co-NP. In particular, we consider the effect of adding a transitive closure operator to monadic NP, and show that the resulting logic is a strict extension of it which is not closed under complementation. This extends Fagin's result that monadic NP is itself not closed under complementation.;We then investigate the expressive power of a class of program schemes which we call RFDPS. We prove a strong result limiting the expressive power of this class, and use it to obtain a strict, infinite hierarchy of problem classes within RFDPS. To our knowledge, this is the first strict, infinite hierarchy in a polynomial-time logic which properly extends inductive fixed-point logic (with the property that the union of the classes of the hierarchy consists of the class of problems definable in the polynomial-time logic itself).;Finally, we turn our attention to constraint satisfaction problems. This important class of problems is NP-hard in general, but many restrictions to it have been identified over the years which ensure its tractability. We introduce a method of combining two tractable classes over disjoint domains, so as to synthesise new tractable classes. We demonstrate that these new classes are genuinely novel, and extend naturally to yet further tractable classes. The algorithms for solving these extended classes can be less than obvious.Mon, 15 Dec 2014 10:40:07 GMThttp://hdl.handle.net/2381/305122014-12-15T10:40:07ZMixed hp - finite element methods for viscous incompressible fluid flow
http://hdl.handle.net/2381/30511
Title: Mixed hp - finite element methods for viscous incompressible fluid flow
Authors: Coggins, Patrick.
Abstract: The efficient numerical approximation of viscous, incompressible flow by families of mixed finite elements is subject to the satisfaction of a stability or inf-sup condition between the velocity and pressure approximation spaces.;The present work analyses the stability of mixed hp-finite elements for planar Stokes flow on affine quadrilateral meshes comprising of regular and anisotropic elements. Firstly, a new family of mixed hp-finite elements is presented for regular elements with an inf-sup constant bounded below independently of the mesh size h and the spectral order p. In particular, the element allows continuous piecewise polynomial pressures to be used.;Next, the stability of families of mixed hp-finite elements on geometrically refined anisotropic elements is considered using a macro-element technique. New results are presented for edge and corner macro-elements, in particular, for the latter case, the dependence of the inf-sup constant on the geometric refinement parameter is explicitly characterised.;The families are then used in the numerical approximation of two physical Navier-Stokes problems.Mon, 15 Dec 2014 10:40:07 GMThttp://hdl.handle.net/2381/305112014-12-15T10:40:07ZThe p- and hp- finite element method applied to a class of non-linear elliptic partial differential equations
http://hdl.handle.net/2381/30510
Title: The p- and hp- finite element method applied to a class of non-linear elliptic partial differential equations
Authors: Kay, David.
Abstract: The analysis of the p- and hp-versions of the finite element methods has been studied in much detail for the Hilbert spaces W1,2 (omega). The following work extends the previous approximation theory to that of general Sobolev spaces W1,q(Q), q 1, oo . This extension is essential when considering the use of the p and hp methods to the non-linear a-Laplacian problem. Firstly, approximation theoretic results are obtained for approximation using continuous piecewise polynomials of degree p on meshes of triangular and quadrilateral elements. Estimates for the rate of convergence in Sobolev spaces W1,q(Q) are given. This analysis shows that the traditional view of avoiding the use of high order polynomial finite element methods is incorrect, and that the rate of convergence of the p version is always at least that of the h version (measured in terms of number of degrees of freedom). It is also shown that, if the solution has certain types of singularity, the rate of convergence of the p version is twice that of the h version. Numerical results are given, confirming the results given by the approximation theory. The p-version approximation theory is then used to obtain the hp approximation theory. The results obtained allow both non-uniform p refinements to be used, and the h refinements only have to be locally quasiuniform. It is then shown that even when the solution has singularities, exponential rates of convergence can be achieved when using the /ip-version, which would not be possible for the h- and p-versions.Mon, 15 Dec 2014 10:40:06 GMThttp://hdl.handle.net/2381/305102014-12-15T10:40:06ZAsymptotic state and parameter observation for dynamical systems with nonlinear parameterisation
http://hdl.handle.net/2381/29323
Title: Asymptotic state and parameter observation for dynamical systems with nonlinear parameterisation
Authors: Cole, David Richard Fairhurst
Abstract: We consider the problem of asymptotic reconstruction of state and parameter values
in dynamical systems that cannot be transformed into a canonical adaptive observer
form. A solution to this problem is proposed for certain classes of systems for which
parameters enter the model nonlinearly. In addition to asymptotic Lyapunov stability,
we provide for these classes, a reconstruction technique based on the notions
of weakly attracting sets and nonuniform convergence.Mon, 08 Dec 2014 11:10:31 GMThttp://hdl.handle.net/2381/293232014-12-08T11:10:31ZFinite Generation of Ext and (D,A)-stacked Algebras
http://hdl.handle.net/2381/29029
Title: Finite Generation of Ext and (D,A)-stacked Algebras
Authors: Leader, Joanne
Abstract: We introduce the class of (D,A)-stacked algebras, which generalise the
classes of Koszul algebras, d-Koszul algebras and (D,A)-stacked monomial algebras.
We show that the Ext algebra of a (D,A)-stacked algebra is finitely generated in
degrees 0, 1, 2 and 3. After investigating some general properties of E(Ʌ) for this class
of algebras, we look at a regrading of E(Ʌ) and give examples for which the regraded
Ext algebra is a Koszul algebra. Following this we give a general construction of a
(D,A)-stacked algebra ~Ʌ from a d-Koszul algebra Ʌ, setting D = dA, with A ≥ 1.
From this construction we relate the homological properties of ~Ʌ and Ʌ, including
the projective resolutions and the structure of the Ext algebra.Fri, 08 Aug 2014 13:59:03 GMThttp://hdl.handle.net/2381/290292014-08-08T13:59:03ZPattern-equivariant homology of finite local complexity patterns
http://hdl.handle.net/2381/28923
Title: Pattern-equivariant homology of finite local complexity patterns
Authors: Walton, James Jonathan
Abstract: This thesis establishes a generalised setting with which to unify the study of
finite local complexity (FLC) patterns. The abstract notion of a pattern is introduced,
which may be seen as an analogue of the space group of isometries preserving
a tiling but where, instead, one considers partial isometries preserving
portions of it. These inverse semigroups of partial transformations are the suitable
analogue of the space group for patterns with FLC but few global symmetries.
In a similar vein we introduce the notion of a collage, a system of equivalence
relations on the ambient space of a pattern, which we show is capable of generalising
many constructions applicable to the study of FLC tilings and Delone sets,
such as the expression of the tiling space as an inverse limit of approximants.
An invariant is constructed for our abstract patterns, the so called patternequivariant
(PE) homology. These homology groups are defined using infinite singular
chains on the ambient space of the pattern, although we show that one may
define cellular versions which are isomorphic under suitable conditions. For FLC
tilings these cellular PE chains are analogous to the PE cellular cochains [47]. The
PE homology and cohomology groups are shown to be related through Poincare
duality.
An efficient and highly geometric method for the computation of the PE homology
groups for hierarchical tilings is presented. The rotationally invariant
PE homology groups are shown not to be a topological invariant for the associated
tiling space and seem to retain extra information about global symmetries
of tilings in the tiling space. We show how the PE homology groups may be incorporated
into a spectral sequence converging to the Cech cohomology of the
rigid hull of a tiling. These methods allow for a simple computation of the Cech
cohomology of the rigid hull of the Penrose tilings.Mon, 16 Jun 2014 15:26:59 GMThttp://hdl.handle.net/2381/289232014-06-16T15:26:59ZOn the prescribed mean curvature problem on the standard n-dimensional ball
http://hdl.handle.net/2381/28493
Title: On the prescribed mean curvature problem on the standard n-dimensional ball
Authors: Sharaf, Khadijah Abdullah Mohammed
Abstract: In this thesis, we consider the problem of existence of conformal scalar flat metric with prescribed boundary mean curvature on the standard n-dimensional ball. Let B[superscript n] be the unit ball in R[superscript n], n ≥ 3, with Euclidean metric g[subscript 0]. Its boundary will be denoted by S[superscript n-1] and will be endowed with the standard metric still denoted by g[subscript 0]. Let H : S[superscript n-1] → R be a given function, we study the problem of finding a conformal metric g = u 4/n-2 g[subscript 0] such that R[subscript g] = 0 in B[superscript n] and h[subscript g] = H on S[superscript n-1]. Here R[subscript g] is the scalar curvature of the metric g in B[superscript n] and h[subscript g] is the mean curvature of g on S[superscript n-1]. This problem is equivalent to solving the following nonlinear boundary value equation: (see PDF for equation) where v is the outward unit vector with respect to the metric g[subscript 0]. In general there are several difficulties in facing this problem by means of variational methods. Indeed, in virtue of the non-compactness of the embedding H[superscript 1](B[superscript n]) → L 2(n-1)/n-2 (∂B[superscript n]), the Euler-Lagrange functional J associated to the problem, does not satisfy the Palais-Smale condition, and that leads to the failure of the standard critical point theory.
One part of this thesis deals with the case where H is a Morse function satisfying a non degeneracy condition. Using an algebraic topological method and the tools of the theory of the critical points at infinity, we provide a variety of classes of functions that can be realized as the mean curvature on the boundary of the the n-dimensional balls.
The other part deals with the case where the non degeneracy condition is not satisfied and replaced by the so called β-flatness condition. In this case, we give precise estimates on the losses of the compactness and we identify the critical points at infinity of the variational problem. Then, we establish under generic boundary condition a Morse inequalities at infinity, which give a lower bound on the number of solutions to the above problem.Fri, 06 Dec 2013 13:36:38 GMThttp://hdl.handle.net/2381/284932013-12-06T13:36:38ZThe effects of axial flow and surface mass-flux on the stability of the rotating-sphere boundary layer
http://hdl.handle.net/2381/28456
Title: The effects of axial flow and surface mass-flux on the stability of the rotating-sphere boundary layer
Authors: Barrow, Alistair
Abstract: A theoretical investigation is carried out into the linear stability of the boundary-layer flow around a rotating sphere immersed in an incompressible viscous fluid. Two potentially stabilising mechanisms are considered: a forced uniform axial flow in the surrounding fluid, and the introduction of mass suction/injection through the surface of the sphere. The investigation is broadly split into a “local” analysis, where a parallel-flow assumption is made which limits the study to individual latitudinal positions; and a “global” analysis, where the entire streamwise extent of the flow is considered. In the local analysis, both stationary and travelling convective disturbances are considered. For a representative subset of the parameter space, critical Reynolds numbers are presented for the predicted onset of convective and absolute instabilities. Axial flow and surface suction are typically found to postpone the onset of all types of instability by raising the critical Reynolds number, whereas surface injection has the opposite effect. This is further demonstrated by a consideration of the convective and absolute growth rates at various parameter values.
The results of the global analysis suggest that the rotating sphere can support a self-sustained, linearly globally-unstable global mode for sufficiently large rotation rates. This is in contrast to the case of the rotating disk, where it is generally accepted that self-sustained linear global modes do not occur.Wed, 27 Nov 2013 09:39:53 GMThttp://hdl.handle.net/2381/284562013-11-27T09:39:53ZApproximation on the complex sphere
http://hdl.handle.net/2381/28368
Title: Approximation on the complex sphere
Authors: Alsaud, Huda Saleh
Abstract: The aim of this thesis is to study approximation of multivariate functions on the complex sphere by spherical harmonic polynomials. Spherical harmonics arise naturally in many theoretical and practical applications. We consider different aspects of the approximation by spherical harmonic which play an important role in a wide range of topics. We study approximation on the spheres by spherical polynomials from the geometric point of view. In particular, we study and develop a generating function of Jacobi polynomials and its special cases which are of geometric nature and give a new representation for the left hand side of a well-known formulae for generating functions for Jacobi polynomials (of integer indices) in terms of associated Legendre functions. This representation arises as a consequence of the interpretation of projective spaces as quotient spaces of complex spheres. In addition, we develop new elements of harmonic analysis on the complex sphere, and use these to establish Jackson's and Kolmogorov's inequalities. We apply these results to get order sharp estimates for m-term approximation. The results obtained are a synthesis of new results on classical orthogonal polynomials geometric properties of Euclidean spaces. As another aspect of approximation, we consider interpolation by radial basis functions. In particular, we study interpolation on the spheres and its error estimate. We show that the improved error of convergence in n dimensional real sphere, given in [7], remain true in the case of the complex sphere.Fri, 08 Nov 2013 12:38:44 GMThttp://hdl.handle.net/2381/283682013-11-08T12:38:44ZSolid-Liquid Interfacial Properties of Fe and Fe-C Alloys from Molecular Dynamics Simulations
http://hdl.handle.net/2381/28269
Title: Solid-Liquid Interfacial Properties of Fe and Fe-C Alloys from Molecular Dynamics Simulations
Authors: Melnykov, Mykhailo
Abstract: This project is devoted to the study of solid-liquid interfaces in pure Fe and Fe-C alloys using molecular simulation. It consists of three parts: first, we use the coexisting phases approach to calculate melting phase diagrams of several recent Fe-C interaction potentials, such as Embedded Atom Method (EAM) potential of Lau et al., EAM potential of Hepburn and Ackland, and Analytic Bond Order (ABOP) potential of Henriksson and Nordlund. Melting of both bcc (ferrite) and fcc (austenite) crystal structures is investigated with C concentrations up to 5 wt%. The results are compared with the experimental data and suggest that the potential of Hepburn and Ackland is the most accurate in reproducing the melting phase diagram of the ferrite but the austenite cannot be stabilised at any C concentration for this potential.
The potential of Lau et al. yields the best qualitative agreement with the real phase diagram in that the ferrite-liquid coexistence at low C concentrations is replaced by the austenite-liquid coexistence at higher C concentrations. However, the crossover C concentration is much larger and the ferrite melting temperature is much higher than in the real Fe-C alloy. The ABOP potential of Henriksson and Nordlund correctly predicts the relative stability of ferrite and austenite at melting, but significantly underestimates the solubility of C in the solid phases.
Second, we develop a new direct method for calculating the solid-liquid interfacial free energy using deformation of the solid-liquid coexistence system.
The deformation is designed to change the area of the interface, while preserving the volume of the system and crystal structure of the solid phase. The interfacial free energy is calculated as the deformation work divided by the change of the interfacial area. The method is applied to the bcc solid-liquid interface of pure Fe described by the Hepburn and Ackland potential. The obtained results are somewhat different from those calculated by the established methods so further development and analysis are required.
Third, we investigate the dependence on C concentration of the bcc solid-liquid interfacial free energy of Fe-C alloy described by the Hepburn and Ackland potential. We use the method proposed by Frolov and Mishin which is analogous to the Gibbs-Duhem integration along the solid-liquid coexistence line. The calculations are performed for three different crystal orientations (100), (110) and (111), allowing us to determine the anisotropy of the interfacial free energy and its dependence on C concentration along the coexistence line. Although the precision is somewhat limited by the high computational cost of such calculations.Tue, 08 Oct 2013 15:00:03 GMThttp://hdl.handle.net/2381/282692013-10-08T15:00:03ZA Classification of Toral and Planar Attractors and Substitution Tiling Spaces
http://hdl.handle.net/2381/28227
Title: A Classification of Toral and Planar Attractors and Substitution Tiling Spaces
Authors: McCann, Sheila Margaret
Abstract: We focus on dynamical systems which are one-dimensional expanding
attractors with a local product structure of an arc times a Cantor set. We
define a class of Denjoy continua and show that each one of the class is homeomorphic to an orientable DA attractor with four complementary domains which in turn is homeomorphic to a tiling space consisting of aperiodic substitution tilings. The planar attractors are non-orientable as is the Plykin attractor in the 2-sphere which we describe.
We classify these attractors and tiling spaces up to homeomorphism and the
symmetries of the underlying spaces up to isomorphism. The criterion for
homeomorphism is the irrational slope of the expanding eigenvector of the
defining matrix from whence the attractor was formed whilst the criterion for
isomorphism is the matrix itself. We find that the permutation groups arising
from the 4 'special points' which serve as the repelling set of an attractor are isomorphic to subgroups of S[subscript 4]. Restricted to these 4 special points, we show that the isotopy class group of the self-homeomorphisms of an attractor, and likewise those of a tiling space, is isomorphic to Z ⊕ Z[subscript 2].Thu, 26 Sep 2013 09:27:20 GMThttp://hdl.handle.net/2381/282272013-09-26T09:27:20ZThe Stability and Transition of the Compressible Boundary-Layer Flow over Broad Rotating Cones
http://hdl.handle.net/2381/28219
Title: The Stability and Transition of the Compressible Boundary-Layer Flow over Broad Rotating Cones
Authors: Towers, Paul David
Abstract: The subject of fluid flows over axisymmetric bodies has increased in recent
times, as they can be used to model flows over a swept wing, spinning projectiles and aeroengines amongst other things. A better mathematical understanding of the transition from laminar to turbulent flow within the boundary layer could lead to an improvement in the design of such applications.
We consider a compressible fluid flow over a rotating cone, defined by half-angle ψ. The mean flow boundary-layer equations are derived and we conduct a high Reynolds number asymptotic linear stability analysis. The flow is susceptible to instabilities caused by inviscid crossflow modes (type I ) and modes caused by a viscous-Coriolis balance force (type II ). Both are considered, along with the effects of changes in the cone half-angle, the magnitude of the local Mach number and the temperature at the cone wall. A surface suction along the cone wall is also analysed.Wed, 25 Sep 2013 15:03:47 GMThttp://hdl.handle.net/2381/282192013-09-25T15:03:47ZAdaptive Radial Basis Function Interpolation for Time-Dependent Partial Differential Equations
http://hdl.handle.net/2381/28184
Title: Adaptive Radial Basis Function Interpolation for Time-Dependent Partial Differential Equations
Authors: Naqvi, Syeda Laila
Abstract: In this thesis we have proposed the meshless adaptive method by radial basis functions (RBFs) for the solution of the time-dependent partial differential equations (PDEs) where the approximate solution is obtained by the multiquadrics (MQ) and the local scattered data reconstruction has been done by polyharmonic splines. We choose MQ because of its exponential convergence for sufficiently smooth functions. The solution of partial differential equations arising in science and engineering, frequently have large variations occurring over small portion of the physical domain, the challenge then is to resolve the solution behaviour there. For the sake of efficiency we require a finer grid in those parts of the physical domain whereas a much coarser grid can be used otherwise.
During our journey, we come up with different ideas and have found many interesting results but the main motivation for the one-dimensional case was the Korteweg-de Vries (KdV) equation rather than the common test problems. The KdV equation is a nonlinear hyperbolic equation with smooth solutions at all times. Furthermore the methods available in the literature for solving this problem are rather fully implicit or limited literature can be found using explicit and semi-explicit methods. Our approach is to adaptively select the nodes, using the radial basis function interpolation.
We aimed in, the extension of our method in solving two-dimensional partial differential equations, however to get an insight of the method we developed the algorithms for one-dimensional PDEs and two-dimensional interpolation problem. The experiments show that the method is able to track the developing features of the profile of the solution. Furthermore this work is based on computations and not on proofs.Fri, 13 Sep 2013 09:46:03 GMThttp://hdl.handle.net/2381/281842013-09-13T09:46:03Z