Vertex splitting and connectivity augmentation in hypergraphs

We consider problems of splitting and connectivity augmentation in hypergraphs. In a hypergraph G = (V +s, E), to split two edges su, sv, is to replace them with a single edge uv. We are interested in doing this in such a way as to preserve a defined level of connectivity in V . The splitting technique is often used as a way of adding new edges into a graph or hypergraph, so as to augment the connectivity to some prescribed level. We begin by providing a short history of work done in this area. Then several preliminary results are given in a general form so that they may be used to tackle several problems. We then analyse the hypergraphs G = (V + s, E) for which there is no split preserving the local-edge-connectivity present in V. We provide two structural theorems, one of which implies a slight extension to Mader’s classical splitting theorem. We also provide a characterisation of the hypergraphs for which there is no such “good” split and a splitting result concerned with a specialisation of the local-connectivity function. We then use our splitting results to provide an upper bound on the smallest number of size-two edges we must add to any given hypergraph to ensure that in the resulting hypergraph we have λ(x, y) ≥ r(x, y) for all x, y in V, where r is an integer valued, symmetric requirement function on V*V. This is the so called “local-edge-connectivity augmentation problem” for hypergraphs. We also provide an extension to a Theorem of Szigeti, about augmenting to satisfy a requirement r, but using hyperedges. Next, in a result born of collaborative work with Zoltán Király from Budapest, we show that the local-connectivity augmentation problem is NP-complete for hypergraphs. Lastly we concern ourselves with an augmentation problem that includes a locational constraint. The premise is that we are given a hypergraph H = (V,E) with a bipartition P = {P1, P2} of V and asked to augment it with size-two edges, so that the result is k-edge-connected, and has no new edge contained in some P(i). We consider the splitting technique and describe the obstacles that prevent us forming “good” splits. From this we deduce results about which hypergraphs have a complete Pk-split. This leads to a minimax result on the optimal number of edges required and a polynomial algorithm to provide an optimal augmentation.

Perturbation, extraction and refinement of invariant pairs for matrix polynomials

Generalizing the notion of an eigenvector, invariant subspaces are frequently used in the context of linear eigenvalue problems, leading to conceptually elegant and numerically stable formulations in applications that require the computation of several eigenvalues and/or eigenvectors. Similar benefits can be expected for polynomial eigenvalue problems, for which the concept of an invariant subspace needs to be replaced by the concept of an invariant pair. Little has been known so far about numerical aspects of such invariant pairs. The aim of this paper is to fill this gap. The behavior of invariant pairs under perturbations of the matrix polynomial is studied and a first-order perturbation expansion is given. From a computational point of view, we investigate how to best extract invariant pairs from a linearization of the matrix polynomial. Moreover, we describe efficient refinement procedures directly based on the polynomial formulation. Numerical experiments with matrix polynomials from a number of applications demonstrate the effectiveness of our extraction and refinement procedures.

High frequency scattering by convex curvilinear polygons

We consider the scattering of a time-harmonic acoustic incident plane wave by a sound soft convex curvilinear polygon with Lipschitz boundary. For standard boundary or finite element methods, with a piecewise polynomial approximation space, the number of degrees of freedom required to achieve a prescribed level of accuracy grows at least linearly with respect to the frequency of the incident wave. Here we propose a novel Galerkin boundary element method with a hybrid approximation space, consisting of the products of plane wave basis functions with piecewise polynomials supported on several overlapping meshes; a uniform mesh on illuminated sides, and graded meshes refined towards the corners of the polygon on illuminated and shadow sides. Numerical experiments suggest that the number of degrees of freedom required to achieve a prescribed level of accuracy need only grow logarithmically as the frequency of the incident wave increases.

Filtering techniques in self-tuning

In the last few years a state-space formulation has been introduced into self-tuning control. This has not only allowed for a wider choice of possible control actions, but has also provided an insight into the theory underlying—and hidden by—that used in the polynomial description. This paper considers many of the self-tuning algorithms, both state-space and polynomial, presently in use, and by starting from first principles develops the observers which are, effectively, used in each case. At any specific time instant the state estimator can be regarded as taking one of two forms. In the first case the most recently available output measurement is excluded, and here an optimal and conditionally stable observer is obtained. In the second case the present output signal is included, and here it is shown that although the observer is once again conditionally stable, it is no longer optimal. This result is of significance, as many of the popular self-tuning controllers lie in the second, rather than first, category.

