LRA Community:
http://hdl.handle.net/2381/445
20150227T13:11:44Z

Minimum Distance Estimation of Milky Way Model Parameters and Related Inference
http://hdl.handle.net/2381/31616
Title: Minimum Distance Estimation of Milky Way Model Parameters and Related Inference
Authors: Banerjee, S.; Bhattacharya, S.; Basu, A.; Bose, S.; Chakrabarty, Dalia; Mukherjee, S.
Abstract: We propose a method to estimate the location of the Sun in the disk of the Milky Way using a
method based on the Hellinger distance and construct confidence sets on our estimate of the unknown
location using a bootstrap based method. Assuming the Galactic disk to be twodimensional, the
sought solar location then reduces to the radial distance separating the Sun from the Galactic center
and the angular separation of the Galactic center to Sun line, from a prefixed line on the disk. On
astronomical scales, the unknown solar location is equivalent to the location of us earthlings who
observe the velocities of a sample of stars in the neighborhood of the Sun. This unknown location
is estimated by undertaking pairwise comparisons of the estimated density of the observed set of
velocities of the sampled stars, with the density estimated using synthetic stellar velocity data
sets generated at chosen locations in the Milky Way disk. The synthetic data sets are generated
at a number of locations that we choose from within a constructed grid, at four different base
astrophysical models of the Galaxy. Thus, we work with one observed stellar velocity data and
four distinct sets of simulated data comprising a number of synthetic velocity data vectors, each
generated at a chosen location. For a given base astrophysical model that gives rise to one such
simulated data set, the chosen location within our constructed grid at which the estimated density of
the generated synthetic data best matches the density of the observed data, is used as an estimate
for the location at which the observed data was realized. In other words, the chosen location
corresponding to the highest match offers an estimate of the solar coordinates in the Milky Way
disk. The “match” between the pair of estimated densities is parameterized by the affinity measure
based on the familiar Hellinger distance. We perform a novel crossvalidation procedure to establish
a desirable “consistency” property of the proposed method.
20150205T14:31:58Z

Inverse Bayesian Estimation of Gravitational Mass Density in Galaxies from Missing Kinematic Data
http://hdl.handle.net/2381/31604
Title: Inverse Bayesian Estimation of Gravitational Mass Density in Galaxies from Missing Kinematic Data
Authors: Chakrabarty, Dalia; Saha, P.
Abstract: In this paper, we focus on a type of inverse problem in which the data are expressed as an unknown function of
the sought and unknown model function (or its discretised representation as a model parameter vector). In particular,
we deal with situations in which training data are not available. Then we cannot model the unknown
functional relationship between data and the unknown model function (or parameter vector) with a Gaussian
Process of appropriate dimensionality. A Bayesian method based on state space modelling is advanced instead.
Within this framework, the likelihood is expressed in terms of the probability density function (pdf) of the state
space variable and the sought model parameter vector is embedded within the domain of this pdf. As the measurable
vector lives only inside an identified subvolume of the system state space, the pdf of the state space variable
is projected onto the space of the measurables, and it is in terms of the projected state space density that the
likelihood is written; the final form of the likelihood is achieved after convolution with the distribution of measurement
errors. Application motivated vague priors are invoked and the posterior probability density of the
model parameter vectors, given the data are computed. Inference is performed by taking posterior samples with
adaptive MCMC. The method is illustrated on synthetic as well as real galactic data.
20150204T17:07:47Z

