Business process management with the user requirements notation

A number of recent initiatives in both academia and industry have sought to achieve improvements in e-businesses through the utilization of Business Process Management (BPM) methodologies and tools. However there are still some inadequacies that need to be addressed when it comes to achieving alignment between business goals and business processes. The User Requirements Notation (URN), recently standardized by ITU-T, has some unique features and capabilities beyond what is available in other notations that can help address alignment issues. In this paper, a URN-based framework and its supporting toolset are introduced which provide business process monitoring and performance management capabilities integrated across the BPM lifecycle. The framework extends the URN notation with Key Performance Indicators (KPIs) and other concepts to measure and align processes and goals. An example process for controlling access to a healthcare data warehouse is used to illustrate and evaluate the framework. Early results indicate the feasibility of the approach.     

Recursive formulations for multibody systems with frictional joints based on the interaction between bodies

In practice, the clearances of joints in a great number of mechanical systems are well under control. In these cases, some of the existing methods become unpractical because of the little differences in the order of magnitude between relative movements and computational errors. Assuming that the effects of impacts are negligible, we proved that both locations and forces of contacts in joints can be fully determined by parts of joint reaction forces. Based on this fact, a method particularly suited for multibody systems possessing frictional joints with tiny clearances is presented. In order to improve the efficiency of computation, recursive formulations are proposed based on the interactions between bodies. The proposed recursive formulations can improve the computation of joint reaction forces. With the methodology presented in this paper, not only the motion of bodies in a multibody system but also the details about the contacts in joints, such as forces of contacts and locations of contact points, can be obtained. Even with the assumption of impact free, the instants of possible impacts can be detected without relying upon any ambiguous parameters, as indicated by numerical examples in this paper.     

Network Design with Edge-Connectivity and Degree Constraints

We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer k≥1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex v∈V is equal to b(v). This problem generalizes metric TSP. In this paper, we show that the problem admits a ρ-approximation algorithm if b(v)≥2, v∈V, where ρ=2.5 if k is even, and ρ=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.     

Searching for Complex Human Activities with No Visual Examples

We describe a method of representing human activities that allows a collection of motions to be queried without examples, using a simple and effective query language. Our approach is based on units of activity at segments of the body, that can be composed across space and across the body to produce complex queries. The presence of search units is inferred automatically by tracking the body, lifting the tracks to 3D and comparing to models trained using motion capture data. Our models of short time scale limb behaviour are built using labelled motion capture set. We show results for a large range of queries applied to a collection of complex motion and activity. We compare with discriminative methods applied to tracker data; our method offers significantly improved performance. We show experimental evidence that our method is robust to view direction and is unaffected by some important changes of clothing.     

A recursive genetic framework for evolutionary decision-making in problems with high dynamism

Communication and coordination are the main cores for reaching a constructive agreement among multi-agent systems (MASs). Dividing the overall performance of MAS to individual agents may lead to group learning as opposed to individual learning, which is one of the weak points of MASs. This paper proposes a recursive genetic framework for solving problems with high dynamism. In this framework, a combination of genetic algorithm and multi-agent capabilities is utilised to accelerate team learning and accurate credit assignment. The argumentation feature is used to accomplish agent learning and the negotiation features of MASs are used to achieve a credit assignment. The proposed framework is quite general and its recursive hierarchical structure could be extended. We have dedicated one special controlling module for increasing convergence time. Due to the complexity of blackjack, we have applied it as a possible test bed to evaluate the system’s performance. The learning rate of agents is measured as well as their credit assignment. The analysis of the obtained results led us to believe that our robust framework with the proposed negotiation operator is a promising methodology to solve similar problems in other areas with high dynamism.     

On the application of the minimum polynomial extrapolation method to incompressible flows with heat transfer

In this paper, the Minimum Polynomial Extrapolation method (MPE) is used to accelerate the convergence of the Characteristic–Based–Split (CBS) scheme for the numerical solution of steady state incompressible flows with heat transfer. The CBS scheme is a fractional step method for the solution of the Navier–Stokes equations while the MPE method is a vector extrapolation method which transforms the original sequence into another sequence converging to the same limit faster then the original one without the explicit knowledge of the sequence generator. The developed algorithm is tested on a two-dimensional benchmark problem (buoyancy–driven convection problem) where the Navier–Stokes equations are coupled with the temperature equation. The obtained results show the feature of the extrapolation procedure to the CBS scheme and the reduction of the computational time of the simulation.     

Regularized Reconstruction of Shapes with Statistical a priori Knowledge

