Some computational graph problems are considered in this thesis and algorithms for solving these problems are described in detail. The problems can be divided into three main classes, namely, problems involving partially ordered sets, finding cycles in graphs, and shortest path problems. Most of the algorithms are based on recursive procedures using depth-first search. The efficiency of each algorithm is derived and it can be concluded that the majority of the proposed algorithms are either optimal and near-optimal within a constant factor. The efficiency of the algorithms is measured by the time and space requirements for their implementation.

This thesis is concerned with an error analysis of numerical methods for two point boundary value problems and much of the investigation is concentrated on collocation methods from an 'a posteriori' point of view. Most of the previous work on error bounds for boundary value problems has been of an 'a priori' nature, requiring knowledge of the inverse of the differential operator under consideration and furnishing convergence proofs and theoretical bounds on the error. There are however a few results of the converse nature and in this thesis means of determining error bounds in practice are developed, much of the analysis also applying to Fredholm integral equations of the second kind. In more detail, having firstly considered certain preliminaries the setting for the theory and the principal results for later use are presented. It is demonstrated how the approximate solution by collocation of linear differential equations fits into this background and different 'a priori' approaches are examined by example and shown to be rather unsatisfactory. The 'a posteriori' outlook is then considered and to achieve practical results the inverse of the approxi- mating operator is related to the inverse of the collocation matrix. However the problem of obtaining a suitable bound on the norm of this inverse operator is encountered and after examination of the most obvious approach which proves unsatisfactory a convenient bound is developed. Certain interesting computational properties of matrices involved in the process are discussed and a brief examination of condition numbers is given. A different theoretical analysis using the concept of a 'collectively compact sequence of operators' is considered and it is demonstrated that the approximate solution by collocation of linear differential equations can be 'extended' to satisfy the conditions for this theory. Again the error bounds are reduced to a more practical level and subsequently a generalisation of the notion of this extension is suggested. The implementation of the various practical error bounds which have been deduced is then considered in detail and formulae for their evaluation are presented. The numerical results of examples of this application are then given followed by a discussion of certain relevent points concerning the experiments. In the final chapter certain possible extensions of the analysis herein are briefly examined and lastly a review of the work of this thesis with appropriate conclusions is given.

This thesis is concerned with the structure of trees and linear graphs. In particular an attempt is made to relate structure of these objects to the known methods for counting them. Although the work described here is essentially not computer oriented, the generation and decomposition of graphs and trees by computer is in the background, and so a short section on the computer representation of the various objects is included. Trees are analysed bearing in mind the counting methods due first to Cayley, and a later method using Polya's classical theorem of enumerative combinatorial analysis. Various methods of representation and generation of trees are presented and compared. This thesis then goes on to the substantially more difficult problem of analysing graphs using similar techniques, and attempts are made to relate the structure of graphs to the known techniques for enumerating graphs. This involves a more detailed study of Polya's theorem and an investigation into the underlying concepts such as permutation groups as they are applicable to the case under scrutiny. Representations are developed to aid these investigations. In the following section of the work, methods are investigated for the decomposition of a linear graph, and a number of different decompositions or factorisations are looked at. One such factorisation considered in some detail is the problem of extracting a spanning tree from a grapho and the ways in which the remaining graph or co-tree graph may be manipulated. The complete decomposition of a graph into trees may be achieved using these methods, and the concept of the structure tree of the decomposition is introduced and its properties explored. The techniques described have all been implemented, and a discussion of the problems of the implementation together with some estimates of timing reguirements is also included.

This thesis is concerned with an error analysis of approximate methods for second order linear two point boundary value problems, in particular for the method of collocation using piecewise polynomial approximations. As in previous related work on strict error bounds an operator theoretic approach is taken. We consider operators acting between two spaces Xl and X2 with uniformly equivalent metrics. The concept of a "collectively compact sequence of operators" is examined in relation to "pointwise convergence" - relevant to many approximate numerical methods. The introduction of a finite dimensional projection operator permits considerable theoretical development which enables us to relate various inverse approximate operators directly to a certain inverse matrix. The application of this theory to the approximate solution of linear two point boundary value problems is then considered. It is demonstrated how the method of collocation can be expressed in terms of a projection method applied to a certain operator equation. The conditions required by the theory are expressed in terms of continuity requirements on the coefficients of the differential equation and in terms of the distribution of the collocation pOints. Various estimates of bounds on the inverse differential operator are presented and it is demonstrated that the "residual" can be a very useful error estimate. The use of a "weighted infinity norm" is shown to improve the applicability of the theory for "stiff" problems. Some real problems are then examined and a selection of numerical results illustrating the theory and application are presented. The thesis concludes with a brief review, outlining some of the deficiencies in the work and possible improvements and extensions of the analysis.