Bayesian Density Estimation via Multiple Sequential Inversions of 2D Images with Application in Electron Microscopy
http://hdl.handle.net/2381/31575
Title: Bayesian Density Estimation via Multiple Sequential Inversions of 2D Images with Application in Electron Microscopy
Authors: Chakrabarty, Dalia; Rigat, F.; Gabrielyan, N.; Beanland, R.; Paul, S.
Abstract: We present a new Bayesian methodology to learn the unknown material density of
a given sample by inverting its twodimensional images that are taken with a Scanning Electron
Microscope. An image results from a sequence of projections of the convolution of the density
function with the unknown microscopy correction function that we also learn from the data;
thus learning of the unknowns demands multiple inversions. We invoke a novel design of experiment,
involving imaging at multiple values of the parameter that controls the subsurface
depth from which information about the density structure is carried, to result in the image.
Reallife material density functions are characterized by high density contrasts and are highly
discontinuous, implying that they exhibit correlation structures that do not vary smoothly. In
the absence of training data, modeling such correlation structures of real material density functions
is not possible. So we discretize the material sample and treat values of the density function
at chosen locations inside it as independent and distributionfree parameters. Resolution
of the available image dictates the discretization length of the model; three models pertaining
to distinct resolution classes (at μm to nano metre scale lengths) are developed. We develop
priors on the material density, such that these priors adapt to the sparsity inherent in the density
function. The likelihood is defined in terms of the distance between the convolution of the unknown
functions and the image data. The posterior probability density of the unknowns given
the data is expressed using the developed priors on the density and priors on the microscopy
correction function as elicited from the Microscopy literature. We achieve posterior samples
using an adaptive MetropoliswithinGibbs inference scheme. The method is applied to learn
the material density of a 3D sample of a nanostructure, using real image data. Illustrations on
simulated image data of alloy samples are also included
20150204T10:02:57Z

Bayesian Learning of Material Density Function by Multiple Sequential Inversions of 2D Images in Electron Microscopy
http://hdl.handle.net/2381/31574
Title: Bayesian Learning of Material Density Function by Multiple Sequential Inversions of 2D Images in Electron Microscopy
Authors: Chakrabarty, Dalia; Paul, S.
Editors: Polpo de Campos, A; Neto,; Ramos Rifo,; Stern,; Lauretto,
Abstract: We discuss a novel inverse problem in which the data is generated by the sequential contractive projections
of the convolution of two unknown functions, both of which we aim to learn. The method is illustrated
using an application that relates to the multiple inversions of image data recorded with a Scanning Electron
Microscope, with the aim of learning the density of a given material sample and the microscopy correction
function. Given the severe logistical difficulties in this application of taking multiple images at different
viewing angles, a novel imaging experiment is undertaken, resulting in expansion of information. In lieu of
training data, it is noted that the highly discontinuous material density function cannot be modelled using a
Gaussian Process (GP) as the parametrisation of the required nonstationary covariance function of such a
GP cannot be achieved without training data. Consequently, we resort to estimating values of the unknown
functions at chosen locations in their domain–locations at which an image data are available. Image data
across a range of resolutions leads to multiscale models which we use to estimate material densities from the
micrometre to nanometre length scales. We discuss applications of the method in nondestructive learning
of material density using simulated metallurgical image data, as well as perform inhomogeneity detection in
multicomponent composite on nano metre scales, by inverting real image data of a brick of nanoparticles.
20150204T09:51:38Z

Simple Locally Finite Lie Algebras of Diagonal Type
http://hdl.handle.net/2381/31502
Title: Simple Locally Finite Lie Algebras of Diagonal Type
Authors: Baranov, Alexander
Abstract: We discuss various characterizations of simple locally finite Lie algebras of diagonal type over an algebraically closed field of characteristic zero.
20150127T14:38:49Z

On time scale invariance of random walks in confined space.
http://hdl.handle.net/2381/31448
Title: On time scale invariance of random walks in confined space.
Authors: Bearup, Daniel; Petrovskii, Sergei
Abstract: Animal movement is often modelled on an individual level using simulated random walks. In such applications it is preferable that the properties of these random walks remain consistent when the choice of time is changed (time scale invariance). While this property is well understood in unbounded space, it has not been studied in detail for random walks in a confined domain. In this work we undertake an investigation of time scale invariance of the drift and diffusion rates of Brownian random walks subject to one of four simple boundary conditions. We find that time scale invariance is lost when the boundary condition is nonconservative, that is when movement (or individuals) is discarded due to boundary encounters. Where possible analytical results are used to describe the limits of the time scaling process, numerical results are then used to characterise the intermediate behaviour.
20150120T14:49:30Z

Modelling 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 everincreasing 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 reactiondiffusion framework we test the two models (preypredator and
susceptibleinfected) 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.
20150108T12:53:35Z