The reconstruction of geometry or, in particular, the shape of objects is a common issue in image analysis. Starting from a variational formulation of such a problem on a shape manifold we introduce a regularization technique incorporating statistical shape knowledge. The key idea is to consider a Riemannian metric on the shape manifold which reflects the statistics of a given training set. We investigate the properties of the regularization functional and illustrate our technique by applying it to region-based and edge-based segmentation of image data. In contrast to previous works our framework can be considered on arbitrary (finite-dimensional) shape manifolds and allows the use of Riemannian metrics for regularization of a wide class of variational problems in image processing.     

Improvement of Convergence to Steady State Solutions of Euler Equations with the WENO Schemes

The convergence to steady state solutions of the Euler equations for high order weighted essentially non-oscillatory (WENO) finite difference schemes with the Lax-Friedrichs flux splitting (Jiang and Shu, in J. Comput. Phys. 126:202–228, 1996) is investigated. Numerical evidence in Zhang and Shu (J. Sci. Comput. 31:273–305, 2007) indicates that there exist slight post-shock oscillations when we use high order WENO schemes to solve problems containing shock waves. Even though these oscillations are small in their magnitude and do not affect the “essentially non-oscillatory” property of the WENO schemes, they are indeed responsible for the numerical residue to hang at the truncation error level of the scheme instead of settling down to machine zero. Differently from the strategy adopted in Zhang and Shu (J. Sci. Comput. 31:273–305, 2007), in which a new smoothness indicator was introduced to facilitate convergence to steady states, in this paper we study the effect of the local characteristic decomposition on steady state convergence. Numerical tests indicate that the slight post-shock oscillation has a close relationship with the local characteristic decomposition process. When this process is based on an average Jacobian at the cell interface using the Roe average, as is the standard procedure for WENO schemes, such post-shock oscillation appears. If we instead use upwind-biased interpolation to approximate the physical variables including the velocity and enthalpy on the cell interface to compute the left and right eigenvectors of the Jacobian for the local characteristic decomposition, the slight post-shock oscillation can be removed or reduced significantly and the numerical residue settles down to lower values than other WENO schemes and can reach machine zero for many test cases. This new procedure is also effective for higher order WENO schemes and for WENO schemes with different smoothness indicators.     

Network Bandwidth-aware job scheduling with dynamic information model for Grid resource brokers

A resource broker with a user-friendly interface for job submission developed on a platform constructed using the Globus toolkit is proposed. The broker employs a domain-based network information model and dynamic version to measure network statuses, and also monitors and collects resource statuses and network-related information as the basis of its brokerage. A network bandwidth-aware job scheduling algorithm for brokering suitable Grid resources to communication-intensive jobs based on improving and preserving the advantages of our previously developed network information model is also proposed. Using timely information, the resource broker effectively matches Grid resources and user requests, thus improving job execution efficiency.     

Accelerating incompressible flow computations with a Pthreads-CUDA implementation on small-footprint multi-GPU platforms

Graphics processor units (GPU) that are originally designed for graphics rendering have emerged as massively-parallel “co-processors” to the central processing unit (CPU). Small-footprint multi-GPU workstations with hundreds of processing elements can accelerate compute-intensive simulation science applications substantially. In this study, we describe the implementation of an incompressible flow Navier–Stokes solver for multi-GPU workstation platforms. A shared-memory parallel code with identical numerical methods is also developed for multi-core CPUs to provide a fair comparison between CPUs and GPUs. Specifically, we adopt NVIDIA’s Compute Unified Device Architecture (CUDA) programming model to implement the discretized form of the governing equations on a single GPU. Pthreads are then used to enable communication across multiple GPUs on a workstation. We use separate CUDA kernels to implement the projection algorithm to solve the incompressible fluid flow equations. Kernels are implemented on different memory spaces on the GPU depending on their arithmetic intensity. The memory hierarchy specific implementation produces significantly faster performance. We present a systematic analysis of speedup and scaling using two generations of NVIDIA GPU architectures and provide a comparison of single and double precision computational performance on the GPU. Using a quad-GPU platform for single precision computations, we observe two orders of magnitude speedup relative to a serial CPU implementation. Our results demonstrate that multi-GPU workstations can serve as a cost-effective small-footprint parallel computing platform to accelerate computational fluid dynamics (CFD) simulations substantially.     

A Spectral Stochastic Semi-Lagrangian Method for Convection-Diffusion Equations with Uncertainty

