Narrow Results

Stencil codes such as the Jacobi, Gauß-Seidel, and red-black Gauß-Seidel kernels are among the most time-consuming routines in many scientific and engineering applications. The performance of these codes critically depends on an efficient usage of caches, and can be improved by tiling. Several tiling schemes have been suggested in the literature; this paper gives an overview and comparison. Then, in the main part, we prove a lower bound on the number of cold and capacity misses. Finally, we analyze a particular tiling scheme, and show that it is off the lower bound by a factor of at most ten. Our results show up limitations to the speedup that can be gained by future research.

Let G = (V,E) be a computation graph, which is a directed graph representing a straight line computation and S ⊂ V. We say a vertex v is an input vertex for S if there is an edge (v, u) such that v ∉ S and u ∈ S. We say a vertex u is an output vertex for S if there is an edge (u, v) such that u ∈ S and v ∉ S. A vertex is called a boundary vertex for a set S if it is either an input vertex or an output vertex for S. We consider the problem of determining the minimum value of boundary size of S over all sets of size M in an infinite directed grid. This problem is related to the vertex isoperimetric parameter of a graph, and is motivated by the need for deriving a lower bound for memory traffic for a computation graph representing a financial application. We first extend the notion of vertex isoperimetric parameter for undirected graphs to computation graphs, and then provide a complete solution for this problem for all M. In particular, we show that a set S of size M = 3k² + 3k + 1 vertices of an infinite directed grid, the boundary size must be at least 6k + 3, and this is obtained when the vertices in S are arranged in a regular hexagonal shape with side k + 1.

The equivalence of finite automata and regular expressions dates back to the seminal paper of Kleene on events in nerve nets and finite automata from 1956. In the present paper we tour a fragment of the literature and summarize results on upper and lower bounds on the conversion of finite automata to regular expressions and vice versa. As an interesting special case also one-unambiguous regular expressions, a sort of a deterministic version of a regular expression, are considered. We also briefly recall the known bounds for the removal of spontaneous transitions (ε-transitions) on non-ε-free nondeter-ministic devices. Moreover, we report on recent results on the average case descriptional complexity bounds for the conversion of regular expressions to finite automata and new developments on the state elimination algorithm that converts finite automata to regular expressions.

The neighbourhood of a language $L$ with respect to an additive distance consists of all strings that have distance at most the given radius from some string of $L$. We show that the worst case deterministic state complexity of a radius $r$ neighbourhood of a language recognized by an $n$ state nondeterministic finite automaton $A$ is ${(r+2)}^n-1$. In the case where $A$ is deterministic we get the same lower bound for the state complexity of the neighbourhood if we use an additive quasi-distance. The lower bound constructions use an alphabet of size linear in $n$. We show that the worst case state complexity of the set of strings that contain a substring within distance $r$ from a string recognized by $A$ is ${(r+2)}^{n-2}+1$.

We consider the problem of evaluating a boolean function P(x₁,…,x_n), by asking queries of the form “x_i=?”, and receiving answers which may not always be truthful. Assuming that the total number of lies does not exceed E, we present an algorithm with cost O(n+s_PE+t_PE), where s_P is the maximal size of a minterm of P(x) and t_P ‘is the maximal size of a maxterm. We also prove that if P is monotone, then any algorithm for evaluating P must ask Ω(s_PE+t_PE) queries for some input.

Evidence is given to suggest that minimally vertex colouring an interval graph may not be in NC¹. This is done by showing that 3-colouring a linked list is NC¹-reducible to minimally colouring an interval graph. However, it is shown that an interval graph with a known interval representation and an O(1) chromatic number can be minimally coloured in NC¹.

For the CRCW PRAM model, an o(log n) time, polynomial processors algorithm is obtained for minimally colouring an interval graph with o(log n) chromatic number and a known interval representation. In particular, when the chromatic number is O((log n)^1-ε), 0<ε<1, the algorithm runs in O(log n/log log n) time. Also, an O(log n) time, O(n) cost, EREW PRAM algorithm is found for interval graphs of arbitrary chromatic numbers. The following lower bound result is also obtained: even when the left and right endpoints of the interval are separately sorted, minimally colouring an interval graph needs Ω(log n/log log n) time, on a CRCW PRAM, with a polynomial number of processors.

