Fast parallel graph searching with applications

This paper presents fast parallel algorithms for the following graph theoretic problems: breadth-depth search of directed acyclic graphs; minimum-depth search of graphs; finding the minimum-weighted paths between all node-pairs of a weighted graph and the critical activities of an activity-on-edge network. The first algorithm hasO(logdlogn) time complexity withO(n ³) processors and the remaining algorithms achieveO(logd loglogn) time bound withO(n ²[n/loglogn]) processors, whered is the diameter of the graph or the directed acyclic graph (which also represents an activity-on-edge network) withn nodes. These algorithms work on an unbounded shared memory model of the single instruction stream, multiple data stream computer that allows both read and write conflicts.     

Two-Dimensional and Three-Dimensional Point Location in Rectangular Subdivisions

We apply van Emde Boas-type stratified trees to point location problems in rectangular subdivisions in 2 and 3 dimensions. In a subdivision with n rectangles having integer coordinates from [0, U − 1], we locate an integer query point in O((log log U)^d) query time using O(n) space when d ≤ 2 or O(n log log U) space when d = 3. Applications and extensions of this "fixed universe" approach include spatial point location using logarithmic time and linear space in rectilinear subdivisions having arbitrary coordinates, point location in c-oriented polygons or fat triangles in the plane, point location in subdivisions of space into "fat prisms," and vertical ray shooting among horizontal "fat objects." Like other results on stratified trees, our algorithms run on a RAM model and make use of perfect hashing.     

An optimal parallel connectivity algorithm

A synchronized parallel algorithm of depth O(n²/p) for p (≤n²/log²n) processors is given for the problem of computing connected components of an undirected graph. The speed-up of this algorithm is optimal in the sense that the depth of the algorithm is of the order of the running time of the fastest known sequential algorithm over the number of processors used.     

An efficient pram algorithm for maximum-weight independent set on permutation graphs

An efficient parallel algorithm is presented to find a maximum weight independent set of a permutation graph which takesO (logn) time usingO (n ²/logn) processors on an EREW PRAM, provided the graph has at mostO (n) maximal independent sets. The best known parallel algorithm takesO (log² n) time andO (n ³/logn) processors on a CREW PRAM.     

A trust region method for solving the decentralized static output feedback design problem

The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents anO(n ²) time sequential algorithm and anO(n ²/p+logn) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, wherep andn represent respectively the number of processors and the number of vertices of the circular-arc graph.     

Stability and convergence of fully discrete finite element schemes for the acoustic wave equation

In this paper, we investigate the stability and convergence of some fully discrete finite element schemes for solving the acoustic wave equation where a discontinuous Galerkin discretization in space is used. We first review and compare conventional time-stepping methods for solving the acoustic wave equation. We identify their main properties and investigate their relationship. The study includes the Newmark algorithm which has been used extensively in applications. We present a rigorous stability analysis based on the energy method and derive sharp stability results covering some well-known CFL conditions. A convergence analysis is carried out and optimal a priori error estimates are obtained. For sufficiently smooth solutions, we demonstrate that the maximal error in the L ²-norm error over a finite time interval converges optimally as O(h ^p+1+??t ^s ), where p denotes the polynomial degree, s=1 or 2, h the mesh size, and ??t the time step.     

Dynamic point location in arrangements of hyperplanes