Real life convection-diffusion problems are characterized by their inherent or externally induced uncertainties in the design parameters. This paper presents a spectral stochastic finite element semi-Lagrangian method for numerical solution of convection-diffusion equations with uncertainty. Using the spectral decomposition, the stochastic variational problem is reformulated to a set of deterministic variational problems to be solved for each Wiener polynomial chaos. To obtain the chaos coefficients in the corresponding deterministic convection-diffusion equations, we implement a semi-Lagrangian method in the finite element framework. Once this representation is computed, statistics of the numerical solution can be easily evaluated. These numerical techniques associate the geometrical flexibility of the finite element method with the ability offered by the semi-Lagrangian method to solve convection-dominated problems using time steps larger than its Eulerian counterpart. Numerical results are shown for a convection-diffusion problem driven with stochastic velocity and for an incompressible viscous flow problem with a random force. In both examples, the proposed method demonstrates its ability to better maintain the shape of the solution in the presence of uncertainties and steep gradients.     

Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound

Known algorithms capable of scheduling implicit-deadline sporadic tasks over identical processors at up to 100% utilisation invariably involve numerous preemptions and migrations. To the challenge of devising a scheduling scheme with as few preemptions and migrations as possible, for a given guaranteed utilisation bound, we respond with the algorithm NPS-F. It is configurable with a parameter, trading off guaranteed schedulable utilisation (up to 100%) vs preemptions. For any possible configuration, NPS-F introduces fewer preemptions than any other known algorithm matching its utilisation bound.     

Energetically consistent simulation of simultaneous impacts and contacts in multibody systems with friction

This paper presents a methodology for treating energy consistency when considering simultaneous impacts and contacts with friction in the simulation of systems of interconnected bodies. Hard impact and contact is considered where deformation of the impacting surfaces is negligible. The proposed approach uses a discrete algebraic model of impact in conjunction with moment and tangential coefficients of restitution (CORs) to develop a general impact law for determining post-impact velocities. This process depends on impulse–momentum theory, the complementarity conditions, a principle of maximum dissipation, and the determination of contact forces and post-impact accelerations. The proposed methodology also uses an energy-modifying COR to directly control the system’s energy profile over time. The key result is that different energy profiles yield different results and thus energy consistency should be considered carefully in the development of dynamic simulations. The approach is illustrated on a double pendulum, considered to be a benchmark case, and a bicycle structure.     

Topological and Variational Properties of a Model for the Reconstruction of Three-Dimensional Transparent Images with Self-Occlusions

We introduce and study a two-dimensional variational model for the reconstruction of a smooth generic solid shape E, which may handle the self-occlusions and that can be considered as an improvement of the 2.1D sketch of Nitzberg and Mumford (Proceedings of the Third International Conference on Computer Vision, Osaka, 1990). We characterize from the topological viewpoint the apparent contour of E, namely, we characterize those planar graphs that are apparent contours of some shape E. This is the classical problem of recovering a three-dimensional layered shape from its apparent contour, which is of interest in theoretical computer vision. We make use of the so-called Huffman labeling (Machine Intelligence, vol. 6, Am. Elsevier, New York, 1971), see also the papers of Williams (Ph.D. Dissertation, 1994 and Int. J. Comput. Vis. 23:93–108, 1997) and the paper of Karpenko and Hughes (Preprint, 2006) for related results. Moreover, we show that if E and F are two shapes having the same apparent contour, then E and F differ by a global homeomorphism which is strictly increasing on each fiber along the direction of the eye of the observer. These two topological theorems allow to find the domain of the functional ℱ describing the model. Compactness, semicontinuity and relaxation properties of ℱ are then studied, as well as connections of our model with the problem of completion of hidden contours.

Registration of Anatomical Images Using Paths of Diffeomorphisms Parameterized with Stationary Vector Field Flows

Computational Anatomy aims for the study of variability in anatomical structures from images. Variability is encoded by the spatial transformations existing between anatomical images and a template selected as reference. In the absence of a more justified model for inter-subject variability, transformations are considered to belong to a convenient family of diffeomorphisms which provides a suitable mathematical setting for the analysis of anatomical variability. One of the proposed paradigms for diffeomorphic registration is the Large Deformation Diffeomorphic Metric Mapping (LDDMM). In this framework, transformations are characterized as end points of paths parameterized by time-varying flows of vector fields defined on the tangent space of a Riemannian manifold of diffeomorphisms and computed from the solution of the non-stationary transport equation associated to these flows. With this characterization, optimization in LDDMM is performed on the space of non-stationary vector field flows resulting into a time and memory consuming algorithm. Recently, an alternative characterization of paths of diffeomorphisms based on constant-time flows of vector fields has been proposed in the literature. With this parameterization, diffeomorphisms constitute solutions of stationary ODEs. In this article, the stationary parameterization is included for diffeomorphic registration in the LDDMM framework. We formulate the variational problem related to this registration scenario and derive the associated Euler-Lagrange equations. Moreover, the performance of the non-stationary vs the stationary parameterizations in real and simulated 3D-MRI brain datasets is evaluated. Compared to the non-stationary parameterization, our proposal provides similar results in terms of image matching and local differences between the diffeomorphic transformations while drastically reducing memory and time requirements.     