In this thesis several topics in the numerical solution of the initial value problem in first-order ordinary differential equations are investigated. Consideration is given initially to stiff differential equations and their solution by stiffly-stable linear multistep methods which incorporate second derivative terms. Attempts are made to increase the size of the stability regions for these methods both by particular choices for the third characteristic polynomial and by the use of optimization techniques while investigations are carried out regarding the capabilities of a high order method. Subsequent work is concerned with the development of Runge-Kutta methods which include second-derivative terms and are implicit with respect to y rather than k. Methods of order three and four are proposed which are L-stable. The major part of the thesis is devoted to the establishment of recurrence relations for operators associated with linear multistep methods which are based on a non-polynomial representation of the theoretical solution. A complete set of recurrence relations is developed for both implicit and explicit multistep methods which are based on a representation involving a polynomial part and any number of arbitrary functions. The amount of work involved in obtaining multistep methods by this technique is considered and criteria are proposed to decide when this particular method of derivation should be employed. The thesis is concluded by using Prony's method to develop one-step methods and multistep methods which are exponentially adaptive and as such can be useful in obtaining solutions to problems which are exponential in nature.

Storage fragmentation, the splitting of available computer memory space into separate gaps by allocations and deal locations of various sized blocks with consequent loss of utilisation due to reduced ability to satisfy reque~ts, has ~roved difficult to analyse. Most previous studies rely on simulation, and nearly all of the few published analyses that do not, simplify the combinatorial complexity that arises by some averaging assumption. After a survey of these results, an exact analytical approach to the study of storage allocation and fragmentation is presented. A model of an allocation scheme of a kind common in many computing systems is described. Requests from a saturated fi rst come fi rst served queue for varyi ng amounts of contiguous storage are satisfied as soon as sufficient space becomes available in a storage memory of fixed total size. A placement algorithm decides which free locations to allocate if a choice is possible. After a variable time, allocated requests are completed and their occupied storage is freed again. In general, the avail ab 1 e space becomes fragmented because allocated requests are not relocated ~r moved around in stora~e. The model's behaviour and in particul~r the storage utilisation are studied under conditions in which the model is a finite homogeneous Markov chain. The algebraic structure of its sparse transition matrix is discovered to have a striki~g recursive pattern, allowing the steady state equation to be simplified considerably and unexpectedly to a simple and direct statement of the effect of the choice of placement algorithm on the steady state. Possible developments and uses of this simplified analysis are indicated, and some investigated. The exact probabilistic behaviour of models of relatively small memory sizes is computed, and different placement algorithms are compared with each other and with the analytic results which are derived for the corresponding model in which relocation is allowed.

The results of a numerical investigation of the Haylaigh·-H:l:tz method for the approxi.mate solution of two-point boundary value problems in ordinary differential equations are presented. Theoretical results are developed which indicate that the observed behaviour ie typical of the method in more general applications. In particular9 a number of choices of co-ord:i.natefunctions for certain second order equations are considerede A new algorit~~ for the efficient evaluation of an established sequence of functions related to the Legendre polynomials is desoribed, and the sequence is compared in use with a similar sequence related to the Chebyshev polynomials. Algebraic properties of the Rayleigh ••R1tz equations tor these and other co-ordinate systems are discussede The Chebyshev system is shown to lead to equations with oonvenient computational and theoretical properties, and the latter are used to characterize the asymptotic convergence of the approximations for linear equationse These results are subsequently extended to a certain type of non-linear equatione An orthonormalization approach to the solution ot the R~leigh- Ritz equations which has been suggested in the literature is compa.red in practice with more usual methods, and it is shown that the properties of the resulting approximations are not improvedo Since it is knoWli.that the method requires more work than established ones it cannot be recommendedo Quadrature approximations of elements of the ~leigh-Ritz matrices a.re investigated, and known results for a restricted class ot quadra·t';.re approximation are extended towards the more general case. In a final chapter extensions of the material of earlier chapters to partial differential equations are described, and new forms of the 'finite element' and 'extended Kantorovich' methods are proposed. A summary of the conclusions discerned from the investigation is given.

