Parallelization of the Gaussian Elimination Algorithm on Systolic Arrays

We study the parallel implementation of the Gaussian elimination scheme on systolic arrays. We first show that the time (resp. area) complexity of the algorithm isT= 3n− 1 (resp.S= (n²/4) +O(n)), wherenis the size of the linear system. Then we exhibit three algorithms. The two first ones are optimal in time. The first one corresponds to an orthogonally connected array of size 3(n²/8) +O(n). The second network is smaller,S= 3(n²/10) +O(n), but two layers are necessary in order to obtain a regular layout with local communications. The third one is hexagonally connected, has size (n²/3) +O(n), and is almost optimal in time.     

Towards optimal range medians

We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O(nlogk+klogn) time to answer k such median queries. This improves previous algorithms by a logarithmic factor and matches a comparison lower bound for k=O(n). The space complexity of our simple algorithm is O(nlogn) in the pointer machine model, and O(n) in the RAM model. In the latter model, a more involved O(n) space data structure can be constructed in O(nlogn) time where the time per query is reduced to O(logn/loglogn). We also give efficient dynamic variants of both data structures, achieving O(log²n) query time using O(nlogn) space in the comparison model and O((logn/loglogn)²) query time using O(nlogn/loglogn) space in the RAM model, and show that in the cell-probe model, any data structure which supports updates in O(log^O(1)n) time must have Ω(logn/loglogn) query time.Our approach naturally generalizes to higher-dimensional range median problems, where element positions and query ranges are multidimensional—it reduces a range median query to a logarithmic number of range counting queries.     

Visibility of disjoint polygons

Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n ²) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n ²) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n ²) time, improving earlierO(n ² logn) results.     

Range mode and range median queries in constant time and sub-quadratic space

Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time.For the function mode we improve the previously known space bound O(n²/logn) to O(n²loglogn/log²n) words.For median the space bound is improved to O(n²loglog²n/log²n) words from O(n²⋅log(k)n/logn), where k is an arbitrary constant and log(k) is the iterated logarithm.     

Gossiping by processors prone to omission failures

We consider the gossip problem in a synchronous message-passing system. Participating processors are prone to omission failures, that is, a faulty processor may fail to send or receive a message. The gossip problem in the fault-tolerant setting is defined as follows: every correct processor must learn the initial value of any other processor, unless the other one is faulty; in the latter case either the initial value or the information about the fault must be learned. We develop two efficient algorithms that solve the gossip problem in time O(logn), where n is the number of processors in the system. The first one is an explicit algorithm (i.e., constructed in polynomial time) sending O(nlogn+f²) messages, and the second one reduces the message complexity to O(n+f²), where f is the upper bound on the number of faulty processors.     

Quadrilateral and tetrahedral mesh stripification using 2-factor partitioning of the dual graph

In order to find a 2-factor of a graph, there exists a O(n ^1.5) deterministic algorithm [7] and a O(n ³) randomized algorithm [14]. In this paper, we propose novel O(nlog³ nloglogn) algorithms to find a 2-factor, if one exists, of a graph in which all n vertices have degree 4 or less. Such graphs are actually dual graphs of quadrilateral and tetrahedral meshes. A 2-factor of such graphs implicitly defines a linear ordering of the mesh primitives in the form of strips. Further, by introducing a few additional primitives, we reduce the number of tetrahedral strips to represent the entire tetrahedral mesh and represent the entire quad surface using a single quad strip.     

Balancing Bounded Treewidth Circuits

We use algorithmic tools for graphs of small treewidth to address questions in complexity theory. For our main construction, we prove that multiplicatively disjoint arithmetic circuits of size n ^O(1) and treewidth k can be simulated by bounded fan-in arithmetic formulas of depth O(k ²logn). From this we derive an analogous statement for syntactically multilinear arithmetic circuits, which strengthens the central theorem of M. Mahajan and B.V.R. Rao (Proc. 33rd International Symposium on Mathematical Foundations of Computer Science, vol. 5162, pp. 455–466, 2008). We show our main construction has the following three applications:

• Bounded width arithmetic circuits of size n ^O(1) can be balanced to depth O(logn), provided chains of iterated multiplication in the circuit are of length O(1).
• Boolean bounded fan-in circuits of size n ^O(1) and treewidth k can be simulated by bounded fan-in formulas of depth O(k ²logn). This strengthens in the non-uniform setting the known inclusion that SC⁰?NC¹.
• We demonstrate treewidth restricted cases of Directed-Reachability and Circuit Value Problem that can be solved in LogDCFL.