We propose time-optimal algorithms for a number of convex polygon problems on meshes with multiple broadcasting. Specifically, we show that on a mesh with multiple broadcasting of size n × n, the task of deciding whether an n-gon is convex, deciding whether two convex n-gons edge-intersect, deciding whether one convex n-gon lies in the interior of another, as well as variants of the tasks of computing the intersection and union of two convex n-gons can be accomplished in Θ(log n) time. We also show that detecting whether two convex n-gons are separable takes O(1) time.

The purpose of this paper is to present non-trivial lower bounds for two classes of enhanced meshes. To achieve this goal we present efficient simulations of these two classes of enhanced meshes on the CREW-PRAM and Common-CRCW. From this, known computational lower bounds for the PRAM are transferred to the enhanced meshes. Our approach of transferring lower bounds from the PRAM to enhanced meshes is novel. Specifically, we show that any computation that takes O(t(n)) steps on an n-processor mesh with multiple broadcasting can be performed in O(t(n)) steps on an n-processor CREW-PRAM with O(n) extra memory. Similarly, with α standing for the inverse Ackermann function, we show that any computation that takes O(t(n)) computational steps on an n-processor basic reconfigurable mesh can be performed in O(α(n)t(n)) computational steps on an n-processor Common-CRCW with O(n) extra memory. We also show that some of the lower bounds that we derive are tight by providing matching upper bounds; as an example, we show that n items stored in one row of a mesh with multiple broadcasting can be sorted in O(log n) time and that this is time optimal. The best previously-known algorithm for this problem takes O(log² n) time.

We present time lower bounds for the permutation routing problem on three- and higher-dimensional n x…x n meshes with buses. We prove an (r–1)n/r lower bound for the general case of an r-dimensional bused mesh, r≥2, which is not as strong for low-dimensional as for higher-dimensional cases. We then use a different approach to construct a 0.705n lower bound for the three-dimensional case.

In the postal model of message passing systems, the actual communication network between processors is abstracted by a single communication latency factor, which measures the inverse ratio of the time it takes for a processor to send a message and the time that passes until the recipient receives the message. In this paper we examine the problem of broadcasting multiple messages in an order-preserving fashion in the postal model. We prove lower bounds for all parameter ranges and show that these lower bounds are within a factor of seven of the best upper bounds. In some cases, our lower bounds show significant asymptotic improvements over the previous best lower bounds.

Given a sequence of m items α₁, α₂,…, α_m from a semigroup S with an associative operation ⊕, the semigroup computation problem involves computing α₁ ⊕ α₂ ⊕…⊕ α_m. We consider the semigroup computation problem involving m (2≤m≤n) items on a mesh with multiple broadcasting of size . Our contribution is to present the first lower bound and the first time-optimal algorithm which apply to the entire range of m (2≤m≤n). Specifically, we show that any algorithm that solves the semigroup computation problem must take Ω(log m) time if and time for . We then show that our bound is tight by designing an algorithm whose running time matches the lower bound. These results unify and generalize all semigroup lower bounds and algorithms known to the authors.

We prove a separation between two models of the reconfigurable mesh (rmesh), the cross-over model and the non-cross-over model. Specifically, for any constant k ≥ 1, we show that in the non-cross-over model, a k × n rmesh requires Ω(log n) time to compute the parity of n bits stored one per column, while in the cross-over model, when k ≥ 3, a k × n rmesh can compute the parity in constant time. This is the first separation demonstrated between the cross-over and non-cross-over model. The lower bound does not rely on the bandwidth constraints of the mesh and does not restrict the instruction sets of the processors. Moreover, it is the first lower bound for the rmesh which requires only binary inputs.

We obtain lower bounds in the algebraic computation tree model for deciding the separability of two disjoint point sets. In particular, we show Ω(n log n) time lower bounds for separability by means of strips, wedges, wedges with apices on a given line, fixed-slopes double wedges, and triangles, which match the complexity of the existing algorithms, and therefore prove their optimality.

Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Rado conjectured 1/4 and proved 1/4.41. Motivated by the problem of channel assignment for wireless access points, in which use of 3 channels is a standard practice, we consider a variant where the selected subset of disks must be 3-colourable with disks of the same colour pairwise-disjoint. For this variant of the problem, we conjecture that it is always possible to cover at least 1/1.41 of the union area and prove 1/2.09. We also provide an O(n²) algorithm to select a subset achieving a 1/2.77 bound. Finally, we discuss some results for other numbers of colours.

We investigate one of the fundamental areas in computational geometry: lower bounds for range reporting problems in the pointer machine and the external memory models. We develop new techniques that lead to new and improved lower bounds for simplex range reporting as well as some other geometric problems.

