Dynamic programming (DP) approaches, in particular value iteration, is often seen as a method to derive optimal policies in inventory management. The challenge in this approach is to deal with an increasing state space when handling realistic problems. As a large part of world food production is thrown out due to its perishable character, a motivation exists to have a good look at order policies in retail. Recently, investigation has been introduced to consider substitution of one product by another, when one is out of stock. Taking this tendency into account in a policy requires an increasing state space. Therefore, we investigate the potential of using GPU platforms in order to derive optimal policies when the number of products taken into account simultaneously is increasing. First results show the potential of the GPU approach to accelerate computation in value iteration for DP.

Summary The resolution of the 3D Helmholtz equation is required in the development of models related to a wide range of scientific and technological applications. For solving this equation in complex arithmetic, the biconjugate gradient (BCG) method is one of the most relevant solvers. However, this iterative method has a high computational cost because of the large sparse matrix and the vector operations involved. In this paper, a specific BCG method, adapted for the regularities of the Helmholtz equation is presented. This BCG is based on the implementation of a novel format (named ‘Regular Format’) that allows the storage of the large sparse matrix involved in the sparse matrix vector product in a compact form. The contribution of this work is twofold: (1) decreasing the memory requirements of the 3D Helmholtz equation using the ‘Regular Format’ and (2) speeding up the resolution of the equation using high performance computing resources. A hybrid Message Passing Interface (MPI)‐graphics processing unit CUDA GPU parallelization that is capable of solving complex problems in short time has carried out (Fast‐Helmholtz). Fast‐Helmholtz combines optimizations at Message Passing Interface and GPU levels to reduce communications costs and to improve the exploitation of GPU architecture. This strategy makes it possible to extend the dimension of the Helmholtz problem to be solved, thanks to the relevant reduction of memory requirements and runtime. Copyright © 2014 John Wiley & Sons, Ltd.

Sparse matrix matrix (SpMM) multiplication is involved in a wide range of scientific and technical applications. The computational requirements for this kind of operation are enormous, especially for large matrices. This paper analyzes and evaluates a method to efficiently compute the SpMM product in a computing environment that includes graphics processing units (GPUs). Some libraries to compute this matricial operation can be found in the literature. However, our strategy (FastSpMM) outperforms the existing approaches because it combines the use of the ELLPACK-R storage format with the exploitation of the high ratio computation/memory access of the SpMM operation and the overlapping of CPU–GPU communications/computations by Compute Unified Device Architecture streaming computation. In this work, FastSpMM is described and its performance evaluated with regard to the CUSPARSE library (supplied by NVIDIA), which also includes routines to compute SpMM on GPUs. Experimental evaluations based on a representative set of test matrices show that, in terms of performance, FastSpMM outperforms the CUSPARSE routine as well as the implementation of the SpMM as a set of sparse matrix vector products.

We focused on the joint exploitation of satellite and ground-based technologies in order to understand the kinematic behavior of landslides and subsidence phenomena relevant to different test sites in Europe. In this context, we efficiently exploited C-band and X-band satellite and ground-based SAR data for the investigation of the temporal and spatial pattern of ground deformations caused by natural and human-induced hazards. The present work has been conducted within the FP7-EU DORIS project.

In general, solving Global Optimization (GO) problems by Branch-and-Bound (B&B) requires a huge computational capacity. Parallel execution is used to speed up the computing time. As in this type of algorithms, the foreseen computational workload (number of nodes in the B&B tree) changes dynamically during the execution, the load balancing and the decision on additional processors is complicated. We use the term left-over to represent the number of nodes that still have to be evaluated at a certain moment during execution. In this work, we study new methods to estimate the left-over value based on the observed amount of pruning. This provides information about the remaining running time of the algorithm and the required computational resources. We focus on their use for interval B&B GO algorithms.

Interval branch-and-bound (B&B) algorithms are powerful methods which look for guaranteed solutions of global optimisation problems. The computational effort needed to reach this aim, increases exponentially with the problem dimension in the worst case. For separable functions this effort is less, as lower dimensional sub-problems can be solved individually. The question is how to design specific methods for cases where the objective function can be considered separable, but common variables occur in the sub-problems. This paper is devoted to establish the bases of B&B algorithms for separable problems. New B&B rules are presented based on derived properties to compute bounds. A numerical illustration is elaborated with a test-bed of problems mostly generated by combining traditional box constrained global optimisation problems, to show the potential of using the derived theoretical basis.

