Instance generators and test suites for the multiobjective quadratic assignment problem

We describe, and make publicly available, two problem instance generators for a multiobjective version of the well-known quadratic assignment problem (QAP). The generators allow a number of instance parameters to be set, including those controlling epistasis and inter-objective correlations. Based on these generators, several initial test suites are provided and described. For each test instance we measure some global properties and, for the smallest ones, make some initial observations of the Pareto optimal sets/fronts. Our purpose in providing these tools is to facilitate the ongoing study of problem structure in multiobjective (combinatorial) optimization, and its effects on search landscape and algorithm performance.

Integrable quadratic Hamiltonians on the Euclidean group of motions

In this paper, we discuss the problem of globally computing sub-Riemannian curves on the Euclidean group of motions SE(3). In particular, we derive a global result for special sub-Riemannian curves whose Hamiltonian satisfies a particular condition. In this paper, sub-Riemannian curves are defined in the context of a constrained optimal control problem. The maximum principle is then applied to this problem to yield an appropriate left-invariant quadratic Hamiltonian. A number of integrable quadratic Hamiltonians are identified. We then proceed to derive convenient expressions for sub-Riemannian curves in SE(3) that correspond to particular extremal curves. These equations are then used to compute sub-Riemannian curves that could potentially be used for motion planning of underwater vehicles.

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.

QUAGMIRE v1.3: a quasi-geostrophic model for investigating rotating fluids experiments

QUAGMIRE is a quasi-geostrophic numerical model for performing fast, high-resolution simulations of multi-layer rotating annulus laboratory experiments on a desktop personal computer. The model uses a hybrid finite-difference/spectral approach to numerically integrate the coupled nonlinear partial differential equations of motion in cylindrical geometry in each layer. Version 1.3 implements the special case of two fluid layers of equal resting depths. The flow is forced either by a differentially rotating lid, or by relaxation to specified streamfunction or potential vorticity fields, or both. Dissipation is achieved through Ekman layer pumping and suction at the horizontal boundaries, including the internal interface. The effects of weak interfacial tension are included, as well as the linear topographic beta-effect and the quadratic centripetal beta-effect. Stochastic forcing may optionally be activated, to represent approximately the effects of random unresolved features. A leapfrog time stepping scheme is used, with a Robert filter. Flows simulated by the model agree well with those observed in the corresponding laboratory experiments.

Voronoi, Delaunay, and Block-Structured Mesh Refinement for Solution of the Shallow-Water Equations on the Sphere

Alternative meshes of the sphere and adaptive mesh refinement could be immensely beneficial for weather and climate forecasts, but it is not clear how mesh refinement should be achieved. A finite-volume model that solves the shallow-water equations on any mesh of the surface of the sphere is presented. The accuracy and cost effectiveness of four quasi-uniform meshes of the sphere are compared: a cubed sphere, reduced latitude–longitude, hexagonal–icosahedral, and triangular–icosahedral. On some standard shallow-water tests, the hexagonal–icosahedral mesh performs best and the reduced latitude–longitude mesh performs well only when the flow is aligned with the mesh. The inclusion of a refined mesh over a disc-shaped region is achieved using either gradual Delaunay, gradual Voronoi, or abrupt 2:1 block-structured refinement. These refined regions can actually degrade global accuracy, presumably because of changes in wave dispersion where the mesh is highly nonuniform. However, using gradual refinement to resolve a mountain in an otherwise coarse mesh can improve accuracy for the same cost. The model prognostic variables are height and momentum collocated at cell centers, and (to remove grid-scale oscillations of the A grid) the mass flux between cells is advanced from the old momentum using the momentum equation. Quadratic and upwind biased cubic differencing methods are used as explicit corrections to a fast implicit solution that uses linear differencing.

Wavelets and the generalization of the variogram

The experimental variogram computed in the usual way by the method of moments and the Haar wavelet transform are similar in that they filter data and yield informative summaries that may be interpreted. The variogram filters out constant values; wavelets can filter variation at several spatial scales and thereby provide a richer repertoire for analysis and demand no assumptions other than that of finite variance. This paper compares the two functions, identifying that part of the Haar wavelet transform that gives it its advantages. It goes on to show that the generalized variogram of order k=1, 2, and 3 filters linear, quadratic, and cubic polynomials from the data, respectively, which correspond with more complex wavelets in Daubechies's family. The additional filter coefficients of the latter can reveal features of the data that are not evident in its usual form. Three examples in which data recorded at regular intervals on transects are analyzed illustrate the extended form of the variogram. The apparent periodicity of gilgais in Australia seems to be accentuated as filter coefficients are added, but otherwise the analysis provides no new insight. Analysis of hyerpsectral data with a strong linear trend showed that the wavelet-based variograms filtered it out. Adding filter coefficients in the analysis of the topsoil across the Jurassic scarplands of England changed the upper bound of the variogram; it then resembled the within-class variogram computed by the method of moments. To elucidate these results, we simulated several series of data to represent a random process with values fluctuating about a mean, data with long-range linear trend, data with local trend, and data with stepped transitions. The results suggest that the wavelet variogram can filter out the effects of long-range trend, but not local trend, and of transitions from one class to another, as across boundaries.

Mersenne numbers

