An oblivious shortest-path routing algorithm for fully connected cubic networks

Fully connected cubic networks (FCCNs) are a class of newly proposed hierarchical interconnection networks for multicomputer systems, which enjoy the strengths of constant node degree and good expandability. The shortest path routing in FCCNs is an open problem. In this paper, we present an oblivious routing algorithm for n-level FCCN with N = 8(n) nodes, and prove that this algorithm creates a shortest path from the source to the destination. At the costs of both an O(N)-parallel-step off-line preprocessing phase and a list of size N stored at each node, the proposed algorithm is carried out at each related node in O(n) time. In some cases the proposed algorithm is superior to the one proposed by Chang and Wang in terms of the length of the routing path. This justifies the utility of our routing strategy. (C) 2006 Elsevier Inc. All rights reserved.

A novel radix-3/9 algorithm for type-III generalized discrete Hartley transform

A novel radix-3/9 algorithm for type-III generalized discrete Hartley transform (GDHT) is proposed, which applies to length-3(P) sequences. This algorithm is especially efficient in the case that multiplication is much more time-consuming than addition. A comparison analysis shows that the proposed algorithm outperforms a known algorithm when one multiplication is more time-consuming than five additions. When combined with any known radix-2 type-III GDHT algorithm, the new algorithm also applies to length-2(q)3(P) sequences.

A forward constrained selection algorithm for probabilistic neural network

A new probabilistic neural network (PNN) learning algorithm based on forward constrained selection (PNN-FCS) is proposed. An incremental learning scheme is adopted such that at each step, new neurons, one for each class, are selected from the training samples arid the weights of the neurons are estimated so as to minimize the overall misclassification error rate. In this manner, only the most significant training samples are used as the neurons. It is shown by simulation that the resultant networks of PNN-FCS have good classification performance compared to other types of classifiers, but much smaller model sizes than conventional PNN.

An algorithm for isentropic flow

An efficient algorithm is presented for the solution of the equations of isentropic gas dynamics with a general convex gas law. The scheme is based on solving linearized Riemann problems approximately, and in more than one dimension incorporates operator splitting. In particular, only two function evaluations in each computational cell are required. The scheme is applied to a standard test problem in gas dynamics for a polytropic gas

An efficient flux difference splitting algorithm for unsteady duct flows of a real gas

A numerical scheme is presented for the solution of the Euler equations of compressible flow of a real gas in a single spatial coordinate. This includes flow in a duct of variable cross-section, as well as flow with slab, cylindrical or spherical symmetry, as well as the case of an ideal gas, and can be useful when testing codes for the two-dimensional equations governing compressible flow of a real gas. The resulting scheme requires an average of the flow variables across the interface between cells, and this average is chosen to be the arithmetic mean for computational efficiency, which is in contrast to the usual “square root” averages found in this type of scheme. The scheme is applied with success to five problems with either slab or cylindrical symmetry and for a number of equations of state. The results compare favourably with the results from other schemes.

An efficient shock capturing algorithm for compressible flows in a duct of variable cross-section

A numerical scheme is presented for the solution of the Euler equations of compressible flow of a gas in a single spatial co-ordinate. This includes flow in a duct of variable cross-section as well as flow with slab, cylindrical or spherical symmetry and can prove useful when testing codes for the two-dimensional equations governing compressible flow of a gas. The resulting scheme requires an average of the flow variables across the interface between cells and for computational efficiency this average is chosen to be the arithmetic mean, which is in contrast to the usual ‘square root’ averages found in this type of scheme. The scheme is applied with success to five problems with either slab or cylindrical symmetry and a comparison is made in the cylindrical case with results from a two-dimensional problem with no sources.

An algorithm for the shallow water equations with body fitted meshes

An efficient algorithm based on flux difference splitting is presented for the solution of the two-dimensional shallow water equations in a generalised coordinate system. The scheme is based on solving linearised Riemann problems approximately and in more than one dimension incorporates operator splitting. The scheme has good jump capturing properties and the advantage of using body-fitted meshes. Numerical results are shown for flow past a circular obstruction.

An isentropic flow algorithm with body fitted meshes