We describe the minimum volume simplex enclosure problem (MVSEP), which is known to be a global optimization problem, and further investigate its multimodality. The problem is a basis for several (unmixing) methods that estimate so-called endmembers and fractional values in a linear mixing model. We describe one of the estimation methods based on MVSEP. We show numerically that using nonlinear optimization local search leads to the estimation results aimed at. This is done using examples, designing instances and comparing the outcomes with a maximum volume enclosing simplex approach which is used frequently in unmixing data.

Blending algorithms aim for solving the problem of determining the mixture of raw materials in order to obtain a cheap and feasible recipe with the smallest number of raw materials. An algorithm that solves this problem for two products, where available raw material is limited, has two phases. The first phase is a simplicial branch-and-bound algorithm which determines, for a given precision, a Pareto set of solutions of the bi-blending problem as well as a subspace of the initial space where better feasible solutions (with more precision) can be found. The second phase basically consists in an exhaustive reduction of the mentioned subspace by deleting simplicial subsets that do not contain solutions. This second phase is useful for future refinement of the solutions. Previous work only focused on the first phase neglecting the second phase due to computational burden. With this in mind, we study the parallelization of the different phases of the sequential bi-blending algorithm and focus on the most time consuming phase, analyzing the performance of several strategies.

A wide range of applications in engineering and scientific computing are based on the computation of matrices products, where one of them is sparse. The computational requirements of these operations are very high when dimensions of the matrices increase. The goal of this work is the acceleration of the sparse matrix matrix product (SpMM) on Graphics Processing Units (GPUs). The operation SpMM can be computed by a set of sparse matrix vector operations (SpMV). However, this approach does not reach optimal performance because it cannot benefit from the large value of the ratio computation/memory access associated to the SpMM operation. In this work a routine called FastSpMM is described and its performance evaluated. FastSpMM can be considered as an extension of the ELLRT routine to compute SpMV on GPUs which is based on the ELLPACK-R storage format for sparse matrices. FastSpMM combines the high ratio computation/memory access with the advantages of ELLR-T to exploit the GPU architecture. The CUSPARSE library, supplied by NVIDIA, which also includes routines to compute SpMM on GPUs is used in this work as a reference for performance comparison. Experimental evaluations based on a representative set of test matrices show that FastSpMM outperforms the corresponding CUSPARSE routine in terms of performance.

Spectral unmixing is an important technique for hyperspectral data exploitation, in which a mixed spectral signature is decomposed into a collection of spectrally pure constituent spectra, called endmembers, and a set of correspondent fractions, or abundances, that indicate the proportion of each endmember present in the mixture. Over the last years, several algorithms have been developed for automatic or semiautomatic endmember extraction. Some available approaches assume that the input data set contains at least one pure spectral signature for each distinct material and further conduct a search for the most spectrally pure signatures in the high-dimensional space spanned by the hyperspectral data. Among these approaches, those aimed at maximizing the volume of the simplex that can be formed using available spectral signatures have found wide acceptance. However, the presence of spectrally pure constituents is unlikely in remotely sensed hyperspectral scenes due to spatial resolution, mixing phenomena, and other considerations. In order to address this issue, other available algorithms have been developed to generate virtual endmembers (not necessarily present among the input data samples) by finding the simplex with minimum volume that encloses all available observations. In this paper, we discuss maximum-volume versus minimum-volume enclosing solutions and further develop a novel algorithm in the latter category which incorporates the fractional abundance estimation as an internal step of the endmember searching process (i.e., it does not require an external method to produce endmember fractional abundances). The method is based on iteratively enclosing the observations in a lower dimensional space and removing observations that are most likely not to be enclosed by the simplex of the endmembers to be estimated. The performance of the algorithm is investigated and compared to that of other algorithms (with and without the pure pixel assumption) using synthetic and real hyperspectral data sets collected by a variety of hyperspectral imaging instruments.

Electron tomography (ET) allows elucidation of the three-dimensional (3D) structure of large complex biological specimens at molecular resolution. In order to achieve such resolution levels, large projection images have to be used to compute the 3D reconstructions. Tomographic reconstruction on this scale requires a tremendous use of computational resources and considerable processing time. Traditionally, parallel and distributed systems, and more recently GPUs, have been the key to cope with this demanding procedure. This work demonstrates that full exploitation of the impressive processing power within modern multi-core processors make them a feasible alternative. The use of parallel computing, vectorization and code optimization allows ultra-fast tomographic reconstructions on standard computers, even outperforming GPUs. Our results confirm that modern processors succeed in providing reconstructed volumes in very little time, which enables them for real-time ET.