We present algorithms for maintaining data structures supporting fast (polylogarithmic) point-location and ray-shooting queries in arrangements of hyperplanes. This data structure allows for deletion and insertion of hyperplanes. Our algorithms use random bits in the construction of the data structure but do not make any assumptions about the update sequence or the hyperplanes in the input. The query bound for our data structure isÕ(polylog(n)), wheren is the number of hyperplanes at any given time, and theÕ notation indicates that the bound holds with high probability, where the probability is solely with respect to randomization in the data structure. By high probability we mean that the probability of error is inversely proportional to a large degree polynomial inn. The space requirement isÕ(n ^d). The cost of update isÕ(n ^d?1 logn. The expected cost of update isO(n ^d?1); the expectation is again solely with respect to randomization in the data structure. Our algorithm is extremely simple. We also give a related algorithm with optimalÕ(logn) query time, expectedO(n ^d) space requirement, and amortizedO(n ^d?1) expected cost of update. Moreover, our approach has a versatile quality which is likely to have further applications to other dynamic algorithms. Ford=2, 3 we also show how to obtain polylogarithmic update time in the CRCW PRAM model so that the processor-time product matches (within a polylogarithmic factor) the sequential update time.     

Faster deterministic wakeup in multiple access channels

We consider the fundamental problem of waking up n processors sharing a multiple access channel. We assume the weakest model of synchronization, the locally synchronous model, in which no global clock is available: processors have local clocks ticking at the same rate, but each clock starts counting the rounds in the round in which the correspondent processor wakes up. Moreover, the number n of processors is not known to the processors. We propose a new deterministic algorithm for this problem in time O(n³log³n), which improves on the currently best upper bound of O(n⁴log⁵n).     

A fast and simple randomized parallel algorithm for the maximal independent set problem

A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O(|E|d_max) processors is O(log n), where d_max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O(|E|) processors the algorithm runs in O(log²n). Previously, an O(log⁴n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log²n) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.     

Branch-and-bound and parallel computation: A historical note

This historical note summarizes what we believe to have been the first use of parallel processing to solve a combinatorial optimization problem by a branch-and-bound algorithm. In 1975, a branch-and-bound algorithm for the traveling salesman problem that used p parallel processors with shared memory was simulated on a single processor. The results show that the simultaneous exploration of several nodes of the search tree yields better feasible solutions earlier. This allows earlier pruning of branches and significantly reduces the number of nodes searched.     

Parallel iterative linear solvers for multistep Runge-Kutta methods

This paper deals with solving stiff systems of differential equations by implicit Multistep Runge-Kutta (MRK) methods. For this type of methods, nonlinear systems of dimension sd arise, where s is the number of Runge-Kutta stages and d the dimension of the problem. Applying a Newton process leads to linear systems of the same dimension, which can be very expensive to solve in practice. With a parallel iterative linear system solver, especially designed for MRK methods, we approximate these linear systems by s systems of dimension d, which can be solved in parallel on a computer with s processors. In terms of Jacobian evaluations and LU-decompositions, the k-steps-stage MRK applied with this technique is on s processors equally expensive as the widely used k-step Backward Differentiation Formula on 1 processor, whereas the stability properties are better than that of BDF. A simple implementation of both methods shows that, for the same number of Newton iterations, the accuracy delivered by the new method is higher than that of BDF.     

Weak- and strong-type inequality for the cone-like maximal operator in variable Lebesgue spaces

The classical Hardy-Littlewood maximal operator is bounded not only on the classical Lebesgue spaces L_p(R^d) (in the case p > 1), but (in the case when 1/p(·) is log-Hölder continuous and p- = inf{p(x): x ∈ R^d > 1) on the variable Lebesgue spaces L_p(·)(R^d), too. Furthermore, the classical Hardy-Littlewood maximal operator is of weak-type (1, 1). In the present note we generalize Besicovitch’s covering theorem for the so-called γ-rectangles. We introduce a general maximal operator M_s^γδ, and with the help of generalized Φ-functions, the strong- and weak-type inequalities will be proved for this maximal operator. Namely, if the exponent function 1/p(·) is log-Hölder continuous and p- ≥ s, where 1 ≤ s ≤ ∞ is arbitrary (or p- ≥ s), then the maximal operator M_s^γδ is bounded on the space L_p(·)(R^d) (or the maximal operator is of weak-type (p(·), p(·))).     

Boundedness for pseudodifferential operators on multivariate α-modulation spaces

The α-modulation spaces M ^s,α _p,q (R ^d ), α∈[0,1], form a family of spaces that contain the Besov and modulation spaces as special cases. In this paper we prove that a pseudodifferential operator σ(x,D) with symbol in the Hörmander class S ^b _ρ,0 extends to a bounded operator σ(x,D):M ^s,α _p,q (R ^d )→M ^s-b,α _p,q (R ^d ) provided 0≤α≤ρ≤1, and 1<p,q<∞. The result extends the well-known result that pseudodifferential operators with symbol in the class S ^b _1,0 maps the Besov space B ^s _p,q (R ^d ) into B ^s-b _p,q (R ^d ).     

An optimal contour algorithm for iso-oriented rectangles

Given a set of n iso-oriented rectangles in 2-space we describe an algorithm which determines the contour of their union in O(n log n + p) time and O(n + p) space, where p is the number of edges in the contour. This performance is time-optimal. The space requirements are the same as in the best previously known algorithm. We achieve this by introducing a new data structure, the contracted segment tree, which is a non-trivial modification of the well known segment tree. If only the pieces of the contour are to be reported then this approach yields a time- and space-optimal algorithm.     

Baire generic histograms of wavelet coefficients and large deviation formalism in Besov and Sobolev spaces

Histograms of wavelet coefficients are expressed in terms of the wavelet profile and the wavelet density. The large deviation multifractal formalism states that if a function f has a minimal uniform Hölder regularity then its Hölder spectrum is equal to the wavelet density. The purpose of this paper is twofold. Firstly, we compute generically (in the sense of Baire's categories) these histograms in Besov and Lp,s(T) spaces, where T is the torus Rd/Zd (resp. in the Baire's vector space where s:q?s(q) is a C¹ and concave function on R⁺ satisfying 0?s^′?d and s(0)>0). Secondly, as an application, we deduce some extra generic properties for the histograms in these spaces, and study the generic validity of the large deviation multifractal formalism in Besov and Lp,s spaces for s>d/p (resp. in the above space V).     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

The weighted maximum independent set problem in permutation graphs

In this paper, sequential and parallel algorithms are presented to find a maximum independent set with largest weight in a weighted permutation graph. The sequential algorithm, which is designed based on dynamic programming, runs in timeO(nlogn) and requiresO(n) space. The parallel algorithm runs inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM.     

Multiple point evaluation on combined tensor product supports

We consider the multiple point evaluation problem for an n-dimensional space of functions [???1,1[ ^d ?? spanned by d-variate basis functions that are the restrictions of simple (say linear) functions to tensor product domains. For arbitrary evaluation points this task is faced in the context of (semi-)Lagrangian schemes using adaptive sparse tensor approximation spaces for boundary value problems in moderately high dimensions. We devise a fast algorithm for performing m?≥?n point evaluations of a function in this space with computational cost O(mlog ^d n). We resort to nested segment tree data structures built in a preprocessing stage with an asymptotic effort of O(nlog ^d???1 n).     

The measure problem for rectangular ranges in d-space

Klee recently posed the question: find an efficient algorithm for computing the measure of a set of n intervals on the line, and the analog for n hyperrectangles (ranges) in d-space. The one-dimensional case is easily solved in O(n log n) and Bentley has proved an O(n^d?1log n) algorithm for dimension d ≥ 2. We present an algorithm for Klee's measure problem that has a worst-case running time of only O(n^d?1) for d?3. While Bentley's algorithm is based on segment trees and requires only linear storage for any dimension, the new method is based on quad-trees and requires quadratic storage for d > 2.     

A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.