These notes have been issued on a small scale in 1983 and 1987 and on request at other times. This issue follows two items of news. First, WaIter Colquitt and Luther Welsh found the 'missed' Mersenne prime M110503 and advanced the frontier of complete Mp-testing to 139,267. In so doing, they terminated Slowinski's significant string of four consecutive Mersenne primes. Secondly, a team of five established a non-Mersenne number as the largest known prime. This result terminated the 1952-89 reign of Mersenne primes. All the original Mersenne numbers with p < 258 were factorised some time ago. The Sandia Laboratories team of Davis, Holdridge & Simmons with some little assistance from a CRAY machine cracked M211 in 1983 and M251 in 1984. They contributed their results to the 'Cunningham Project', care of Sam Wagstaff. That project is now moving apace thanks to developments in technology, factorisation and primality testing. New levels of computer power and new computer architectures motivated by the open-ended promise of parallelism are now available. Once again, the suppliers may be offering free buildings with the computer. However, the Sandia '84 CRAY-l implementation of the quadratic-sieve method is now outpowered by the number-field sieve technique. This is deployed on either purpose-built hardware or large syndicates, even distributed world-wide, of collaborating standard processors. New factorisation techniques of both special and general applicability have been defined and deployed. The elliptic-curve method finds large factors with helpful properties while the number-field sieve approach is breaking down composites with over one hundred digits. The material is updated on an occasional basis to follow the latest developments in primality-testing large Mp and factorising smaller Mp; all dates derive from the published literature or referenced private communications. Minor corrections, additions and changes merely advance the issue number after the decimal point. The reader is invited to report any errors and omissions that have escaped the proof-reading, to answer the unresolved questions noted and to suggest additional material associated with this subject.

Evaluating a new LISFLOOD-FP formulation with data from the summer 2007 floods in Tewkesbury, UK

Two-dimensional flood inundation modelling is a widely used tool to aid flood risk management. In urban areas, where asset value and population density are greatest, the model spatial resolution required to represent flows through a typical street network (i.e. < 10m) often results in impractical computational cost at the whole city scale. Explicit diffusive storage cell models become very inefficient at such high resolutions, relative to shallow water models, because the stable time step in such schemes scales as a quadratic of resolution. This paper presents the calibration and evaluation of a recently developed new formulation of the LISFLOOD-FP model, where stability is controlled by the Courant–Freidrichs–Levy condition for the shallow water equations, such that, the stable time step instead scales linearly with resolution. The case study used is based on observations during the summer 2007 floods in Tewkesbury, UK. Aerial photography is available for model evaluation on three separate days from the 24th to the 31st of July. The model covered a 3.6 km by 2 km domain and was calibrated using gauge data from high flows during the previous month. The new formulation was benchmarked against the original version of the model at 20 m and 40 m resolutions, demonstrating equally accurate performance given the available validation data but at 67x faster computation time. The July event was then simulated at the 2 m resolution of the available airborne LiDAR DEM. This resulted in a significantly more accurate simulation of the drying dynamics compared to that simulated by the coarse resolution models, although estimates of peak inundation depth were similar.

Anharmonic force field of acetylene

The harmonic and anharmonic force field of acetylene has been determined in a least-squares calculation from recently determined data on the spectroscopic constants of various isotopic species (including the vibrational l-doubling constant). A general quadratic and cubic force field was used, but a constrained quartic force field containing only 8 of the 23 possible quartic constants. The results are discussed and compared with earlier work.

The anharmonic force field of HCN and HCP

The quadratic, cubic, and quartic force field of HCN has been calculated by a least squares refinement to fit the most recent observed data on the vibration-rotation constants of HCN, DCN and H13CN. All of the observed parameters are fitted within their standard errors of observation. The corresponding parameters for other isotopic species are calculated. For HCP and DCP the more limited data available have been fitted to an anharmonic force field using constraints based on comparison with HCN. Using this force field the zero-point rotational constants B0 have been corrected to obtain the equilibrium constants Be, and hence the equilibrium structure has been determined to be re(CH) = 1•0692(7)A, and re(CP) = 1•5398(2)A.

A potential energy surface for the ground state of formaldehyde, H2CO(1A1)

A model potential energy function for the ground state of H2CO has been derived which covers the whole space of the six internal coordinates. This potential reproduces the experimental energy, geometry and quadratic force field of formaldehyde, and dissociates correctly to all possible atom, diatom and triatom fragments. Thus there are good reasons for believing it to be close to the true potential energy surface except in regions where both hydrogen atoms are close to the oxygen. It leads to the prediction that there should be a metastable singlet hydroxycarbene HCOH which has a planar trans structure and an energy of 2•31 eV above that of equilibrium formaldehyde. The reaction path for dissociation into H2 + CO is predicted to pass through a low symmetry transition state with an activation energy of 4•8 eV. Both of these predictions are in good agreement with recently published ab initio calculations.

Puckering structure in the infrared spectrum of cyclobutane

The theory of rotational-pucker-vibrational transitions in the vibrational spectrum of cyclobutane is reviewed. Puckering sideband structure on the 1453 cm-1v14 infra-red fundamental of C4H8 has been observed and analysed, in terms of two slightly different puckering potential functions for the ground and the excited vibrational states. The results have been fitted to quartic-quadratic potential functions in the puckering coordinate, with a barrier to inversion of 503 cm-1 (1•44 kcal mole-1 = 6•02 kJ mole-1) in the ground state and 491 cm-1 in the excited state ν14 = 1. For reasonable assumptions about the reduced mass, the equilibrium dihedral angle of the C4 ring is determined to be about 35°, in agreement with previous estimates. Ueda and Shimanouchi's observations on the 2878 cm-1 C4H8 band have been re-analysed, and puckering sidebands have also been observed and analysed for the 1083 cm-1v14 infra-red fundamental of C4D8. Pure puckering transitions have been observed in the Raman spectrum of C4H8 vapour. All of these observations are shown to be consistent with the same ground state puckering potential function.