A matheuristic approach with nonlinear subproblems for large-scale packing of ellipsoids

The problem of packing ellipsoids in the three-dimensional space is considered in the present work. The proposed approach combines heuristic techniques with the resolution of recently introduced nonlinear programming models in order to construct solutions with a large number of ellipsoids. The introduced approach is able to pack identical and non-identical ellipsoids within a variety of containers. Moreover, it allows the inclusion of additional positioning constraints. This fact makes the proposed approach suitable for constructing large-scale solutions with specific positioning constraints in which density may not be the main issue. Numerical experiments illustrate that the introduced approach delivers good quality solutions with a computational cost that scales linearly with the number of ellipsoids; and solutions with more than a million ellipsoids are exhibited.     

Polynomial algorithms for (integral) maximum two-flows in vertex edge-capacitated planar graphs

In this paper we study the maximum two-flow problem in vertex- and edge-capacitated undirected ST₂-planar graphs, that is, planar graphs where the vertices of each terminal pair are on the same face. For such graphs we provide an O(n) algorithm for finding a minimum two-cut and an O(n log n) algorithm for determining a maximum two-flow and show that the value of a maximum two-flow equals the value of a minimum two-cut. We further show that the flow obtained is half-integral and provide a characterization of edge and vertex capacitated ST₂-planar graphs that guarantees a maximum two-flow that is integral. By a simple variation of our maximum two-flow algorithm we then develop, for ST₂-planar graphs with vertex and edge capacities, an O(n log n) algorithm for determining an integral maximum two-flow of value not less than the value of a maximum two-flow minus one.     

Integration and Optimization of Multivariate Polynomials by Restriction onto a Random Subspace

We consider the problem of efficient integration of an n-variate polynomial with respect to the Gaussian measure in ℝⁿ and related problems of complex integration and optimization of a polynomial on the unit sphere. We identify a class of n-variate polynomials f for which the integral of any positive integer power f^p over the whole space is well approximated by a properly scaled integral over a random subspace of dimension O(log n). Consequently, the maximum of f on the unit sphere is well approximated by a properly scaled maximum on the unit sphere in a random subspace of dimension O(log n). We discuss connections with problems of combinatorial counting and applications to efficient approximation of a hafnian of a positive matrix.     

High resolution instrumentation system for fibre-Bragg grating aerospace sensors

A passive technique for high-resolution detection of the wavelength of peak reflection from fibre Bragg grating (FBG) sensors is presented. The approach, based on a de-convolution of the FBG spectrum and the spectrometer resolution, essentially overcomes the low spectral resolution (≈0.1 nm) associated with commercial spectrometers employing CCD detection. The performance of two algorithms, the Centroid Detection algorithm (CDA) and the least squares method (LSQ), are compared. The LSQ algorithm offers resolution enhancement of at least two orders of magnitude and is shown to be independent of the FBG intensity and bandwidth over a broad range.     

The powers and pitfalls of algorithmic knowledge: a case study

This study examines one child's use of computational procedures over a period of 3 years in an urban elementary school where teachers were using a standards-based curriculum. From a sociocultural perspective, the use of standard algorithms to solve mathematical problems is viewed as a cultural tool that both enables and constrains particular practices. As this student appropriated and mastered procedures for addition, subtraction, multiplication and division, she could solve problems that involved fairly straightforward computations or where she could easily model the action to determine an appropriate computation. At the same time, her use of these algorithms, along with other readily available tools, such as her fingers or multiplication tables, constrained her ability to reflect on the tens-structure of the number system, an effect that had serious consequences for her overall mathematical achievement. The results of this study suggest that even when not directly introduced, algorithms have such strong currency that they can mediate more reform-oriented instruction.     

Markov games with incomplete information

We consider zero-sum Markov games with incomplete information. Here, the second player is never informed about the current state of the underlying Markov chain. The existence of a value and of optimal strategies for both players is shown. In particular, we present finite algorithms for computing optimal strategies for the informed and uninformed player. The algorithms are based on linear programming results.     

Turbulent flow computations on 3D unstructured grids

An edge-based finite element method is presented for the simulation of compressible turbulent flows on unstructured tetrahedral grids. A two equation k–ω turbulence model is employed and the standard Galerkin approach is used for spatial discretisation. Stabilisation of the resulting procedure is achieved by the addition of an appropriate diffusion. An explicit multistage time-stepping scheme is used to advance the solution in time to steady state. The performance of the algorithm is demonstrated for the simulation of a high Reynolds number transonic separated flow over a wing.     

Isotopic Implicit Surface Meshing

This paper addresses the problem of piecewise linear approximation of implicit surfaces. We first give a criterion ensuring that the zero-set of a smooth function and the one of a piecewise linear approximation of it are isotopic. Then, we deduce from this criterion an implicit surface meshing algorithm certifying that the output mesh is isotopic to the actual implicit surface. This is the first algorithm achieving this goal in a provably correct way.