An efficient algorithm based on flux difference splitting is presented for the solution of the three-dimensional equations of isentropic flow in a generalised coordinate system, and with a general convex gas law. The scheme is based on solving linearised Riemann problems approximately and in more than one dimension incorporates operator splitting. The algorithm requires only one function evaluation of the gas law in each computational cell. The scheme has good shock capturing properties and the advantage of using body-fitted meshes. Numerical results are shown for Mach 3 flow of air past a circular cylinder. Furthermore, the algorithm also applies to shallow water flows by employing the familiar gas dynamics analogy.

Temperature and the development rates of thrips: evidence for a constraint on local adaptation?

Typically, the relationship between insect development and temperature is described by two characteristics: the minimum temperature needed for development to occur (T-min) and the number of day degrees required (DDR) for the completion of development. We investigated these characteristics in three English populations of Thrips major and T tabaci [Cawood, Yorkshire (N53degrees49', W1degrees7'); Boxworth, Cambridgeshire (N52degrees15', W0degrees1'); Silwood Park, Berkshire (N51degrees24', W0degrees38')], and two populations of Frankliniella occidentalis (Cawood; Silwood Park). While there were no significant differences among populations in either T-min (mean for T major = 7.0degreesC; T tabaci = 5.9degreesC; F. occidentalis = 6.7degreesC) or DDR (mean for T major = 229.9; T tabaci = 260.8; F occidentalis = 233.4), there were significant differences in the relationship between temperature and body size, suggesting the presence of geographic variation in this trait. Using published data, in addition to those newly collected, we found a negative relationship between T-min. and DDR for F occidentalis and T tabaci, supporting the hypothesis that a trade-off between T-min and DDR may constrain adaptation to local climatic conditions.

Combined CloudSat-CALIPSO-MODIS retrievals of the properties of ice clouds

In this paper, data from spaceborne radar, lidar and infrared radiometers on the “A-Train” of satellites are combined in a variational algorithm to retrieve ice cloud properties. The method allows a seamless retrieval between regions where both radar and lidar are sensitive to the regions where one detects the cloud. We first implement a cloud phase identification method, including identification of supercooled water layers using the lidar signal and temperature to discriminate ice from liquid. We also include rigorous calculation of errors assigned in the variational scheme. We estimate the impact of the microphysical assumptions on the algorithm when radiances are not assimilated by evaluating the impact of the change in the area-diameter and the density-diameter relationships in the retrieval of cloud properties. We show that changes to these assumptions affect the radar-only and lidar-only retrieval more than the radar-lidar retrieval, although the lidar-only extinction retrieval is only weakly affected. We also show that making use of the molecular lidar signal beyond the cloud as a constraint on optical depth, when ice clouds are sufficiently thin to allow the lidar signal to penetrate them entirely, improves the retrieved extinction. When infrared radiances are available, they provide an extra constraint and allow the extinction-to-backscatter ratio to vary linearly with height instead of being constant, which improves the vertical distribution of retrieved cloud properties.

Bayesian retrieval of complete posterior PDFs of oceanic rain rate from microwave observations

A new Bayesian algorithm for retrieving surface rain rate from Tropical Rainfall Measuring Mission (TRMM) Microwave Imager (TMI) over the ocean is presented, along with validations against estimates from the TRMM Precipitation Radar (PR). The Bayesian approach offers a rigorous basis for optimally combining multichannel observations with prior knowledge. While other rain-rate algorithms have been published that are based at least partly on Bayesian reasoning, this is believed to be the first self-contained algorithm that fully exploits Bayes’s theorem to yield not just a single rain rate, but rather a continuous posterior probability distribution of rain rate. To advance the understanding of theoretical benefits of the Bayesian approach, sensitivity analyses have been conducted based on two synthetic datasets for which the “true” conditional and prior distribution are known. Results demonstrate that even when the prior and conditional likelihoods are specified perfectly, biased retrievals may occur at high rain rates. This bias is not the result of a defect of the Bayesian formalism, but rather represents the expected outcome when the physical constraint imposed by the radiometric observations is weak owing to saturation effects. It is also suggested that both the choice of the estimators and the prior information are crucial to the retrieval. In addition, the performance of the Bayesian algorithm herein is found to be comparable to that of other benchmark algorithms in real-world applications, while having the additional advantage of providing a complete continuous posterior probability distribution of surface rain rate.

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.