A Bisection-Like Algorithm for Branch Switching at a Simple Branch Point

At a Simple Branch Point x ₀ of a parameter-dependent nonlinear system, two distinct solutions branches S ₁ and S ₂ intersect. A popular method of branch switching from S ₁ to S ₂ at x ₀ is to use an orthogonal vector to the tangent vector to S ₁ at x ₀ as an initial guess for the tangent vector to S ₂ at x ₀. We describe an improved version of this method using a bisection-like procedure, which is especially useful for large problems.     

A Hybrid Algorithm for the Baer-Nunziato Model Using the Riemann Invariants

The paper considers the Baer-Nunziato model for two-phase flow in porous media, with discontinuous porosity. Computing solutions of the Riemann problem rests on capturing the jump in the solution across the porosity jump. A recent study (Lowe in J. Comput. Phys. 204:598–632, 2005) showed that numerical discretizations may fail to correctly capture the jump conditions across the so-called compaction wave, and yield incorrect solutions. We have formulated the Baer-Nunziato system using the Riemann invariants across the porosity jump, and propose a hybrid algorithm that uses the Riemann invariants formulation across the compaction wave, and the conservative formulation away from the compaction wave. The paper motivates and describes the hybrid scheme and present numerical results.     

Recent Developments in Spectral Stochastic Methods for the Numerical Solution of Stochastic Partial Differential Equations

Uncertainty quantification appears today as a crucial point in numerous branches of science and engineering. In the last two decades, a growing interest has been devoted to a new family of methods, called spectral stochastic methods, for the propagation of uncertainties through physical models governed by stochastic partial differential equations. These approaches rely on a fruitful marriage of probability theory and approximation theory in functional analysis. This paper provides a review of some recent developments in computational stochastic methods, with a particular emphasis on spectral stochastic approaches. After a review of different choices for the functional representation of random variables, we provide an overview of various numerical methods for the computation of these functional representations: projection, collocation, Galerkin approaches…. A detailed presentation of Galerkin-type spectral stochastic approaches and related computational issues is provided. Recent developments on model reduction techniques in the context of spectral stochastic methods are also discussed. The aim of these techniques is to circumvent several drawbacks of spectral stochastic approaches (computing time, memory requirements, intrusive character) and to allow their use for large scale applications. We particularly focus on model reduction techniques based on spectral decomposition techniques and their generalizations. This work is supported by the French National Research Agency (grant ANR-06-JCJC-0064) and by GdR MoMaS with partners ANDRA, BRGM, CEA, CNRS, EDF, IRSN.     

An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

The parameterized node multiway cut problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4 ^k n ³) time algorithm for this problem, significantly improving the previous algorithm of time for the problem. Our result gives the first polynomial time algorithm for the minimum node multiway cut problem when the separator size is bounded by O(log n). A preliminary version of this paper was presented at The 10th Workshop on Algorithms and Data Structures (WADS 2007). This work was supported in part by the National Science Foundation under the Grants CCR-0311590 and CCF-0430683.     

An Almost Quadratic Time Algorithm for Sparse Spliced Alignment

The sparse spliced alignment problem consists of finding a chain of zero or more exons from O(n) prescribed candidate exons of a DNA sequence of length O(n) that is most similar to a known related gene sequence of length n. This study improves the running time of the fastest known algorithm for this problem to date, which executes in O(n ^2.25) time, or very recently, in O(n ²log ² n) time, by proposing an O(n ²log n)-time algorithm.     

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.     

Simple and Improved Parameterized Algorithms for Multiterminal Cuts

