A domain decomposition algorithm for inverse welding problems

A mathematical model and a numerical scheme for the inverse determination of heat sources generated by means of a welding process is presented in this paper. The accuracy of the heat source retrieval is discussed.

A robust tri-state election algorithm for scalable applications

Existing election algorithms suffer limited scalability. This limit stems from the communication design which in turn stems from their fundamentally two-state behaviour. This paper presents a new election algorithm specifically designed to be highly scalable in broadcast networks whilst allowing any processing node to become coordinator with initially equal probability. To achieve this, careful attention has been paid to the communication design, and an additional state has been introduced. The design of the tri-state election algorithm has been motivated by the requirements analysis of a major research project to deliver robust scalable distributed applications, including load sharing, in hostile computing environments in which it is common for processing nodes to be rebooted frequently without notice. The new election algorithm is based in-part on a simple 'emergent' design. The science of emergence is of great relevance to developers of distributed applications because it describes how higher-level self-regulatory behaviour can arise from many participants following a small set of simple rules. The tri-state election algorithm is shown to have very low communication complexity in which the number of messages generated remains loosely-bounded regardless of scale for large systems; is highly scalable because nodes in the idle state do not transmit any messages; and because of its self-organising characteristics, is very stable.

A multilevel algorithm for force-directed graph-drawing

We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G0, G1, …, GL. The coarsest graph, GL, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for Gl is taken from its coarser and smaller child graph, Gl+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

A distributed algorithm for European options with nonlinear volatility

A distributed algorithm is developed to solve nonlinear Black-Scholes equations in the hedging of portfolios. The algorithm is based on an approximate inverse Laplace transform and is particularly suitable for problems that do not require detailed knowledge of each intermediate time steps.

An improved approximation algorithm for the two-machine flow shop scheduling problem with an interstage transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables

An approximation algorithm for the two-machine flow shop with a single transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables.

An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

An algorithm for total variation inpainting based on nonlinear multi-grid methods

Image inpainting refers to restoring a damaged image with missing information. The total variation (TV) inpainting model is one such method that simultaneously fills in the regions with available information from their surroundings and eliminates noises. The method works well with small narrow inpainting domains. However there remains an urgent need to develop fast iterative solvers, as the underlying problem sizes are large. In addition one needs to tackle the imbalance of results between inpainting and denoising. When the inpainting regions are thick and large, the procedure of inpainting works quite slowly and usually requires a significant number of iterations and leads inevitably to oversmoothing in the outside of the inpainting domain. To overcome these difficulties, we propose a solution for TV inpainting method based on the nonlinear multi-grid algorithm.

Coccolithophore bloom detection in the north east Atlantic using SeaWiFS: Algorithm description, application and sensitivity analysis

Coccolithophores are the largest source of calcium carbonate in the oceans and are considered to play an important role in oceanic carbon cycles. Current methods to detect the presence of coccolithophore blooms from Earth observation data often produce high numbers of false positives in shelf seas and coastal zones due to the spectral similarity between coccolithophores and other suspended particulates. Current methods are therefore unable to characterise the bloom events in shelf seas and coastal zones, despite the importance of these phytoplankton in the global carbon cycle. A novel approach to detect the presence of coccolithophore blooms from Earth observation data is presented. The method builds upon previous optical work and uses a statistical framework to combine spectral, spatial and temporal information to produce maps of coccolithophore bloom extent. Validation and verification results for an area of the north east Atlantic are presented using an in situ database (N = 432) and all available SeaWiFS data for 2003 and 2004. Verification results show that the approach produces a temporal seasonal signal consistent with biological studies of these phytoplankton. Validation using the in situ coccolithophore cell count database shows a high correct recognition rate of 80% and a low false-positive rate of 0.14 (in comparison to 63% and 0.34 respectively for the established, purely spectral approach). To guide its broader use, a full sensitivity analysis for the algorithm parameters is presented.

Data processing of remotely sensed airborne hyperspectral data using the Airborne Processing Library (APL): Geocorrection algorithm descriptions and spatial accuracy assessment

Remote sensing airborne hyperspectral data are routinely used for applications including algorithm development for satellite sensors, environmental monitoring and atmospheric studies. Single flight lines of airborne hyperspectral data are often in the region of tens of gigabytes in size. This means that a single aircraft can collect terabytes of remotely sensed hyperspectral data during a single year. Before these data can be used for scientific analyses, they need to be radiometrically calibrated, synchronised with the aircraft's position and attitude and then geocorrected. To enable efficient processing of these large datasets the UK Airborne Research and Survey Facility has recently developed a software suite, the Airborne Processing Library (APL), for processing airborne hyperspectral data acquired from the Specim AISA Eagle and Hawk instruments. The APL toolbox allows users to radiometrically calibrate, geocorrect, reproject and resample airborne data. Each stage of the toolbox outputs data in the common Band Interleaved Lines (BILs) format, which allows its integration with other standard remote sensing software packages. APL was developed to be user-friendly and suitable for use on a workstation PC as well as for the automated processing of the facility; to this end APL can be used under both Windows and Linux environments on a single desktop machine or through a Grid engine. A graphical user interface also exists. In this paper we describe the Airborne Processing Library software, its algorithms and approach. We present example results from using APL with an AISA Eagle sensor and we assess its spatial accuracy using data from multiple flight lines collected during a campaign in 2008 together with in situ surveyed ground control points.

