We propose two high performance algorithms for motion estimation searching. The first algorithm express minimum mean square error motion estimation in terms of a cross-correlation computation; this approach reduces the number of multiply-adds needed by almost factor of two, with further improvement possible when fast cross-correlation algorithms are used. In the second algorithm we express the motion estimation computation in a form similar to the matrix-matrix multiplication computation. We propose an efficient algorithm for this computation. The algorithm exploits the memory hierarchy of the target processor and gives optimal performance for this formulation. In certain cases, both approaches can be used simultaneously.

We describe a parallel implementation of a MPEG-2 compliant, constant bit rate video encoder on a shared memory system. The emphasis is on techniques for obtaining compressed video with picture quality superior to that of commercially available real-time hardware encoders. We propose a novel scheme for bit allocation and rate control. The most remarkable aspect of this scheme is the analysis of future frames in order to determine bit allocation for the current frame. This analysis includes use of preliminary motion estimation, masking factor computation, and coding regions of future frames to model their coding complexity. To the best of our knowledge, this is the first instance of an MPEG encoder which integrates a detailed analysis of future frames in the bit-allocation/rate-control mechanism.

A parallelizable (or malleable) task is one which can be run on an arbitrary number of processors, with a task execution time that depends on the number of processors allotted to it. Consider a system of M independent parallelizable tasks which are to be scheduled without preemption on a parallel computer consisting of P identical processors. For each task, the execution time is a known function of the number of processors allotted to it. The goal is to find (1) for each task i, an allotment of processors β, and (2) overall, a non-preemptive schedule assigning the tasks to the processors which minimizes the average response time of the tasks. Equivalently, we can minimize the flow time which is the sum of the completion times of each of the tasks.

This paper discusses a parallel implementation of the e-relaxation algorithm for the rein-cost flow problem on the CM-5.There is considerable loss in et%ciency in going from one processor sequential implementation to one processor parallel implementation.While a naive parallelization is shown to have very low parallelism, we investigate the effectiveness of a set of algorithmic augmentations.These augmentations work by either eliminating non-parallel iterations or increasing the parallelism of the remaining iterations.Although the size of memory on the machine limits the size of problems used in our experiments, experimental scalability data shows that the parallel implementation may be able to beat the best sequential implementation on large enough problems.1 *Some of the performance data presented in this paper was derived using CMMD2.0-betaand CMOST7.2-betawhich are prerelease versions of system softwere for the CM-S from Thinking Machines Corp.

Using the ideas from the NC algorithm of Ben-Or and Tiwari [Journal of Complexity 6, 417-442, 1990], we develop a practical parallel algorithm that approximates the roots of a polynomial whose roots are all real.A new elementary proof of correctness is provided and the complexity of the algorithm is analyzed.A particular implementation of the algorithm that performs well in practice is described and its run-time behaviour is compared with the analytical predictions.Its performance is also compared with that of the root-finding algorithm in the PARI package.

It is proved that no finite computation tree with operations { +, -, *, /, mod, < } can decide whether the greatest common divisor (gcd) of a and b is one, for all pairs of integers a and b . This settles a problem posed by Gro¨tschel et al. Moreover, if the constants explicitly involved in any operation performed in the tree are restricted to be “0” and “1” (and any other constant must be computed), then we prove an Ω(log log n ) lower bound on the depth of any computation tree with operations { +, -, *, /, mod, < } that decides whether the gcd of a and b is one, for all pairs of n -bit integers a and b . A novel technique for handling the truncation operation is implicit in the proof of this lower bound. In a companion paper, other lower bounds for a large class of problems are proved using a similar technique.

A general lower bound technique is developed for computation trees with operations $\{ + , - , * ,/,\lfloor \cdot \rfloor , < \} $ and constants $\{ 0,1\} $, for functions that have as their input a single n-bit integer. The technique applies to many natural functions, such as perfect square root (deciding if the square root of the input is integral or not), computing the parity of $\lfloor {\log x} \rfloor $ , etc. The arguments are then extended to obtain the same lower bounds on the time complexity of any RAM program with operations $\{ + , - , * ,/,\lfloor \cdot \rfloor , < \} $ that solves the problem. Another related result is described in a companion paper [Proc. 29th IEEE Symposium on Foundations of Computer Science, 1988] and [J. Assoc. Comput. Mach., 1991, to appear].