Given a graph G=(V,E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 ^l kT(n,m)) time and Vertex Multiterminal Cut can be solved in O(k ^l T(n,m)) time, where T(n,m)=O(min?(n ^2/3,m ^1/2)m) is the running time of finding a minimum (s,t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 ^l T(n,m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 ^l T(n,m)), O(2.772 ^l T(n,m)), O(3.349 ^l T(n,m)) and O(3.857 ^l T(n,m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: $O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m))Given a graph G=(V,E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 ^l kT(n,m)) time and Vertex Multiterminal Cut can be solved in O(k ^l T(n,m)) time, where T(n,m)=O(min (n ^2/3,m ^1/2)m) is the running time of finding a minimum (s,t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 ^l T(n,m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 ^l T(n,m)), O(2.772 ^l T(n,m)), O(3.349 ^l T(n,m)) and O(3.857 ^l T(n,m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: O((min(?{2k},l)+1)^2k2^lT(n,m))O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m)) -time algorithm for Edge Multicut and O((2k) ^k+l/2 T(n,m))-time algorithm for Vertex Multicut.     

An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions

We present a new streaming algorithm for maintaining an ε-kernel of a point set in ℝ ^d using O((1/ε ^(d−1)/2)log (1/ε)) space. The space used by our algorithm is optimal up to a small logarithmic factor. This significantly improves (for any fixed dimension d ≥3) the best previous algorithm for this problem that uses O(1/ε ^d−(3/2)) space, presented by Agarwal and Yu. Our algorithm immediately improves the space complexity of the previous streaming algorithms for a number of fundamental geometric optimization problems in fixed dimensions, including width, minimum-volume bounding box, minimum-radius enclosing cylinder, minimum-width enclosing annulus, etc.     

Smooth Scheduling under Variable Rates or the Analog-Digital Confinement Game

This work considers non-terminating scheduling problems in which a system of multiple resources serves clients having variable needs. The system has m identical resources and n clients; in each time slot each resource may serve at most one client; in each such slot t each client γ has a rate, a real number ρ _γ (t), that specifies his needs in this slot. The rates satisfy the restriction ∑ _γ ρ _γ (t)≤m for any slot t. Except of this restriction, the rates can vary in arbitrary fashion. (This contrasts most prior works in this area in which the rates of the clients are constant.) The schedule is required to be smooth as follows: a schedule is Δ -smooth if for all time intervals I the absolute difference between the amount of service received by each client γ to his nominal needs of ∑ _t∈I ρ _γ (t) is less than Δ. Our objective are online schedulers that produce Δ-smooth schedules where Δ is a small constant which is independent of m and n. Our paper constructs such schedulers; these are the first online Δ-smooth schedulers, with a constant Δ, for clients with arbitrarily variable rates in a single or multiple resource system. Furthermore, the paper also considers a non-concurrent environment in which there is an additional restriction that each client is served at most once in each time slot; it presents the first online smooth schedulers for variable rates under this restriction. The above non-concurrent restriction is crucial in some applications (e.g., CPU scheduling). It has been pointed out that this restriction “adds a surprising amount of difficulty” to the scheduling problem. However, this observation was never formalized and, of course, was never proved. Our paper formalizes and proves some aspects of this observation. Another contribution of this paper is the introduction of a complete information, two player game called the analog-digital confinement game. In such a game pebbles are located on the real line; the two players, the analog player and the digital player, take alternating turns and each one, in his turn, moves some of the pebbles; the digital player moves the pebbles backwards by discrete distances while the analog player moves the pebbles forward by analog distances; the aim of the analog player is to cause one pebble (or more) to escape a pre-defined real interval while the aim of the digital player is to confine the pebbles into the interval. We demonstrate that this game is a convenient framework to study the general question of how to approximate an analog process by a digital one. All the above scheduling results are established via this game. In this derivation, the pebbles represent the clients, the analog player generates the needs of the clients and the digital player generates the schedule. Dedicated to the memory of Professor Shimon Even for his inspiration and encouragement     

An Approximation Algorithm for Binary Searching in Trees

We consider the problem of computing efficient strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of a tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a linear time algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(log n)-approximation.     

A Linear-Time Algorithm for Hamming Distance with Shifts

The Hamming distance with shifts was introduced by Bookstein et al. as a generalization of the traditional Hamming distance to allow a tunable degree of fuzziness when comparing two binary sequences of the same length. We present a linear-time algorithm for computing this distance. The previous best time bound was quadratic.     

Performance Modeling and Algorithm Characterization for Robust Image Segmentation

This paper presents a probabilistic framework based on Bayesian theory for the performance prediction and selection of an optimal segmentation algorithm. The framework models the optimal algorithm selection process as one that accounts for the information content of an input image as well as the behavioral properties of a particular candidate segmentation algorithm. The input image information content is measured in terms of image features while the candidate segmentation algorithm’s behavioral characteristics are captured through the use of segmentation quality features. Gaussian probability distribution models are used to learn the required relationships between the extracted image and algorithm features and the framework tested on the Berkeley Segmentation Dataset using four candidate segmentation algorithms.     

Stochastic switching for partially observable dynamics and optimal asset allocation

In industrial applications, optimal control problems frequently appear in the context of decision-making under incomplete information. In such framework, decisions must be adapted dynamically to account for possible regime changes of the underlying dynamics. Using stochastic filtering theory, Markovian evolution can be modelled in terms of latent variables, which naturally leads to high-dimensional state space, making practical solutions to these control problems notoriously challenging. In our approach, we utilise a specific structure of this problem class to present a solution in terms of simple, reliable, and fast algorithms. The algorithms presented in this paper have already been implemented in an R package.     

Stochastic allocation and scheduling for conditional task graphs in multi-processor systems-on-chip

Embedded systems designers are turning to multicore architectures to satisfy the ever-growing computational needs of applications within a reasonable power envelope. One of the most daunting challenges for MultiProcessor System-on-Chip (MPSoC) platforms is the development of tools for efficient mapping multi-task applications onto hardware platforms. Software mapping can be formulated as an optimal allocation and scheduling problem, where the application is modeled as a task graph, the target hardware is modeled as a set of heterogeneous resources, and the objective function represents a design goal α (e.g. minimum execution time, minimum usage of communication resources, etc.). Conditional task graphs, where inter-task edges represent data as well as control dependencies, are a well-known computational model to describe complex real-life applications where alternative execution paths, guarded by conditionals, can be specified. Each condition has a probability associated with each possible outcome.     

Lattice Boltzmann Model Based on the Rebuilding-Divergency Method for the Laplace Equation and the Poisson Equation

In this paper, a new lattice Boltzmann model based on the rebuilding-divergency method for the Poisson equation is proposed. In order to translate the Poisson equation into a conservation law equation, the source term and diffusion term are changed into divergence forms. By using the Chapman-Enskog expansion and the multi-scale time expansion, a series of partial differential equations in different time scales and several higher-order moments of equilibrium distribution functions are obtained. Thus, by rebuilding the divergence of the source and diffusion terms, the Laplace equation and the Poisson equation with the second accuracy of the truncation errors are recovered. In the numerical examples, we compare the numerical results of this scheme with those obtained by other classical method for the Green-Taylor vortex flow, numerical results agree well with the classical ones.     

An Efficient Algorithm for Modelling Duration in Hidden Markov Models, with a Dramatic Application

For many years, the hidden Markov model (HMM) has been one of the most popular tools for analysing sequential data. One frequently used special case is the left-right model, in which the order of the hidden states is known. If knowledge of the duration of a state is available it is not possible to represent it explicitly with an HMM. Methods for modelling duration with HMM’s do exist (Rabiner in Proc. IEEE 77(2):257–286, [1989]), but they come at the price of increased computational complexity. Here we present an efficient and robust algorithm for modelling duration in HMM’s, and this algorithm is successfully used to control autonomous computer actors in a theatrical play.     

A High Order Compact Scheme for the Pure-Streamfunction Formulation of the Navier-Stokes Equations

In this paper we continue the study, which was initiated in (Ben-Artzi et al. in Math. Model. Numer. Anal. 35(2):313–303, 2001; Fishelov et al. in Lecture Notes in Computer Science, vol. 2667, pp. 809–817, 2003; Ben-Artzi et al. in J. Comput. Phys. 205(2):640–664, 2005 and SIAM J. Numer. Anal. 44(5):1997–2024, 2006) of the numerical resolution of the pure streamfunction formulation of the time-dependent two-dimensional Navier-Stokes equation. Here we focus on enhancing our second-order scheme, introduced in the last three afore-mentioned articles, to fourth order accuracy. We construct fourth order approximations for the Laplacian, the biharmonic and the nonlinear convective operators. The scheme is compact (nine-point stencil) for the Laplacian and the biharmonic operators, which are both treated implicitly in the time-stepping scheme. The approximation of the convective term is compact in the no-leak boundary conditions case and is nearly compact (thirteen points stencil) in the case of general boundary conditions. However, we stress that in any case no unphysical boundary condition was applied to our scheme. Numerical results demonstrate that the fourth order accuracy is actually obtained for several test-cases.     

A Dual-Petrov-Galerkin Method for the Kawahara-Type Equations

An efficient and accurate numerical scheme is proposed, analyzed and implemented for the Kawahara and modified Kawahara equations which model many physical phenomena such as gravity-capillary waves and magneto-sound propagation in plasmas. The scheme consists of dual-Petrov-Galerkin method in space and Crank-Nicholson-leap-frog in time such that at each time step only a sparse banded linear system needs to be solved. Theoretical analysis and numerical results are presented to show that the proposed numerical is extremely accurate and efficient for Kawahara type equations and other fifth-order nonlinear equations. This work is partially supported by the National Science Council of the Republic of China under the grant NSC 94-2115-M-126-004 and 95-2115-M-126-003. This work is partially supported by NSF grant DMS-0610646.     

A Local Algorithm for the Computation of Image Velocity via Constructive Interference of Global Fourier Components

A novel Fourier-based technique for local motion detection from image sequences is proposed. In this method, the instantaneous velocities of local image points are inferred directly from the global 3D Fourier components of the image sequence. This is done by selecting those velocities for which the superposition of the corresponding Fourier gratings leads to constructive interference at the image point. Hence, image velocities can be assigned locally even though position is computed from the phases and amplitudes of global Fourier components (spanning the whole image sequence) that have been filtered based on the motion-constraint equation, reducing certain aperture effects typically arising from windowing in other methods. Regularization is introduced for sequences having smooth flow fields. Aperture effects and their effect on optic-flow regularization are investigated in this context. The algorithm is tested on both synthetic and real image sequences and the results are compared to those of other local methods. Finally, we show that other motion features, i.e. motion direction, can be computed using the same algorithmic framework without requiring an intermediate representation of local velocity, which is an important characteristic of the proposed method.