We also give a construction showing, for both arithmetic and Boolean circuits, that any circuit of size n ^O(1) and treewidth O(log ⁱ n) can be simulated by a circuit of width O(log ⁱ⁺¹ n) and size n ^c , where c=O(1), if i=0, and c=O(loglogn) otherwise.     

A fast algorithm for computing sparse visibility graphs

AnO(¦E¦log² n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n ²)-time andO(n ²)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.     

Robust gossiping with an application to consensus

We study deterministic gossiping in synchronous systems with dynamic crash failures. Each processor is initialized with an input value called rumor. In the standard gossip problem, the goal of every processor is to learn all the rumors. When processors may crash, then this goal needs to be revised, since it is possible, at a point in an execution, that certain rumors are known only to processors that have already crashed. We define gossiping to be completed, for a system with crashes, when every processor knows either the rumor of processor v or that v has already crashed, for any processor v. We design gossiping algorithms that are efficient with respect to both time and communication. Let t<n be the number of failures, where n is the number of processors. If , then one of our algorithms completes gossiping in O(log²t) time and with O(npolylogn) messages. We develop an algorithm that performs gossiping with O(n^1.77) messages and in O(log²n) time, in any execution in which at least one processor remains non-faulty. We show a trade-off between time and communication in gossiping algorithms: if the number of messages is at most O(npolylogn), then the time has to be at least . By way of application, we show that if n−t=Ω(n), then consensus can be solved in O(t) time and with O(nlog²t) messages.     

Parallel Algorithms for the Edge-Coloring and Edge-Coloring Update Problems

LetG(V,E) be a simple undirected graph with a maximum vertex degree Δ(G) (or Δ for short), |V| =nand |E| =m. An edge-coloring ofGis an assignment to each edge inGa color such that all edges sharing a common vertex have different colors. The minimum number of colors needed is denoted by χ′(G) (called thechromatic index). For a simple graphG, it is known that Δ ≤ χ′(G) ≤ Δ + 1. This paper studies two edge-coloring problems. The first problem is to perform edge-coloring for an existing edge-colored graphGwith Δ + 1 colors stemming from the addition of a new vertex intoG. The proposed parallel algorithm for this problem runs inO(Δ^3/2log³Δ + Δ logn) time usingO(max{nΔ, Δ³}) processors. The second problem is to color the edges of a given uncolored graphGwith Δ + 1 colors. For this problem, our first parallel algorithm requiresO(Δ^5.5log³Δ logn+ Δ⁵log⁴n) time andO(max{n²Δ,nΔ³}) processors, which is a slight improvement on the algorithm by H. J. Karloff and D. B. Shmoys [J. Algorithms8 (1987), 39–52]. Their algorithm costsO(Δ⁶log⁴n) time andO(n²Δ) processors if we use the fastest known algorithm for finding maximal independent sets by M. Goldberg and T. Spencer [SIAM J. Discrete Math.2 (1989), 322–328]. Our second algorithm requiresO(Δ^4.5log³Δ logn+ Δ⁴log⁴n) time andO(max{n²,nΔ³}) processors. Finally, we present our third algorithm by incorporating the second algorithm as a subroutine. This algorithm requiresO(Δ^3.5log³Δ logn+ Δ³log⁴n) time andO(max{n²log Δ,nΔ³}) processors, which improves, by anO(Δ^2.5) factor in time, on Karloff and Shmoys' algorithm. All of these algorithms run in the COMMON CRCW PRAM model.     

A Study of Permutation Networks: New Designs and Some Generalizations

Permutation networks have been used in the literature to model interprocessor and processor-memory interconnections in parallel computers. This paper introduces new permutation network designs and generalizes the notion of a permutation network to provide a more flexible model of such interconnections. The new designs are based concentrators and superconcentrators, and for n inputs they can be optimized to obtain self-routing permutation networks with O(n lg n) cost, O(lg n) depth, and O(lg²n) routing time. The main feature of these new network designs is that they do not require complex routing schemes such as Clos networks since they are inherently self-routing. Generalizations of these designs are also given to obtain permutation networks in which the numbers of inputs and outputs may be different, and/or the maximum number of parallel routes between inputs and outputs can be less than the number of inputs or outputs, or both. For n inputs, αn outputs, and O(n^ϵ) parallel routes, where 0 < α ≤ 1, 0 < ϵ < 1, these generalized designs can be optimized to have permutation networks with O(n) cost, O(lg n), depth, and O(lg²n) routing time. It is shown that the previously known designs, such as Clos networks, result in inferior realizations when compared with these new designs.     

A better performance guarantee for approximate graph coloring

Approximate graph coloring takes as input a graph and returns a legal coloring which is not necessarily optimal. We improve the performance guarantee, or worst-case ratio between the number of colors used and the minimum number of colors possible, toO(n(log logn)³/(logn)³), anO(logn/log logn) factor better than the previous best-known result.     