Branch and Bound (B&B) algorithms are highlyparallelizable but they are irregular and dynamic load balancing techniques have been used to avoid idle processors. In previous work, authors use a dynamic number of threads at run time, which depends on the measured performance of the application for just one interval B&B algorithm running on the system. In this way, load balancing is achieved by thread generation decisions. In this work, we extend the study of these models to non-dedicated systems. In order to have a controlled test bed and comparable results, several instances of the interval global optimization algorithm are executed in the system, with the same model and problem to solve. Therefore, a non-dedicated system is simulated because the execution of one application affects the execution of the other instances. This paper discusses different methods and models to decide when a thread should be created. Experiments show which of the proposed methods performs best in terms of maximum running time per application, using the fewest running threads. Following this parallel programming methodology, which is well suited for other B&B codes, applications can adapt their parallelism level to their performance and load of the system(at run time). This work represents a step forward towards increasing the performance of parallel algorithm running inn on-dedicated and heterogeneous systems. The adaptive model discussed in this work is able to reduce the overall execution time for a set of instances of the same application running simultaneously. It also exempts the user from specifying the number of threads each application should use.

The aim of this work is to study the Simplex Cover (SC) problem, which is to determine whether a given simplex is covered by spheres centered at its vertices. We show that the SC problem is equivalent to a global optimization problem. We investigate its characteristics.

This papers studies a novel prefetching scheme for the remote browsing of sequences of high resolution JPEG 2000 images. Using this scheme, an user is able to select randomly any of the remote images for its analysis, repeating this process with other images after some undefined time. Our solution has been proposed in a low bit-rate communication context where the complete transmission of any of the images for its lossless recovery should take too much time for an interactive visualization. For this reason, quality scalability is used in order to minimize the decoding latency. Frequently, the user can also play a "video'', moving sequentially on the neighbour (consecutive in time over previous or following) images of the currently displayed one. With the objective of hiding also the link latency, the proposed data scheduler transmits in parallel data of the image that it is currently displayed and data of the rest of the temporally adjacent images. This scheduler uses a model based on the quality progression of the image in order to estimate which percentage of the bandwidth is dedicated to prefetch data. Our experimental results prove that a significant benefit can be achieved in terms of both subjective quality and responsiveness by means of prefetching.

Spectral unmixing is an important task for remotely sensed hyperspectral data exploitation. Linear spectral unmixing relies on two main steps: 1) identification of pure spectral constituents (endmembers), and 2) end member abundance estimation in mixed pixels. One of the main problems concerning the identification of spectral endmembers is the lack of pure spectral signatures in real hyperspectral data due to spatial resolution and mixture phenomena happening at different scales. In this paper, we present a new method for endmember estimation which does not assume the presence of pure pixels in the input data. The method minimizes the volume of an enclosing simplex in the reduced space while estimating the fractional abundance of vertices in simultaneous fashion, as opposed to other volume-based approaches such as N-FINDR which inflate the simplex of maximumvolume that can be formed using available image pixels. Our experimental results and comparisons to other endmember extraction algorithms indicate promising performance of the method in the task of extracting endmembers from real hyperspectral data. In our experiments, we use laboratory-simulated forest scenes with known endmembers and fractional abundances due to their acquisition in a controlled environment using a real hyperspectral imaging instrument.

Electron tomography (ET) allows elucidation of the three-dimensional (3D) structure of large complex biological specimens at molecular resolution. In order to achieve such resolution levels, large projection images have to be used to compute the 3D reconstructions. Tomographic reconstruction on this scale requires a tremendous use of computational resources and a considerable processing time. In this work, we present and evaluate a highly optimized implementation of the Weighted Back-Projection reconstruction algorithm. Briefly, optimizations made to the code comprise (1) vector processing with SSE (Streaming SIMD Extensions) instructions, (2) an efficient use of cache memory, (3) to take advantage of the inherent image symmetry, (4) to use the FFTW (Fastest Fourier Transform in the West) library for image filtering, (5) to use regions of interest and last, but not least, (6) a wide range of minor optimizations like some data pre-calculations or an instruction level parallelism improvement. We have evaluated the method on tomographic reconstructions of several datasets and on two computing platforms. The results show that our version speeds up the method by a factor around 14 or 16, depending on the platform.