Special functions and generalized functions
http://hdl.handle.net/2381/30544
Title: Special functions and generalized functions
Authors: AlSirehy, 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 xlr+ . Moreover, other results are obtained concerning the neutrix product of xlambdar lnp x and sgn x xlambdar. Other theorems are proved about the matrix product of some other distributions such as xl+ ln x+ and xlr .;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.
20141215T10:40:16Z

On finite groups of plocal rank one and a conjecture of Robinson
http://hdl.handle.net/2381/30542
Title: On finite groups of plocal 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 psubgroups. Groups of this type are said to have plocal 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.;.
20141215T10:40:15Z

Ancient 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..
20141215T10:40:15Z

Data 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 nirregular 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.
20141215T10:40:15Z

A 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 SturmLiouville 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 highindex eigenvalues of general SturmLiouville problems.
20141215T10:40:15Z

Multivariate 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 ddimensional Euclidean space Hd and the unit sphere 5d_1, where the data is generated not only by pointevaluations, but also by the derivatives, or differential/pseudodifferential operators. Some sufficient and necessary conditions for the wellposedness 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.
20141215T10:40:14Z

On indecomposable modules over clustertilted algebras of type A
http://hdl.handle.net/2381/30538
Title: On indecomposable modules over clustertilted 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 simplylaced 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 clustertilted algebra of Dynkin type A.;It is known that the quiver of a clustertilted 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 quasiCartan companion of the corresponding exchange matrix.;Our main result establishes that the dimension vectors of the finitely generated indecomposable modules over a clustertilted 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 clustertilted algebras of Dynkin type A have a particularly nice description in terms of triangulation of regular polygons.
20141215T10:40:14Z

Anisotropic 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 hpadaptation strategies for discontinuous Galerkin interior penalty methods for secondorder 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 highorder) 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 goaloriented setting.;Based on our a posteriori error bound we first design and implement an adaptive anisotropic hrefinement 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 hisotropic mesh refinement algorithm and a Hessian based hanisotropic 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 hpisotropic refinement algorithm and an hanisotropic/pisotropic adaptive procedure.
20141215T10:40:14Z

On 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 subalgebra 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.
20141215T10:40:14Z

Euler 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 ddimensional codimension n polytopal projection pattern with d > n..
20141215T10:40:13Z

Efficient 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. 61726175] which combines the set of stabilising transformations proposed by Schmelcher and Diakonos [Phys. Rev. Lett., 78 (1997), pp. 47334736] with a modified semiimplicit Euler iterative scheme and seeding with periodic orbits of neighbouring periods, has been shown to be highly efficient when applied to lowdimensional 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 highdimensional 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 highdimensional systems. Another important aspect of our treatment of highdimensional 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 highdimensional phase space is a challenging problem in itself. The performance of the new approach is illustrated by its application to the fourdimensional kicked double rotor map, a sixdimensional system of three coupled Henon maps and to the KuramotoSivashinsky system in the weakly turbulent regime.
20141215T10:40:13Z

Uncertainty 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.
20141215T10:40:13Z

Embeddings, fault tolerance and communication strategies in kary ncube interconnection networks
http://hdl.handle.net/2381/30532
Title: Embeddings, fault tolerance and communication strategies in kary ncube interconnection networks
Authors: Ashir, Yaagoub A.
Abstract: The kary ncube interconnection network Qkn, for k 3 and n 2, is ndimensional network with k processors in each dimension. A kary ncube parallel computer consists of kn identical processors, each provided with its own sizeable memory and interconnected with 2n other processors. The kary ncube 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 kary ncube 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 kary ncube 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 kary ncube 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 kary ncube.;Embeddings of Hamiltonian cycles in faulty kary ncubes is also studied. We develop a technique for embedding a Hamiltonian cycle in a kary ncube with at most 4n5 faulty links where every node is incident with at least two healthy links. Our result is optimal as there exist kary ncubes 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 kary ncube contains a Hamiltonian cycle is NPcomplete, for all (fixed) k 3.
20141215T10:40:12Z

