![[McsHomepage]](/images/McsLogoIcon.gif)
1997/2
Aspects of an Adaptive hp-Finite Element Method:
Adaptive Strategy, Conforming Appoximation and Efficient Solvers
M Ainsworth, B Senior
The main components needed for an adaptive $hp$-version finite element algorithm are discussed: an adaptive $hp$-refinement strategy, effective methods for constructing conforming $hp$-approximations, and, efficient solvers for the large, ill-conditioned systems of linear equations. Together, these provide the methodology for an effective adaptive $hp$-version algorithm. The presentation emphasizes the links between the differing components showing how the algorithms may be implemented efficiently in practice. The main principles are illustrated by use of concrete examples so that a non-expert may develop their own adaptive $hp$-code. The performance of the whole algorithm is illustrated for some representative problems taken from linear elasticity.
1997/11
Reliable and Robust a Posteriori Error Estimation for Singularly Perturbed
Reaction Diffusion Problems
M Ainsworth,
I Babuska
Problems with singular perturbations exhibit solutions with strong boundary layers and other types of local behaviour. Such features lend themselves to adaptive solution methods. The quality of any adaptive algorithm ultimately rests on the reliability and robustness of the a posteriori error control. An estimator that has proved to be one of the most reliable is the equilibrated residual method. The main property of the estimator is that it bounds the true error from above. However, the method is not robust in the singularly perturbed limit.
The current work generalizes the error estimator based on the equilibrated residuals and coincides with the standard method in the unperturbed limit. It is shown that the new method is robust in the singularly perturbed limit whilst maintaining reliability, yielding a guaranteed upper bound on the true error. Finally, the application of the estimator to the problem of controlling the spatial error in Rothe's method for the time discretistion of a simple parabolic problem is included.
1997/12
Duration Properties of Timed Transition Systems
Z Liu,
A P Ravn,
X Li
This paper proposes a method for formal real-time systems development: Ihe system requirements and high level design decisions are time interval properties, and are therefore specified in the Duration Calculus (DC), while the implementation is described in terms of timed transition systems (TTS). A link from implementation properties to the requirements and design properties is given by interpreting a DC formula in a model of the executions of a TTS and then providing rules for lifting properties proved for a TTS to DC. The method is illustrated by the Gas Burner case study.
{\bf Keywords}: Duration Calculus, Timed Transition System, Real-time systems.
1997/14
Hamiltonian cycles and all-to-all broadcasts in faulty hypercubes and k-ary
n-cubes
Iain A. Stewart
We derive a sequential algorithm {\em Find-Ham-Cycle\/} with the following property. On input: $k$ and $n$ (specifying the $k$-ary $n$-cube $Q_n^k$); $F$, a set of at most $2n-2$ faulty links; and $v$, a node of $Q_n^k$, the algorithm outputs nodes $v^+$ and $v^-$ such that if {\em Find-Ham-Cycle\/} is executed once for every node $v$ of $Q_n^k$ then the node $v^+$ (resp. $v^-$) denotes the successor (resp. predecessor) node of $v$ on a fixed Hamiltonian cycle in $Q_n^k$ in which no link is in $F$. Moreover, the algorithm {\em Find-Ham-Cycle\/} runs in time polynomial in $n$ and $k$. We also obtain a similar algorithm for a $n$-dimensional hypercube with at most $n-2$ faulty links. We use our algorithms to develop all-to-all broadcast algorithms in certain faulty hypercubes and $k$-ary $n$-cubes (improving upon one derived from a broadcast algorithm of Peleg), and to solve an open problem posed by Chan and Lee concerning the distributed construction of Hamiltonian cycles in faulty hypercubes, and also in faulty $k$-ary $n$-cubes.
1997/15
A Perspective on Lindstrom Quantifiers and Oracles
Iain A. Stewart
This paper presents a perspective on the relationship between Lindstr\"om quantifiers in model theory and oracle computations in complexity theory. We do not study this relationship here in full generality (indeed, there is much more work to do in order to obtain a full appreciation), but instead we examine what amounts to a thread of research in this topic running from the motivating results, concerning logical characterizations of nondeterministic polynomial-time, to the consideration of Lindstr\"om quantifiers as oracles, and through to the study of some naturally arising questions (and subsequent answers). Our presentation follows the chronological progress of the thread and highlights some important techniques and results at the interface between finite model theory and computational complexity theory.
1997/17
Embeddings of cycles, meshes and tori in faulty k-ary n-cubes
Yaagoub A Ashir,
Iain A Stewart
We investigate the existence of cycles, meshes and tori in a $k$-ary $n$-cube $Q_n^k$ in which a limited number of nodes and links are faulty. Our main result is that in a $k$-ary $n$-cube $Q_n^k$ in which there are $\nu$ faulty nodes and $\lambda$ faulty links where $\nu+\lambda\leq n$, there is a cycle of length at least $k^n-\nu\omega$, where $\omega=1$ if $k$ is odd and $\omega=2$ if $k$ is even (throughout, $k\geq 3$ and $n\geq 2$). We extend this result so as to prove the existence of large meshes and tori in such a faulty $k$-ary $n$-cube.
1997/21
The Cohomology and K-theory of Commuting Homeomorphisms of the Cantor Set
Alan Forrest,
John Hunton
Given a $Z^d$ homeomorphic action, $\alpha$, on the Cantor set, $X$, we consider higher order continuous integer valued dynamicalcohomology, $H*(X,\alpha)$. We also consider the dynamical K-theory of the action, the K-theory of the crossed product $C^*$-algebra $C(X)\times_{\alpha}Z{}^d$. We show that these two invariants are essentially equivalent. We also show that they only ever take torsion free values. Our work links the two invariants via a third invariant based on topological complex K-theory evaluated on an associated mapping torus.
1997/25
The Homology of Spaces Representing Exact Pairs of Homology Functors
John R Hunton,
P R Turner
We begin a study of how a relationship between representable homotopy functors manifests itself ina relationship between the homology of the representing spaces. In this paper we examine in detail the case of exact pairs of functors where a particulary simple description can be given in terms of the tensor product of coalgebraic modules.
1997/26
Extensions of Umbral Calculas II: Double Delta Operators, Leibniz
Extensions and Hattori-Stong Theorems
Francis Clarke,
John Hunton,
Nigel Ray
We continue our programme of extending the Roman-Rota umbral calculus to the setting of delta operators over a graded ring $E_*$ with a view to applications in algebraic topology and the theory of formal group laws. We concentrate on the situation where $E_*$ is free of additive torsion, in which context the central issues are number-theoretic questions of divisibility. We study polynomial algebras which admit the action of two delta operators linked by an invertible power series, and make related constructions which are motivated by the Hattori-Stong theorem of algebraic topology. Our treatment is couched purely in terms of the umbral calculus, but inspires novel topological applications; we also explain how the theory of Sheffer sequences fits naturally into this framework.
1997/28
Groups, Semigroups and Finite Presentations
C M Campbell,
E F Robertson,
N Ruskuc,
R M Thomas
Two questions are discussed. Firstly, what is the connection between the group and the semigroup defined by the same presentation? Secondly, do there exist any results for semigroups with respect to substructures being finitely presented that correspond to the classical results for groups? These themes are considered both from a geometric and a combinatorial point of view.
1997/29
Automatic Semigroups
C M Campbell,
E F Robertson,
N Ruskuc,
R M Thomas
The area of automatic groups has been one in which significant advances have been made in recent years. While it is clear that the definition of an automatic group can easily be extended to that of an automatic semigroup, there does not seem to have been a systematic investigation of such structures. It is the purpose of this paper to make such a study.
We show that certain results from the group-theoretic situation hold in this wider context, such as the solvability of the word problem in quadratic time, although others do not, such as finite presentability. There are also situations which arise in the general theory of semigroups which do not occur when considering groups; for example, we show that a semigroup S is automatic if and only if S with a zero adjoined is automatic, and also that S is automatic if and only if S with an identity adjoined is automatic. We use this last result to show that any finitely generated subsemigroup of a free semigroup is automatic.
1997/30
Compositional Inductive Verification of Duration Properties of Real-Time
Systems
Zhiming Liu,
Anders P Ravn,
Xiaoshan Li
This paper proposes a method for formal real-time systems development. At high level a system is modelled as a conventional dynamical system with states that are functions of time represented by non-negative real numbers, while the implementation and refinement at low level are described in terms of timed transition systems (TTS). Therefore, The system requirements and high level design decisions are time interval properties, and are thus specified and reasoned about in the Duration Calculus (DC), and the properties of the implementation at low level are specified and verified compositionally and inductively in timed linear temporal logic (TLTL). A link from implementation properties to the requirement and design properties is given by interpreting a DC formula in a model of the executions of a TTS and then providing rules for lifting TLTL properties proved for a TTS to DC. The method is illustrated by the Gas Burner case study.
{\bf Keywords: } Real-time Systems, Duration Calculus, Timed Transition Systems, Specification, Verification.
1997/34
A Reliable A Posterior Error Estimator for Adaptive Hierarchic Modelling
Mark Ainsworth,
Mark Arnold
An a posteriori error estimator is obtained for estimating the error in non-uniform order hierarchic models of elliptic boundary value problems on thin domains, and is shown to provide an upper bound on the actual error measured in the energy norm. The estimator has many similarities with a known heuristic refinement indicator used for adaptive hierarchic modelling and in this sense provides some theoretical support for the existing technique. Numerical examples show that the performance of both estimators is comparable, both yielding good results, with the new technique performing slightly better.
1997/35
Syntactic and Rees indices of subsemigroups
N Ruskuc,
R M Thomas
We define two different notions of index for subsemigroups of semigroups: the (right) syntactic index and the Rees index. We investigate the relationships between them and with the group index. In particular, we show that the syntactic index is a generalisation of both the group index and the Rees index. We use this fact to prove further similarities between the group index and the Rees index.
1997/36
The Complex oriented Cohomology of Extended Powers
John Hunton
We examine the behaviour of a complex oriented cohomology theory $G*(-)$ on $D_p(X)$, the $C_p$-extended power of a space $X$, seeking a description of $G^*(D_p(X))$ in terms of the cohomology $G^*(X)$. We give descriptions for the particular cases of Morava K-theory $K(n)$ for any space $X$ and for complex cobordism MU, the Brown-Peterson theories BP and any Landweber exact theory for a wide class of spaces.
1997/37
The Conditioning of Boundary Element Equations on Locally Refined Meshes
and Preconditioning by Diagonal Scaling
Mark Ainsworth,
William McLean,
Thanh Tran
Consider a boundary integral operator on a bounded, $d$-dimensional, surface in $\RR^{d+1}$. Suppose that the operator is a pseudodifferential operator of order $2m$, $m\in\RR$, and that the the associated bilinear form is symmetric and positive-definite. (The surface may be open or closed, and $m$ may be positive or negative). Let $\b{B}$ denote the stiffness matrix arising from a Galerkin boundary element method with standard nodal basis functions. If local mesh refinement is used then the partition may contain elements of very widely differing sizes, and consequently $\b{B}$ may be very badly conditioned. In fact, if the elements are non-degenerate and $2|m| Keywords: Boundary element method. Condition numbers. Diagonal scaling. Preconditioning.
1997/39
Reflexivity of Modules over QF-3 Algebras
Nicole Snashall
The indecomposable injective projective modules of a basic finite-dimensional algebra are studied in relation to the notion of a chain end; this concept is a generalisation of that given by Murase for such algebras which are also indecomposable and serial. It is shown that the basic finite-dimensional algebras for which the chain ends are precisely the indecomposable injective projective modules are those which are both QF-3 and left QF-2. Reflexivity in the sense of Halmos and Fuller, Nicholson and Watters is then investigated for modules over such algebras. The reflexive QF-3 and left QF-2 algebras are characterised, and necessary and sufficient conditions are given on the quiver of the algebra for every faithful left module to be reflexive.
1997/40
Domain Decomposition Preconditioners for p and hp Finite Element
Approximation of Stokes Equations
Mark Ainsworth,
Spencer Sherwin
Domain decomposition preconditioning techniques are developed in the context of $hp$ finite element approximation of the Stokes problem. Two basic types of preconditioner are considered: a block diagonal scheme based on decoupling the velocity and pressure components, and, a scheme based on an indefinite system similar to the original Stokes system. For each type of scheme, theoretical estimates are obtained for the location of the eigenvalues of the preconditioned operators in terms of the polynomial degree, the mesh sizes on the coarse and fine grids, and the {\em inf-sup} constant for the method. Theoretical estimates show that the growth of the bounds is modest as the mesh is refined and the polynomial order is increased. The preconditioners are shown to be applicable to various iterative schemes for the Stokes systems. The theoretical bounds are compared with actual quantities obtained in practical computations for several representative problems.
1997/41
Solving Hamiltonian systems arising from ODE eigenproblems
Carsten R Maple,
Marco Marletta
The numerical solution of a linear Hamiltonian system of ordinary differential equations is discussed. Eigenvalue problems for Hamiltonian systems can arise from a number of sources. Here we are concerned with the system attained after transforming the general $2m$th order regular Sturm-Liouville problem. A new algorithm is developed that attempts to bypass the problems that force existing solvers to take a large number of small integration steps when the eigenparameter is large. A coupled system of differential equations for the eigenvalues and eigenvectors of a certain matrix is formed. This system is then solved using a predictor-corrector type method. The eigenvectors vary in a relatively smooth manner, and therefore these differential equations are solved using a numerical method. The eigenvalues are found by approximating the differential equations and solving exactly. A numerical results discussion illustrates the advantages and drawbacks of the algorithm.
1997/42
Implementing Operational Semantics
(Preliminary Report)
Roy Crole
This paper describes a high level operational semantics for a simple programming language, called KOREL, together with a parser, interpreter and pretty printer which are implemented in the (pure) functional programming language Haskell. The syntax of KOREL is presented via BNF grammars, and the operational semantics is specified via structured, inductive rules. The paper outlines the broad ideas behind the Haskell implementation, with a more detailed explication of the key techniques. A code listing can be found in TR 1997/43.
1997/43
The KOREL Programming Language
(Preliminary Report)
Roy Crole
This report contains the full listing of the Haskell code which implements the programming language KOREL. A description of the language, and of the Haskell code, can be found in TR 1997/42.
1997/44
Asymptotic behaviour of the spectral decomposition of Riccati-like
variables for linear Hamiltonian systems
Carsten R Maple,
Marco Marletta
This work is a sequel to Tech Report 1997/41, in which an algorithm was proposed to solve linear Hamiltonian systems. This involved finding a coupled system of differential equations for the eigenvalues and eigenvectors of the so-called Atkinson theta matrices associated with the system. The Atkinson theta matrices are closely related to Riccati variables. In the present report, we examine the behaviour of these eigenvalues and eigenvectors for large values of the spectral parameter $\lambda$, for two model problems. The analysis reveals radically different behaviour of the eigenvalues and eigenvectors for two Hamiltonian systems which are superficially very similar. This shows that the method in Tech Report 1997/41 will easily cope with large values of $\lambda$ for some problems, but not for others.
![[Top]](/images/McsTopIcon.gif)