Three assumptions are normally made about roundoff error sequences in fixed-point arithmetic digital processors: all values of error, within the limits set by the roundoff process, have an equal probability of occurrence; they are random; and they are not correlated with any other signal or error sequence. The validity of these assumptions for digital filter realisations employing a signal wordlength in the range of 4 to 3 bits is examined. The investigation begins by using a fast Fourier transform algorithm to perform spectral analysis on roundoff error sequences when the test signal is a quantised sinusoid. It continues by comparing the variance of the error sequence measured at the output of various filter realisations with that theoretically predicted using the normal assumptions; this is done using random test sequences. It is shown that under certain conditions, for the signal wordlengths under consideration, each of the three assumptions can become invalid. In conclusion this work reports attempts to develop more accurate predictive noise models which only incorporate assumptions of greater validity.

In this thesis we study the computability theory of partial functions defined over metric algebras. We integrate aspects of two broad approaches to generalising the theory of computability on the natural numbers to uncountable algebraic structures - abstract models that use generalised models of computation to compute over structures which are considered independently of any representation or implementation, and concrete models for which connections with computability on the naturals and physical realisability are the main focus. The abstract models with which we work are those of the imperative style 'while' programming language and generalisations of Kleene's <I>μ</I>-recursive function schemes from the naturals to abstract algebras. We study computation by such models over effective metric partial algebras. The effectivity of such algebras is based on the choice of a computable dense metric sub-space. The notion of a computable function over these types of spaces is well established. We review some simple connections with other models. We prove the closure of these functions under abstract 'while' language computation and approximation. We prove analogous results for recursive function schemes. We consider some of these ideas in several applications connected with the real numbers, matrix algebra, deterministic parallel models of computation and Hilbert and Banach spaces. We analyse the connection between sets with computable projection functions and computable distance functions in Hilbert space.

A great many physical phenomena are modelled by partial di erential equations (PDEs), and numerical schemes often have to be employed to approximate the solutions to these equations where analytical solutions cannot be found. We develop and analyse here new schemes belonging to two broad classes, schemes that are asynchronous, and exponential integrators. We apply these schemes to test models of advection-di usion-reaction processes that occur in porous media ow. Asynchronous schemes allow di erent parts of the physical domain to evolve at different rates. We develop a class of asynchronous schemes that progress by discrete events, where a single event is the transfer of a unit of mass through the domain, according to the local ux. These schemes are intended to focus computational e ort where it is most needed, as a high local ux will cause the algorithm to automatically take more events in that part of the domain. We develop the simplest version of this scheme, and then develop further schemes by adding modi cations to address potential shortcomings. Numerical experiments indicate a number of interesting relations between the parameters of these schemes. Particularly, the error of the schemes seems to be rst order with respect to a control parameter we call the mass unit. Some analysis is conducted which can pave the way towards robust theoretical understanding of these schemes in the future. Exponential integrators are time stepping schemes which exactly solve the linear part of a semilinear ODE system. This class of schemes requires the approximation of a matrix exponential in every step, and one successful modern method is the Krylov subspace projection method. We investigate, through analysis and experiment, the e ect of breaking down a single timestep into multiple substeps, recycling the Krylov subspace to minimise costs. Our results indicate that this can increase accuracy and e ciency. We show the results of an investigation into developing a class of `semi-exponential' Runge-Kutta type schemes, which use an exponential integrator for the initial stage and then essentially ful l classical order conditions for the remaining stages. Finally, we return to the concept of asynchronicity in a di erent form. With the advent of massively parallel machines, there is increasing interest in developing domain-decomposition type schemes that are robust to random failures or delays in communication between processing elements. This is because in massively parallel machines, communication between processors is likely to be the signi cant bottleneck in execution time. Recently the e ect of such communication delay with a simple domain-decomposed Euler timestepping solver applied to a linear PDE has been investigated with promising results. Here, inspired by exponential integrators, we investigate the natural extension of this, by replacing the Euler timestepping with the evaluation of the appropriate matrix exponential on the sub-domain. We have performed experiments simulating the communication delay and the results are also promising.