Logic, 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 nondeterministic 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 wellknown 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 nonuniform 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 boundedalternation 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 nonuniform boolean quantified constraint satisfaction problem.;We study the nonuniform QCSP, especially on digraghs, through a combinatorial analog  the alternatinghomomorphism problem  that sits in relation to the QCSP exactly as the homomorphism problem sits with the CSP. We establish a trichotomy theorem for the nonuniform 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, NPcomplete or Pspacecomplete.;We study closure properties on templates that respect QCSP hardness or QCSP equality. Our investigation leads us to examine the properties of firstorder logic when deprived of the equality relation.;We study the nonuniform QCSP on tournament templates, deriving sufficient conditions for tractablity, NPcompleteness and Pspacecompleteness. In particular, we prove that those tournament templates that give rise to tractable CSP also give rise to tractable QCSP.
20141215T10:40:12Z

On 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 ndimensional vector space over a field K. The symmetric group acts by place permutation on the tensor space E âŠ—r. The Sigmarmodule 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 twopart 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.
20141215T10:40:12Z

Hamilton 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 reparameterized NoseHoover 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 NoseHoover chains [43] method is used, which inherits the NoseHoover deficiencies noted above. More recently the introduction of the Hamiltonian NosePoincare 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 proteinbath and quantumclassical models.;For Nose dynamics, it is often stated that the system is driven to equilibrium through a resonant interaction between the selfoscillation 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 Nosechain approach. This has led to the introduction of two Hamiltonian schemes, the NosePoincare 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.
20141215T10:40:11Z

Blocks 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.
20141215T10:40:11Z

Selfinjective algebras and the second Hochschild cohomology group
http://hdl.handle.net/2381/30528
Title: Selfinjective algebras and the second Hochschild cohomology group
Authors: AlKadi, 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 selfinjective 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 selfinjective one parametric tame algebras which are not weakly symmetric. Here we show that HH2(Lambda) is nonzero and find a nonzero element eta in HH2(Lambda) and an associative deformation Lambdaeta of Lambda.
20141215T10:40:11Z

Meshfree radical basis function methods for advectiondominated diffusion problems
http://hdl.handle.net/2381/30529
Title: Meshfree radical basis function methods for advectiondominated diffusion problems
Authors: Hunt, David Patrick
Abstract: This thesis is concerned with the numerical solution of advectiondominated diffusion problems. There are essentially two key aspects to this work: the derivatives of an a priori error estimate for a semiLagrangian meshfree method using radial basis function interpolation to numerically approximate the firstorder linear transport problem; and the design and testing of a semiLagrangian meshless method to numerically solve the full parabolic advectiondiffusion 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 semiLagrangian 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 semiLagrangian method for the numerical approximation of advectiondominated diffusion problems, which is validated through two numerical experiments..
20141215T10:40:11Z

Finiteness conditions on the Extalgebra
http://hdl.handle.net/2381/30527
Title: Finiteness conditions on the Extalgebra
Authors: Davis, Gabriel.
Abstract: Let A be a finitedimensional algebra given by quiver and monomial relations. In [18] we see that the Extalgebra of A is finitely generated only if all the Extalgebras of certain cycle algebras overlying A are finitely generated. Here a cycle algebra Lambda is a finitedimensional 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 Extalgebra of such a Lambda to be finitely generated; this is achieved by defining a computable invariant of Lambda, the smotube. We also give necessary and sufficient conditions for the Extalgebra of Lambda to be Noetherian.;Let Lambda be a triangular matrix algebra, defined by algebras T and U and a TUbimodule M. Under certain conditions we show that if the Extalgebras of T and U are right (respectively left) Noetherian rings, then the Extalgebra 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 onepoint extension: we give a specific presentation of a result that parallels a similar theorem for the more general case above.
20141215T10:40:11Z

Constraint 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 secondorder 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 socalled forbidden patterns problems (FP), that correspond exactly to the logic MMSNP and introduce some novel algebraic tools like the recolouring 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 counterexamples. 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.
20141215T10:40:10Z

Hierarchic 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.
20141215T10:40:10Z

Normal 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.
20141215T10:40:10Z

Monads 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.
20141215T10:40:10Z

Error 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.
20141215T10:40:09Z

Algorithmic 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.
20141215T10:40:09Z