Absorption-based algorithm of primary production for total and size-fractionated phytoplankton in coastal waters

Most satellite models of production have been designed and calibrated for use in the open ocean. Coastal waters are optically more complex, and the use of chlorophyll a (chl a) as a first-order predictor of primary production may lead to substantial errors due to significant quantities of coloured dissolved organic matter (CDOM) and total suspended material (TSM) within the first optical depth. We demonstrate the use of phytoplankton absorption as a proxy to estimate primary production in the coastal waters of the North Sea and Western English Channel for both total, micro- and nano+pico-phytoplankton production. The method is implemented to extrapolate the absorption coefficient of phytoplankton and production at the sea surface to depth to give integrated fields of total and micro- and nano+pico-phytoplankton primary production using the peak in absorption coefficient at red wavelengths. The model is accurate to 8% in the Western English Channel and 22% in this region and the North Sea. By comparison, the accuracy of similar chl a based production models was >250%. The applicability of the method to autonomous optical sensors and remotely sensed aircraft data in both coastal and estuarine environments is discussed.

Evaluating the SEVIRI Fire Thermal Anomaly Detection Algorithm across the Central African Republic Using the MODIS Active Fire Product

Satellite-based remote sensing of active fires is the only practical way to consistently and continuously monitor diurnal fluctuations in biomass burning from regional, to continental, to global scales. Failure to understand, quantify, and communicate the performance of an active fire detection algorithm, however, can lead to improper interpretations of the spatiotemporal distribution of biomass burning, and flawed estimates of fuel consumption and trace gas and aerosol emissions. This work evaluates the performance of the Spinning Enhanced Visible and Infrared Imager (SEVIRI) Fire Thermal Anomaly (FTA) detection algorithm using seven months of active fire pixels detected by the Moderate Resolution Imaging Spectroradiometer (MODIS) across the Central African Republic (CAR). Results indicate that the omission rate of the SEVIRI FTA detection algorithm relative to MODIS varies spatially across the CAR, ranging from 25% in the south to 74% in the east. In the absence of confounding artifacts such as sunglint, uncertainties in the background thermal characterization, and cloud cover, the regional variation in SEVIRI's omission rate can be attributed to a coupling between SEVIRI's low spatial resolution detection bias (i.e., the inability to detect fires below a certain size and intensity) and a strong geographic gradient in active fire characteristics across the CAR. SEVIRI's commission rate relative to MODIS increases from 9% when evaluated near MODIS nadir to 53% near the MODIS scene edges, indicating that SEVIRI errors of commission at the MODIS scene edges may not be false alarms but rather true fires that MODIS failed to detect as a result of larger pixel sizes at extreme MODIS scan angles. Results from this work are expected to facilitate (i) future improvements to the SEVIRI FTA detection algorithm; (ii) the assimilation of the SEVIRI and MODIS active fire products; and (iii) the potential inclusion of SEVIRI into a network of geostationary sensors designed to achieve global diurnal active fire monitoring.

Metocean Comparisons of Jason-2 and AltiKa—A Method to Develop a New Wind Speed Algorithm

As well as range, the AltiKa altimeter provides estimates of wave height, Hs and normalized backscatter, s0, that need to be assessed prior to statistics based on them being included in climate databases. An analysis of crossovers with the Jason-2 altimeter shows AltiKa Hs values to be biased high by only »0.05m, with a standard deviation (s.d.) of »0.1m for seven-point averages. AltiKa’s s 0 values are 2.5–3 dB less than those from Jason-2, with a s.d. of »0.3 dB, with these relatively large mismatches to be expected as AltiKa measures a different part of the spectrum of sea surface roughness. A new wind speed algorithm is developed through matchinghistogram of s0 values to that for Jason-2 wind speeds. The algorithm is robust to the use of short durations of data, with a consistency at roughly the 0.1 m/s level. Incorporation of Hs as a secondary input reduces the assessed error at crossovers from 0.82 m/s to 0.71 m/s. A comparison across all altimeter frequencies used to date demonstrates that the lowest wind speeds preferentially develop the shortest scales of roughness.