Self-tuning regulators—a state space approach

This paper employs a state space system description to provide a pole placement scheme via state feedback. It is shown that when a recursive least squares estimation scheme is used, the feedback employed can be expressed simply in terms of the estimated system parameters. To complement the state feedback approach, a method employing both state feedback and linear output feedback is discussed. Both methods arc then compared with the previous output polynomial type feedback schemes.

Optimal observers for ARMA models

A polynomial-based ARMA model, when posed in a state-space framework can be regarded in many different ways. In this paper two particular state-space forms of the ARMA model are considered, and although both are canonical in structure they differ in respect of the mode in which disturbances are fed into the state and output equations. For both forms a solution is found to the optimal discrete-time observer problem and algebraic connections between the two optimal observers are shown. The purpose of the paper is to highlight the fact that the optimal observer obtained from the first state-space form, commonly known as the innovations form, is not that employed in an optimal controller, in the minimum-output variance sense, whereas the optimal observer obtained from the second form is. Hence the second form is a much more appropriate state-space description to use for controller design, particularly when employed in self-tuning control schemes.

Data based constructive identification - overcoming the curse of dimensionality

The modelling of a nonlinear stochastic dynamical processes from data involves solving the problems of data gathering, preprocessing, model architecture selection, learning or adaptation, parametric evaluation and model validation. For a given model architecture such as associative memory networks, a common problem in non-linear modelling is the problem of "the curse of dimensionality". A series of complementary data based constructive identification schemes, mainly based on but not limited to an operating point dependent fuzzy models, are introduced in this paper with the aim to overcome the curse of dimensionality. These include (i) a mixture of experts algorithm based on a forward constrained regression algorithm; (ii) an inherent parsimonious delaunay input space partition based piecewise local lineal modelling concept; (iii) a neurofuzzy model constructive approach based on forward orthogonal least squares and optimal experimental design and finally (iv) the neurofuzzy model construction algorithm based on basis functions that are Bézier Bernstein polynomial functions and the additive decomposition. Illustrative examples demonstrate their applicability, showing that the final major hurdle in data based modelling has almost been removed.

A new approach to reduced-order modelling

An error polynomial is defined, the coefficients of which indicate the difference at any instant between a system and a model of lower order approximating the system. It is shown how Markov parameters and time series proportionals of the model can be matched with those of the system by setting error polynomial coefficients to zero. Also discussed is the way in which the error between system and model can be considered as being a filtered form of an error input function specified by means of model parameter selection.

Survival of Lactobacillus plantarum in model solutions and fruit juices

The aim of the work was to study the survival of Lactobacillus plantarum NCIMB 8826 in model solutions and develop a mathematical model describing its dependence on pH, citric acid and ascorbic acid. A Central Composite Design (CCD) was developed studying each of the three factors at five levels within the following ranges, i.e., pH (3.0-4.2), citric acid (6-40 g/L), and ascorbic acid (100-1000 mg/L). In total, 17 experimental runs were carried out. The initial cell concentration in the model solutions was approximately 1 × 10(8)CFU/mL; the solutions were stored at 4°C for 6 weeks. Analysis of variance (ANOVA) of the stepwise regression demonstrated that a second order polynomial model fits well the data. The results demonstrated that high pH and citric acid concentration enhanced cell survival; one the other hand, ascorbic acid did not have an effect. Cell survival during storage was also investigated in various types of juices, including orange, grapefruit, blackcurrant, pineapple, pomegranate, cranberry and lemon juice. The model predicted well the cell survival in orange, blackcurrant and pineapple, however it failed to predict cell survival in grapefruit and pomegranate, indicating the influence of additional factors, besides pH and citric acid, on cell survival. Very good cell survival (less than 0.4 log decrease) was observed after 6 weeks of storage in orange, blackcurrant and pineapple juice, all of which had a pH of about 3.8. Cell survival in cranberry and pomegranate decreased very quickly, whereas in the case of lemon juice, the cell concentration decreased approximately 1.1 logs after 6 weeks of storage, albeit the fact that lemon juice had the lowest pH (pH~2.5) among all the juices tested. Taking into account the results from the compositional analysis of the juices and the model, it was deduced that in certain juices, other compounds seemed to protect the cells during storage; these were likely to be proteins and dietary fibre In contrast, in certain juices, such as pomegranate, cell survival was much lower than expected; this could be due to the presence of antimicrobial compounds, such as phenolic compounds.