The 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, nontrivial, 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 NPcomplete. For some of these properties p we then show that by applying certain restrictions the problem still remains NPcomplete, 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 Hcolouring 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 Hcolourable subgraph of G is NPcomplete, if H is bipartite, and Sp2complete, if H is nonbipartite. 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 Hcolourable subgraph of G is Pcomplete, if H is bipartite, and DP2complete, if H is nonbipartite.;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.
20141215T10:40:09Z

Contextsensitive decision problems in groups
http://hdl.handle.net/2381/30517
Title: Contextsensitive 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) contextsensitive 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 contextfree 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 contextsensitive conjugacy problem. Our main result eliminates the previouslyconsidered possibility that the groups with contextsensitive word problem could be classified as the set of groups which are subgroups of automatic groups, by constructing a group with contextsensitive 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.
20141215T10:40:09Z

Approximation 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.
20141215T10:40:08Z

Perturbations of black holes in EinsteinCartan theory
http://hdl.handle.net/2381/30515
Title: Perturbations of black holes in EinsteinCartan theory
Authors: White, Andrew.
Abstract: Torsion is a property of spacetime 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 nonpropagating 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 energymomentum 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 energymomentum 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.
20141215T10:40:08Z

Formal 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 contextfree reduced word problem with respect to some finite monoid generating set are exactly the contextfree groups, thus proving a conjecture of HaringSmith. 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 stringrewriting 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 stringrewriting system if and only if it is the direct product of an infinite cyclic group and a finite cyclic group.
20141215T10:40:08Z

A 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 CSPbased 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 CSPbased analysis technique to model the property of nonrepudiation and give a formal generalized definition. Our definition of nonrepudiation 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.
20141215T10:40:08Z

Mixed 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 infsup condition between the velocity and pressure approximation spaces.;The present work analyses the stability of mixed hpfinite elements for planar Stokes flow on affine quadrilateral meshes comprising of regular and anisotropic elements. Firstly, a new family of mixed hpfinite elements is presented for regular elements with an infsup 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 hpfinite elements on geometrically refined anisotropic elements is considered using a macroelement technique. New results are presented for edge and corner macroelements, in particular, for the latter case, the dependence of the infsup constant on the geometric refinement parameter is explicitly characterised.;The families are then used in the numerical approximation of two physical NavierStokes problems.
20141215T10:40:07Z

Expressibility 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 = coNP. 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 polynomialtime logic which properly extends inductive fixedpoint logic (with the property that the union of the classes of the hierarchy consists of the class of problems definable in the polynomialtime logic itself).;Finally, we turn our attention to constraint satisfaction problems. This important class of problems is NPhard 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.
20141215T10:40:07Z

The p and hp finite element method applied to a class of nonlinear elliptic partial differential equations
http://hdl.handle.net/2381/30510
Title: The p and hp finite element method applied to a class of nonlinear elliptic partial differential equations
Authors: Kay, David.
Abstract: The analysis of the p and hpversions 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 nonlinear aLaplacian 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 pversion approximation theory is then used to obtain the hp approximation theory. The results obtained allow both nonuniform 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 /ipversion, which would not be possible for the h and pversions.
20141215T10:40:06Z

Asymptotic 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.
20141208T11:10:31Z

Finite 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, dKoszul 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 dKoszul 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.
20140808T13:59:03Z

Patternequivariant homology of finite local complexity patterns
http://hdl.handle.net/2381/28923
Title: Patternequivariant 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.
20140616T15:26:59Z

hpVersion discontinuous Galerkin methods on polygonal and polyhedral meshes
http://hdl.handle.net/2381/28886
Title: hpVersion discontinuous Galerkin methods on polygonal and polyhedral meshes
Authors: Cangiani, Andrea; Georgoulis, Emmanuil H.; Houston, Paul
Abstract: An hpversion interior penalty discontinuous Galerkin method (DGFEM) for the numerical solution of secondorder elliptic partial differential equations on general computational meshes consisting of polygonal/polyhedral elements is presented and analyzed. Utilizing a bounding box concept, the method employs elemental polynomial bases of total degree p (P[subscript p]basis) defined on the physical space, without the need to map from a given reference or canonical frame. This, together with a new specific choice of the interior penalty parameter which allows for facedegeneration, ensures that optimal a priori bounds may be established, for general meshes including polygonal elements with degenerating edges in two dimensions and polyhedral elements with degenerating faces and/or edges in three dimensions. Numerical experiments highlighting the performance of the proposed method are presented. Moreover, the competitiveness of the pversion DGFEM employing a P[subscript p]basis in comparison to the conforming pversion finite element method on tensorproduct elements is studied numerically for a simple test problem.
Description: Electronic version of an article published as Mathematical Models and Methods in Applied Sciences, 24 (10), 2014, DOI:10.1142/S0218202514500146 © copyright World Scientific Publishing Company http://www.worldscientific.com/doi/abs/10.1142/S0218202514500146
20140602T12:47:49Z