Channel assignment via fast zeta transform

We show an O^?(n(?+1))-time algorithm for the channel assignment problem, where ? is the maximum edge weight. This improves on the previous O^?(n(?+2))-time algorithm by Král (2005) [1], as well as algorithms for important special cases, like L(2,1)-labeling. For the latter problem, our algorithm works in O^?(n³) time. The progress is achieved by applying the fast zeta transform in combination with the inclusion-exclusion principle.     

Direct and indirect algorithms for on-line learning of disjunctions

It is easy to design on-line learning algorithms for learning k out of n variable monotone disjunctions by simply keeping one weight per disjunction. Such algorithms use roughly O(n^k) weights which can be prohibitively expensive. Surprisingly, algorithms like Winnow require only n weights (one per variable or attribute) and the mistake bound of these algorithms is not too much worse than the mistake bound of the more costly algorithms. The purpose of this paper is to investigate how exponentially many weights can be collapsed into only O(n) weights. In particular, we consider probabilistic assumptions that enable the Bayes optimal algorithm's posterior over the disjunctions to be encoded with only O(n) weights. This results in a new O(n) algorithm for learning disjunctions which is related to the Bylander's BEG algorithm originally introduced for linear regression. Besides providing a Bayesian interpretation for this new algorithm, we are also able to obtain mistake bounds for the noise free case resembling those that have been derived for the Winnow algorithm. The same techniques used to derive this new algorithm also provide a Bayesian interpretation for a normalized version of Winnow.     

Orthogonally Drawing Cubic Graphs in Parallel

In this paper we describe a parallel algorithm that, given annvertex cubic graphGas input, outputs an orthogonal drawing ofGwithO(n) bends,O(n) maximum edge length, andO(n²) area inO(log n) time using a CRCW PRAM withnprocessors. We give two slight variants of the algorithm. The first generates a drawing in which each edge has at most 2 bends; the total number of bends and the area are bounded byn+3 and [formula], respectively. The second optimizes the number of bends per edge (at most one) even if the values of the other functions are slightly worst. Despite its nonoptimality, this parallel algorithm is the first dealing with nonplanar, nonbiconnected graphs. Moreover, no embedding of the graph is requested as input nor is anst-numbering (orlmc-numbering) computed.     

L 1 shortest paths among polygonal obstacles in the plane

We present an algorithm for computingL ₁ shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of “events.” By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(n?^?1/2 log² n) time andO(n?^?1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL ₁ Voronoi diagram for source points that lie among a collection of polygonal obstacles.     

Recognition of largest empty orthoconvex polygon in a point set

An algorithm for computing the maximum area empty isothetic orthoconvex polygon among a set of n points on a 2D rectangular region, is presented. The worst-case time and space complexities of the proposed algorithm are O(n³) and O(n²) respectively.     

A time-luck tradeoff in relativized cryptography

New definitions are proposed for the security of Transient-Key Cryptography (a variant on Public-Key Cryptography) that account for the possibility of super-polynomial-time Monte Carlo cryptanalytical attacks. Weaker definitions no longer appear to be satisfactory in the light of Adleman's recent algorithm capable of breaking the Diffie-Hellman scheme in RTIME(O(2^{0(√n log n)})) for keys of length n. The basic question we address is: How can one relate the amount of time a cryptanalyst is willing to spend decoding cryptograms to his likelihood of success? What more can one say than the obvious “The more time he uses, the less lucky he needs to be?” These questions and others are partially answered in a relativized model of computation in which there exists a transient-key cryptosystem such that even a cryptanalyst willing to spend as much as (almost) O(2^{n/log n}) steps on length n cryptograms cannot hope to break but an exponentially small fraction of them, even if he is allowed to make use of a true random number generator. This is rather tight because the same cryptosystem falls immediately if the cryptanalyst is willing to spend O(2^cn) steps for any constant c > 0.     

Repeated detection of conjunctive predicates in distributed executions

Given a conjunctive predicate ? over a distributed execution, this paper gives an algorithm to detect all interval sets, each interval set containing one interval per process, in which the local values satisfy the Definitely(?) modality. The time complexity of the algorithm is O(n³p), where n is the number of processes and p is the bound on the number of times a local predicate becomes true at any process. The paper also proves that unlike the Possibly(?) modality which admits O(pn) solution interval sets, the Definitely(?) modality admits O(np) solution interval sets. The paper also gives an on-line test to determine whether all solution interval sets can be detected in polynomial time under arbitrary fine-grained causality-based modality specifications.     

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.