Analysis of multibody systems with flexible plates using variational graph-theoretic methods

This work treats the problem of modelling multibody systems with structural flexibility. By combining linear graph theory with the principle of virtual work and finite elements, a dynamic formulation is obtained that extends graph-theoretic (GT) modelling methods to the analysis of thin flexible plates for multibody systems. The system is represented by a linear graph, in which nodes represent reference frames on flexible plates, and edges represent components that connect these frames. To generate the equations of motion with elastic deformations, the flexible plates are discretized using a triangular thin shell finite element based on the discrete Kirchhoff criterion and can be used to discretize bidirectional bodies such as satellite panels, flatbed trailers, and mechanisms with plates. Three flexible systems with plates are analyzed to illustrate the performance of this new variational graph-theoretic formulation and its ability to generate directly a set of motion equations for flexible multibody systems (FMS) without additional user input.     

Contact identification for assembly–disassembly simulation with a haptic device

Assembly/Disassembly (A/D) simulations using haptic devices are facing difficulties while simulating insertion/extraction operations, such as removing cylinders from holes. In order to address this configuration as well as others, an approach based on contact identification between components is presented in this paper. This approach can efficiently contribute either to a new A/D simulation preparation process relying on two types of shape representations (mesh and CAD NURBS models), or directly to the real time simulation process when it is performed with 6D haptic devices. The model processing pipeline is described and illustrated to show how information can be propagated and used for contact detection. Then, the contact identification process is introduced and illustrated through an example.

Collaborative filtering with information-rich and information-sparse entities

In this paper, we consider a popular model for collaborative filtering in recommender systems. In particular, we consider both the clustering model, where only users (or items) are clustered, and the co-clustering model, where both users and items are clustered, and further, we assume that some users rate many items (information-rich users) and some users rate only a few items (information-sparse users). When users (or items) are clustered, our algorithm can recover the rating matrix with \(\omega (MK \log M)\) noisy entries while \(MK\) entries are necessary, where \(K\) is the number of clusters and \(M\) is the number of items. In the case of co-clustering, we prove that \(K^2\) entries are necessary for recovering the rating matrix, and our algorithm achieves this lower bound within a logarithmic factor when \(K\) is sufficiently large. Extensive simulations on Netflix and MovieLens data show that our algorithm outperforms the alternating minimization and the popularity-among-friends algorithm. The performance difference increases even more when noise is added to the datasets.     

Comparing G-maps with other topological data structures

This article compares two approaches to storing spatial information: On the one hand there are topological datatypes where primitives and their connectivity are explicitly stored, on the other hand there is the G-maps-approach storing abstract “darts” and groups acting on these darts such that their orbits implicitly give the elements and topology of the stored space. First these concepts are mutually related from a categorial viewpoint and, second, their storage complexity is compared.     

Variable Sized Online Interval Coloring with Bandwidth

We consider online coloring of intervals with bandwidth in a setting where colors have variable capacities. Whenever the algorithm opens a new color, it must choose the capacity for that color and cannot change it later. A set of intervals can be assigned the same color a of capacity C _a if the sum of bandwidths of intervals at each point does not exceed C _a . The goal is to minimize the total capacity of all the colors used. We consider the bounded model, where all capacities must be chosen in the range (0,1], and the unbounded model, where the algorithm may use colors of any positive capacity. For the absolute competitive ratio, we give an upper bound of 14 and a lower bound of 4.59 for the bounded model, and an upper bound of 4 and a matching lower bound of 4 for the unbounded model. We also consider the offline version of these problems and show that whereas the unbounded model is polynomially solvable, the bounded model is NP-hard in the strong sense and admits a 3.6-approximation algorithm. A preliminary version of this paper has appeared in the Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), Lecture Notes in Computer Science, Vol. 4059, pp. 29–40, Springer, 2006.