SUMMARY: Interpretation of electron tomograms is difficult due to the high noise levels. Thus, denoising techniques are needed to improve the signal-to-noise ratio. XMSF (Microscopy Mean Shift Filtering) is a fast, user-friendly application that succeeds in filtering noise while preserving the structures of interest. It is based on the extension to 3D of a method widely applied in other image processing fields under very different scenarios. XMSF has been tested for a variety of tomograms, showing a great potential to become a state-of-the-art filtering program in electron tomography. Applied iteratively, the algorithm yields pre-segmented volumes facilitating posterior segmentation tasks. Moreover, execution times remain low thanks to parallel computing techniques to exploit current multicore computers. AVAILABILITY: http://sites.google.com/site/xmsfilter/

A continuous location problem in which a firm wants to set up two or more new facilities in a competitive environment is considered. Other facilities offering the same product or service already exist in the area. Both the locations and the qualities of the new facilities are to be found so as to maximize the profit obtained by the firm. This is a global optimization problem, with many local optima. In this paper we analyze several approaches to solve it, namely, three multistart local search heuristics, a multistart simulated annealing algorithm, and two variants of an evolutionary algorithm. Through a comprehensive computational study it is shown that the evolutionary algorithms are the heuristics that provide the best solutions. Furthermore, using a set of problems for which the optimal solutions are known, only the evolutionary algorithms were able to find the optimal solutions for all the instances. The evolutionary strategies presented in this paper can be easily adapted to handle other continuous location problems.

Electron tomography allows elucidation of the three-dimensional (3D) structure of large complex biological specimens at molecular resolution. In order to achieve such resolution levels, large projection images have to be used to compute the 3D reconstructions. Tomographic reconstruction on this scale requires a tremendous use of computational resources and considerable processing time. In this work, we present and evaluate a vector approach for fast 3D reconstruction that takes advantage of the multimedia extensions in modern processors. We have implemented the standard 3D reconstruction method, weighted backprojection, using the Streaming SIMD Extensions (SSE). We have evaluated the method on tomographic reconstruction of several datasets of various sizes on a computing platform based on Intel Xeon processor. The results show that our approach speeds up the method by a factor of 3.

This paper describes and analyzes JPIP-W, an innovative proposal for the interactive transmission of JPEG2000 images on the Internet. JPIP-W is an extension of JPIP, the current JPEG protocol proposed for interactive JPEG2000 image browsing. One of the JPIP characteristics of greatest interest is its ability to use the Web for retrieving images. However, JPIP is unable to exploit the large infrastructure of today's Web caching systems (proxies), used to reduce response time and network traffic. To overcome this drawback, JPIP-W defines a new server-client interaction consisting of splitting JPEG2000 images into data blocks that can be cached by the proxies. These blocks can be shared among several clients, allowing fast recovery of some portions of the images. Experimental results demonstrate that JPIP-W significantly reduces JPIP retrieving times.

UNLABELLED: Electron tomography is the leading technique to elucidate the structure of complex biological specimens. Due to the resolution needs, huge reconstructions are required. Grid computing has the potential to face the significant computational demands involved. However, there are a number of key issues, such as stability or difficult user-grid interaction, that currently preclude fully exploitation of its potential. EGEETomo is a user-friendly application that facilitates the interaction with the grid for the non-specialized user and automates job submission and supervision. In addition, EGEETomo is supplied with an automated fault recovery mechanism, which is key to make all the work transparent to the user. EGEETomo significantly accelerates tomographic reconstruction by exploiting the computational resources in the EGEE grid with minimal user intervention. AVAILABILITY: http://www.ace.ual.es/~jrbcast/EGEETomo.tar.gz

This article describes and analyzes the parallelization of the Anisotropic Nonlinear Diffusion (AND) for filtering 3D images. AND is one of the most powerful denoising techniques in the field of computer vision. This technique consists in resolving the equation of diffusion tightly coupled with a massive set of eigensystems. Denoising large 3D images in biomedicine and structural cellular biology by AND has a high computational cost. In this work, we propose a portable and efficient parallel implementation of AND based on a hybrid paradigm that combines (1) the message passing model and (2)the shared address space model. The proposed parallel implementation has been evaluated on a cluster of SMPs based on a UMA Uniform Memory access. The evaluation results show that the hybrid model is more suitable for this kind of platforms.