We consider the problem of determining whether or not there exists a sparse univariate polynomial p(x) that interpolates a given set S = {(xi, Yi)} of points.Several important cases are resolved, e.g., the case when the zi's are all positive.But the general problem remains open.

Any implementation of Carter-Wegman universal hashing from n-bit strings to m-bit strings requires a time-space tradeoff of TS = f~(nm).The bound holds in the general boolean branching program model, and thus in essentially any model of computation.As a corollary, computing a + b • c in any field F requires a quadratic time-space tradeoff, and the bound holds for any representation of the elements of the field.Other lower bounds on the complexity of any implementation of universal hashing are given as well: Quadratic AT 2 bound for VLSI implementation; f~(log n) parallel time bound on a CREW PRAM; and exponential size for constant depth circuits.

The authors prove upper and lower bounds for approximately computing the square root using a given set of operations. The bounds are extended to hold for approximating the kth root, for any fixed k. Several tools from approximation theory are used to prove the lower bound. These include Markoff inequality, Chebyshev polynomials, and a theorem that relates the degree of a rational function to its deviation from the approximated function over a given interval. The lower bound can be generalized to other algebraic functions. The upper bound can be generalized to obtain an O(1)-step straight-line program for evaluating any rational function with integer coefficients at a given integer point.>

View an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with the lengths of random walks on the graph. For example, the commute time between two vertices s and t (the expected length of a random walk from s to t and back) is precisely characterized by the effective resistance Rst between s and t: commute time = 2mRst. Additionally, the cover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistance R in the graph to within a factor of log n: mR ≤ cover time ≤ O (mR log n). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, using this approach, we improve known bounds on cover times for various classes of graphs, including high-degree graphs, expanders, and multi-dimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.

This paper initiates the study of communication complexity when the processors have limited work space. The following tradeoffs between number C of communications steps and space S are proved:

An Omega (log log n) lower bound is proved on the depth of any computation tree with operations (+, -, /, mod,>

An efficient deterministic polynomial time algorithm is developed for the sparse polynomial interpolation problem. The number of evaluations needed by this algorithm is very small. The algorithm also has a simple NC implementation.

Given a polynomial $p(z)$ of degree n with m bit integer coefficients and an integer $\mu $, the problem of determining all its roots with error less than $2^{ - \mu } $ is considered. It is shown that this problem is in the class NC if $p(z)$ has all real roots. Some very interesting properties of a Sturm sequence of a polynomial with distinct real roots are proved and used in the design of a fast parallel algorithm for this problem. Using Newton identities and a novel numerical integration scheme for evaluating a contour integral to high precision, this algorithm determines good approximations to the linear factors of $p(z)$.

The main result of this paper is a general technique for determining lower bounds on the communication complexity of problems on various distributed computer networks. This general technique is derived by simulating the general network by a linear array and then using a lower bound on the communication complexity of the problem on the linear array. Applications of this technique yield optimal bounds on the communication complexity of merging, ranking, uniqueness, and triangle-detection problems on a ring of processors. Nontrivial near-optimal lower bounds on the communication complexity of distinctness, merging, and ranking on meshes and complete binary trees are also derived.

Article Free Access Share on A fast parallel algorithm for determining all roots of a polynomial with real roots Authors: M Ben-Or Hebrew University, Jerusalem, Israel Hebrew University, Jerusalem, IsraelView Profile , E Feig IBM Research, Yorktown Heights, NY IBM Research, Yorktown Heights, NYView Profile , D Kozen Dept. of Computer Science, Cornell University, Ithaca, NY Dept. of Computer Science, Cornell University, Ithaca, NYView Profile , P Tiwari Coordinated Science Lab., University of Illinois at Urbana-Champaign, Urbana, IL Coordinated Science Lab., University of Illinois at Urbana-Champaign, Urbana, ILView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 340–349https://doi.org/10.1145/12130.12165Published:01 November 1986Publication History 15citation381DownloadsMetricsTotal Citations15Total Downloads381Last 12 Months35Last 6 weeks16 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We prove that for almost all boolean functions f , the conmunication complexity of f on a linear array with p+1 processors is approximately p times its commuication complexity on a system with two processors. We use this result to develop a technique for establishing lower bounds on communication complexity on general networks by simulating them on linear arrays. Using this technique, we derive optimal lower bounds for ranking, distinctness, uniqueness and triangle-detection problems on the ring. The application of this technique to meshes and trees yields nontrivial near optimal lower bounds on the communicaton complexity of ranking and distinctness problems on these networks.