A comprehensive investigation of the synthesis of prebiotic galactooligosaccharides by whole cells of Bifidobacterium bifidum NCIMB 41171

The synthesis of galactooligosaccharides (GOS) by whole cells of Bifidobacterium bifidum NCIMB 41171 was investigated by developing a set of mathematical models. These were second order polynomial equations, which described responses related to the production of GOS constituents, the selectivity of lactose conversion into GOS, and the relative composition of the produced GOS mixture, as a function of the amount of biocatalyst, temperature, initial lactose concentration, and time. The synthesis reactions were followed for up to 36 h. Samples were withdrawn every 4 h, tested for β-galactosidase activity, and analysed for their carbohydrate content. GOS synthesis was well explained by the models, which were all significant (P < 0.001). The GOS yield increased as temperature increased from 40 °C to 60 °C, as transgalactosylation became more pronounced compared to hydrolysis. The relative composition of GOS produced changed significantly with the initial lactose concentration (P < 0.001); higher ratios of tri-, tetra-, and penta-galactooligosaccharides to transgalactosylated disaccharides were obtained as lactose concentration increased. Time was a critical factor, as a balanced state between GOS synthesis and hydrolysis was roughly attained in most cases between 12 and 20 h, and was followed by more pronounced GOS hydrolysis than synthesis.

Advanced global optimisation for mission analysis and design

This report describes the analysis and development of novel tools for the global optimisation of relevant mission design problems. A taxonomy was created for mission design problems, and an empirical analysis of their optimisational complexity performed - it was demonstrated that the use of global optimisation was necessary on most classes and informed the selection of appropriate global algorithms. The selected algorithms were then applied to the di®erent problem classes: Di®erential Evolution was found to be the most e±cient. Considering the speci¯c problem of multiple gravity assist trajectory design, a search space pruning algorithm was developed that displays both polynomial time and space complexity. Empirically, this was shown to typically achieve search space reductions of greater than six orders of magnitude, thus reducing signi¯cantly the complexity of the subsequent optimisation. The algorithm was fully implemented in a software package that allows simple visualisation of high-dimensional search spaces, and e®ective optimisation over the reduced search bounds.

Collision prediction of a moving object within a virtual world

This paper provides a solution for predicting moving/moving and moving/static collisions of objects within a virtual environment. Feasible prediction in real-time virtual worlds can be obtained by encompassing moving objects within a sphere and static objects within a convex polygon. Fast solutions are then attainable by describing the movement of objects parametrically in time as a polynomial.

Robust eigenstructure assignment in quadratic matrix polynomials: nonsingular case

Feedback design for a second-order control system leads to an eigenstructure assignment problem for a quadratic matrix polynomial. It is desirable that the feedback controller not only assigns specified eigenvalues to the second-order closed loop system but also that the system is robust, or insensitive to perturbations. We derive here new sensitivity measures, or condition numbers, for the eigenvalues of the quadratic matrix polynomial and define a measure of the robustness of the corresponding system. We then show that the robustness of the quadratic inverse eigenvalue problem can be achieved by solving a generalized linear eigenvalue assignment problem subject to structured perturbations. Numerically reliable methods for solving the structured generalized linear problem are developed that take advantage of the special properties of the system in order to minimize the computational work required. In this part of the work we treat the case where the leading coefficient matrix in the quadratic polynomial is nonsingular, which ensures that the polynomial is regular. In a second part, we will examine the case where the open loop matrix polynomial is not necessarily regular.

Plane wave approximation of homogeneous Helmholtz solutions

In this paper, we study the approximation of solutions of the homogeneous Helmholtz equation Δu + ω 2 u = 0 by linear combinations of plane waves with different directions. We combine approximation estimates for homogeneous Helmholtz solutions by generalized harmonic polynomials, obtained from Vekua’s theory, with estimates for the approximation of generalized harmonic polynomials by plane waves. The latter is the focus of this paper. We establish best approximation error estimates in Sobolev norms, which are explicit in terms of the degree of the generalized polynomial to be approximated, the domain size, and the number of plane waves used in the approximations.