Computer games follow a scheme of continuous simulation, coupling the rendering phase and the simulation phase. That way of operation has disadvantages that can be avoided using a discrete event simulator as a game kernel. This paper proposes to integrate a discrete event simulator (DESK) to manage the videogames events. The videogame kernel used is Fly3D. The new kernel is called DFlySD. It allows a discrete event simulation scheme and the rendering and simulation phase independence. The integration objective has been to maintain the FlySD main structure and functionality, changing only the events management. The videogames objects behavior and interconnection is modeled by message passing. Maintaining the videogame quality, the videogames created using DFlySD allow reducing the computer power used to execute it. That allows to execute the videogame in computers with less computing power or to improve the game quality

Three-Dimensional Electron Microscopy (3DEM) has turned out to be a major player in structural proteomics. In 3DEM, tens of thousands of EM images from a macromolecule at different views are combined to derive its structure by means of a 3D reconstruction algorithm. However, for an optimal reconstruction, the most suitable algorithm has to be used and its parameters have to be tuned for the macromolecule under study and the experimental conditions found. The use of phantoms is central to objective comparison of reconstruction algorithms and optimization of their parameters. Phan3D is a tool intended to provide a fully visual and interactive environment that facilitates the design of phantoms resembling biological specimens in 3DEM. Phan3D has been developed as an alternative to the tedious, error-prone and old-fashioned phantom design that is based on hand-written text description files.

This work addresses the application of blob-based series expansion methods in structure determination of macromolecules from the perspective of computational speed and convergence rate. This work explores the use of traditional series expansion methods, such as algebraic reconstruction techniques, as well as other very recently developed methods: such as averaging sequential strings or component averaging methods characterized by a really fast convergence, achieving least-squares solutions in a few iterations.

This paper studies a progressive image transmission technique over waveform channels. The channel optimized vector quantization codec (COVQ) (Farvardin and Vaishampayan 1991) is applied to the image wavelet coefficients creating a robust progressive image transmission technique that mitigates the effects of a noisy channel on the reconstructed image. In order to evaluate the performance of our proposal, a Gaussian and slow-fading Rayleigh channel model, with several different values of channel signal to noise ratio (CSNR) were simulated in our experiments. Examples show a significant visual improvement of our application compared to other progressive image transmission techniques.

A new approach to the detection of shapes under global deformations is presented. The algorithm is based in the combination of a generalized Hough transform (GHT) and an universal evolutionary global optimizer (UEGO). This method exploits the invariant characteristics to rotation, scale and displacement of the GHT to detect shapes deformed by a global deformation model, and without an initial positioning of the template. The GHT is used as an objective function for the UEGO, an optimizer that is able to find multiple optima with a low computational cost.

In this work, a practical implementation of two parallel thinning algorithms on a multicomputer system are described. The solution has been conceived for a multiprocessor using the SPMD (single program multiple data) programming model. Our main goal is intended to describe our experiences on data partition/distribution among processors for parallel thinning algorithms as a representative type of algorithm where communications take place between neighbor processors and the work load for each processor depends on the input data. It will be shown how the efficiency of the parallel implementation can be improved through the application of a preprocess. This preprocess is based on the analysis of the work load balance. An analysis of the communication cost is also made. Although the results shown here are concerned with the implementations of two parallel thinning algorithms we think that our proposal about data distribution is general and useful for a wide set of algorithms in the field of image processing. Copyright © 2000 John Wiley & Sons, Ltd.

This article is concerned with the use of iterative methods for image reconstruction from projections in 3D cone beam emission tomography. It is aimed at the analysis of some of the parameters which likely play an important role in the accuracy of the results. These parameters are related to three stages of the global acquisition/reconstruction procedure; the tomographic data acquisition geometry, the sampling frequency of the projection data and the reconstruction algorithm.

In this paper an efficient parallel implementation of the Lanczos method for matrix tridlagonalization is described.This work is restricted to sparse matrices where the work load unbalance problem must be solved in order to optimize the efficiency of the parallel implementation.A new strategy for data dktribution (called Pivoting Block) is purposed in this work. Efficiency of the parallelLanczos method for sparse matrices using Pivoting Block is slightly improved compared to others data dktribution strategies.