A statistical model of aggregate fragmentation
http://hdl.handle.net/2381/28811
Title: A statistical model of aggregate fragmentation
Authors: Spahn, F.; Vieira Neto, E.; Guimaraes, A. H. F.; Gorban, Alexander N.; Brilliantov, N. V.
Abstract: A statistical model of fragmentation of aggregates is proposed, based on the stochastic propagation of cracks through the body. The propagation rules are formulated on a lattice and mimic two important features of the process—a crack moves against the stress gradient while dissipating energy during its growth. We perform numerical simulations of the model for twodimensional lattice and reveal that the mass distribution for small and intermediatesize fragments obeys a power law, F(m)∝m[superscript −3/2], in agreement with experimental observations. We develop an analytical theory which explains the detected power law and demonstrate that the overall fragment mass distribution in our model agrees qualitatively with that one observed in experiments.
20140516T13:26:45Z

The inputoutput relationship approach to structural identifiability analysis
http://hdl.handle.net/2381/28585
Title: The inputoutput relationship approach to structural identifiability analysis
Authors: Bearup, Daniel J.; Evans, Neil D.; Chappell, Michael J.
Abstract: Analysis of the identifiability of a given model system is an essential prerequisite to the determination of model parameters from physical data. However, the tools available for the analysis of nonlinear systems can be limited both in applicability and by computational intractability for any but the simplest of models. The inputoutput relation of a model summarises the inputoutput structure of the whole system and as such provides the potential for an alternative approach to this analysis. However for this approach to be valid it is necessary to determine whether the monomials of a differential polynomial are linearly independent. A simple test for this property is presented in this work. The derivation and analysis of this relation can be implemented symbolically within Maple. These techniques are applied to analyse classical models from biomedical systems modelling and those of enzyme catalysed reaction schemes.
20140212T14:16:49Z

Adaptive discontinuous Galerkin methods for nonstationary convection–diffusion problems
http://hdl.handle.net/2381/28539
Title: Adaptive discontinuous Galerkin methods for nonstationary convection–diffusion problems
Authors: Cangiani, Andrea; Georgoulis, Emmanuil H.; Metcalfe, Stephen
Abstract: This work is concerned with the derivation of a robust a posteriori error estimator for a discontinuous Galerkin (dG) method discretization of a linear nonstationary convection–diffusion initial/boundary value problem and with the implementation of a corresponding adaptive algorithm. More specifically, we derive a posteriori bounds for the error in the L[superscript 2](H[superscript 1]) + L∞(L[superscript 2])type norm for an interior penalty dG discretization in space and a backward Euler discretization in time. Finally, an adaptive algorithm is proposed utilizing the error estimator. Optimal rate of convergence of the adaptive algorithm is observed in a number of test problems and for various Pèclet numbers.
20140123T09:55:27Z

On the prescribed mean curvature problem on the standard ndimensional ball
http://hdl.handle.net/2381/28493
Title: On the prescribed mean curvature problem on the standard ndimensional 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 ndimensional 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 n1] and will be endowed with the standard metric still denoted by g[subscript 0]. Let H : S[superscript n1] → R be a given function, we study the problem of finding a conformal metric g = u 4/n2 g[subscript 0] such that R[subscript g] = 0 in B[superscript n] and h[subscript g] = H on S[superscript n1]. 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 n1]. 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 noncompactness of the embedding H[superscript 1](B[superscript n]) → L 2(n1)/n2 (∂B[superscript n]), the EulerLagrange functional J associated to the problem, does not satisfy the PalaisSmale 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 ndimensional 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.
20131206T13:36:38Z