Simplex range reporting is the problem of storing n points in the d-dimensional space in a data structure such that the k points that lie inside a query simplex can be found efficiently. This is one of the fundamental and extensively studied problems in computational geometry. Currently, the best data structures for the problem achieve Q(n) + O(k) query time using space in which the notation either hides a polylogarithmic or an n^ε factor for any constant ε > 0, (depending on the data structure and Q(n)). The best lower bound on this problem is due to Chazelle and Rosenberg who showed any pointer machine data structure that can answer queries in O(n^γ + k) time must use Ω(n^d-ε-dγ) space. Observe that this bound is a polynomial factor away from the best known data structures.

In this article, we improve the space lower bound to . Not only this bridges the gap from polynomial to sub-polynomial, it also offers a smooth trade-off curve. For instance, for polylogarithmic values of Q(n), our space lower bound almost equals Ω((n/Q(n))^d); the latter is generally believed to be the “right” bound.

By a simple geometric transformation, we also improve the best lower bounds for the halfspace range reporting problem. Furthermore, we study the external memory model and offer a new simple framework for proving lower bounds in this model. We show that answering simplex range reporting queries with Q(n)+O(k/B) I/Os requires ) space or blocks, in which B is the block size.

In this paper, we investigate the problem of finding the common tangents of two convex polygons that intersect in two (unknown) points. First, we give a Θ(log²n) bound for algorithms that store the polygons in independent arrays. Second, we show how to beat the lower bound if the vertices of the convex polygons are drawn from a fixed set of n points. We introduce a data structure called a compact interval tree that supports common tangent computations, as well as the standard binary-search-based queries, in O(logn) time apiece. Third, we apply compact interval trees to solve the subpath hull query problem: given a simple path, preprocess it so that we can find the convex hull of a query subpath quickly. With O(nlogn) preprocessing, we can assemble a compact interval tree that represents the convex hull of a query subpath in O(logn) time. In order to represent arrangements of Lines implicitly, Edelsbrunner et al. used a less efficient structure, called bridge trees, to solve the subpath hull query problem. Our compact interval trees improve their results by a factor of O(logn). Thus, the present paper replaces the paper on bridge trees referred to by Edelsbrunner et al.

We present a simple algorithm for maintaining order-k Voronoi diagrams in the plane. By using a duality transform that is of interest in its own right, we show that the insertion or deletion of a site involves little more than the construction of a single convex hull in three-space. In particular, the order-k Voronoi diagram for n sites can be computed in time and optimal space by an on-line randomized incremental algorithm. The time bound can be improved by a logarithmic factor without losing much simplicity. For k≥log² n, this is optimal for a randomized incremental construction; we show that the expected number of structural changes during the construction is ⊝(nk²). Finally, by going back to primal space, we obtain a dynamic data structure that supports k-nearest neighbor queries, insertions, and deletions in a planar set of sites. The structure promises easy implementation, exhibits a satisfactory expected performance, and occupies no more storage than the current order-k Voronoi diagram.

The class of n²-hard geometric problems is described, with special concentration on detecting collinearities among a set of points in the plane.

We found the lower bounds on the number of ones in fully indecomposable $(0,1)$ matrices such that their permanents are equal to the determinants of matrices obtained by a suitable change of signs in the entries. We consider separately general case and the case of symmetric matrices with vanishing diagonals.

This paper aims to develop numerical approximations of the Keller–Segel equations that mimic at the discrete level the lower bounds and the energy law of the continuous problem. We solve these equations for two unknowns: the organism (or cell) density, which is a positive variable, and the chemoattractant density, which is a non-negative variable. We propose two algorithms, which combine a stabilized finite element method and a semi-implicit time integration. The stabilization consists of a nonlinear artificial diffusion that employs a graph-Laplacian operator and a shock detector that localizes local extrema. As a result, both algorithms turn out to be nonlinear and can generate cell and chemoattractant numerical densities fulfilling lower bounds. However, the first algorithm requires a suitable constraint between the space and time discrete parameters, whereas the second one does not. We design the latter to attain a discrete energy law on acute meshes. We report some numerical experiments to validate the theoretical results on blowup and nonblowup phenomena. In the blowup setting, we identify a locking phenomenon that relates the $L^{\infty }(\mathrm{\Omega })$-norm to the $L^1(\mathrm{\Omega })$-norm limiting the growth of the singularity when supported on a macroelement.