Rate of convergence of schmidt pairs and rational functions corresponding to best approximants of truncated hankel operators

The problem of approximating Hankel operators of infinite rank by finite-rank Hankel operators is considered. For efficiency, truncated infinite Hankel matrices ⁿ of are utilized. In this paper for any compact Hankel operator of the Wiener class, we derive the rate of l₂-convergence of the Schmidt pairs of ⁿ to the corresponding Schmidt pairs of . For a certain subclass of Hankel operators of the Wiener class, we also obtain the rate of l₁-convergence. In addition, an upper bound for the rate of uniform convergence of the rational symbols of best rank-k Hankel approximants of ⁿ to the corresponding rational symbol of the best rank-k Hankel approximant to asn is derived.Supported by SDIO/IST managed by the U.S. Army under Contract No. DAAL03-87-K-0025 and also supported by the National Science Foundation under Grant No. DMS 89-01345.     

Pathwise approximation and simulation for the Zakai filtering equation through operator splitting

Pathwise approximate solutions to the Zakai nonlinear filtering equation are analyzed and computed through operator splitting techniques. Several examples are presented to test the performances of the operator splitting algorithms. The work of R. Glowinski was supported by the U.S. Army Research Office under Contract DAAL03-86-K-0138 and by NSF via Grant INT-8612680.     

State representations form-D systems with generalized causality structures

This paper considers the definitions of recursive and statelike representations form-D systems modeled as operators on a partially ordered Hilbert resolution space.Using only the causality structure we develop a second-order transition representation which encompasses previously studied models. The same representation is shown to be valid for both quarter plane and arbitrary conic causality structures.Transformation of the transition representation into a first-orderm-D local state model leads to the concept of structural minimality. We develop explicit conditions which apply to both stationary and nonstationary cases.The transition representation also enables us to establish the existence of general 1-D wave advance model representations. Minimality of the wave advance model is also discussed.Supported in part by SDIO/IST and managed by ARO under Contract D24962-MA SDI.     

Optimal cooperative search in fractional cascaded data structures

Fractional cascading is a technique designed to allow efficient sequential search in a graph with catalogs of total sizen. The search consists of locating a key in the catalogs along a path. In this paper we show how to preprocess a variety of fractional cascaded data structures whose underlying graph is a tree so that searching can be done efficiently in parallel. The preprocessing takesO(logn) time withn/logn processors on an EREW PRAM. For a balanced binary tree, cooperative search along root-to-leaf paths can be done inO((logn)/logp) time usingp processors on a CREW PRAM. Both of these time/processor constraints are optimal. The searching in the fractional cascaded data structure can be either explicit, in which the search path is specified before the search starts, or implicit, in which the branching is determined at each node. We apply this technique to a variety of geometric problems, including point location, range search, and segment intersection search.An earlier version of this work appears inProceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, July 1990, pp. 307–316. The first author's support was provided in part by National Science Foundation Grant CCR-9007851, by the U.S. Army Research Office under Grants DAAL03-91-G-0035 and DAAH04-93-0134, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA Order 8225. This research was performed while the second author was at Brown University. Support was provided in part by an NSF Presidential Young Investigator Award CCR-9047466, with matching funds from IBM, by National Science Foundation Grant CCR-9007851, by the U.S. Army Research Office under Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA Order 8225.     

Dynamic expression trees

We present a technique for dynamically maintaining a collection of arithmetic expressions represented by binary trees (whose leaves are variables and whose internal nodes are operators). A query operation asks for the value of an expression (associated with the root of a tree). Update operations include changing the value of a variable and combining or decomposing expressions by linking or cutting the corresponding trees. Our dynamic data structure uses linear space and supports queries and updates in logarithmic time. An important application is the dynamic maintenance of maximum flow and shortest path in series-parallel digraphs under a sequence of vertex and edge insertions, series and parallel compositions, and their respective inverses. Queries include reporting the maximum flow or shortestst-path in a series-parallel subgraph.Research supported in part by the National Science Foundation under Grant CCR-9007851, by the US Army Research Office under Grants DAAL03-91-G-0035 and DAAH04-93-0134, by the Office of Naval Research and the Defense Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA Order 8225, and by Cadre Technologies, Inc.     

An efficient parallel algorithm for shortest paths in planar layered digraphs

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs.We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log² n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log² n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model.Support for the first and third authors was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA, Order 8225. Support for the second author was provided in part by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052 and ARPA Order 8225.     

On the control of discrete-event dynamical systems

We study a class of problems related to the supervisory control of a discrete-event system (DES), as formulated by Ramadge and Wonham, and we focus on the computational effort required for their solution. While the problem of supervisory control of a perfectly observed DES may be easily solved by dynamic programming, the problem becomes intractable (in the sense of complexity theory) when imperfectly observed systems are considered. Research supported by the Army Research Office (Grant No. DAAL03-86-K-0171) and by an NSF PYI award, with matching funds from Bellcore Inc.     

A note on weighted distributed match-making

In many distributed computing environments, processes are concurrently executed by nodes in a store-and-forward network. Distributed control issues as diverse as name-server, mutual exclusion, and replicated data management, involve making matches between processes. The generic paradigm is a formal problem called “distributed match-making.” We define multidimensional and weighted versions, and the relations between the two, and develop a very general method to prove lower bounds on the complexity as a tradeoff between number of messages and “distributedness.” The resulting lower bounds are tight in all cases we have examined. We present a success-stop version of distributed match-making that is analysed in terms of a weight distribution that in all cases results in approximately halving the (expected) number of messages required in the corresponding strategy that does not use these weights. The second author did part of this work at the Laboratory for Computer Science, M.I.T., Cambridge, MA. He was supported in part by the Office of Naval Research under Contract N00014-85-K-0168, by the Office of Army Research under Contract DAAG29-84-K-0058, by the National Science Foundation under Grant DCR-83-02391, and by the Defence Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125. A preliminary version of this paper appeared inProc. VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing (AWOC 88), Lecture Notes in Computer Science, vol. 319, Springer-Verlag, Berlin, 1988, pp. 361–368.     

Local tests for consistency of support hyperplane data

Support functions and samples of convex bodies in R ⁿ are studied with regard to conditions for their validity or consistency. Necessary and sufficient conditions for a function to be a support function are reviewed in a general setting. An apparently little known classical such result for the planar case due to Rademacher and based on a determinantal inequality is presented and a generalization to arbitrary dimensions is developed. These conditions are global in the sense that they involve values of the support function at widely separated points. The corresponding discrete problem of determining the validity of a set of samples of a support function is treated. Conditions similar to the continuous inequality results are given for the consistency of a set of discrete support observations. These conditions are in terms of a series of local inequality tests involving only neighboring support samples. Our results serve to generalize existing planar conditions to arbitrary dimensions by providing a generalization of the notion of nearest neighbor for plane vectors which utilizes a simple positive cone condition on the respective support sample normals.This work partially supported by the Center for Intelligent Control Systems under the U.S. Army Research Office Grant DAAL03-92-G-0115, the Office of Naval Research under Grant N00014-91-J-1004, and the National Science Foundation under Grant MIP-9015281.Partially supported by the National Science Foundation under grant IRI-9209577 and by the U.S. Army Research Office under grant DAAL03-92-G-0320     

Near-Horn Prolog and beyond

Near-Horn Prolog is an extension of Prolog designed to handle disjunction and classical negation. The emphasis here is on minimal change from standard Prolog in regard to notation, derivation form, and speed of inner-loop computation. The procedure is optimized for the input program that is near-Horn; i.e., a program where almost all clauses are definite clauses. This paper goes beyond the near-Horn focus to report on the completeness of one version of nH-Prolog, along with soundness of the procedure. Completeness is important here not only for the usual reasons of guaranteed success on small problems and insight into the behavior of the procedure but also because we anticipate the introduction of negation-as-failure which requires conviction that a proof will be found if a proof exists.This research was supported in part by the U.S. Army Research Office under grants DAAG29-84-K-0072 and DAAL03-88-K-0082 and by NSF Grant IRI-8805696.     

Bounded time-stamps

Summary Time-stamps are labels which a system adds to its data items. These labels enable the system to keep track of the temporal precedence relations among its data elements. Many distributed protocols and some applications use the natural numbers as time-stamps. The natural numbers however are not useful for bounded protocols. In this paper we develop a theory ofbounded time-stamps. Time-stamp schemes are defined and the complexity of their implementation is analyzed. This indicates a direction for developing a general tool for converting time-stamp based protocols to bounded protocols. Amos Israeli received his B.Sc. in Mathematics and Physics from Hebrew University in 1976, and his M.Sc. and D.Sc. in Computer Science from the Weizmann Institute in 1980 and the Technion in 1985, respectively. Currently he is a senior lecturer at the Tlectrical Engineering Department at the Technion. Prior to this he was a postdoctoral fellow at the Aiken Computation Laboratory at Harvard. His research interests are in Parallel and Distributed Computing and in Robotics. In particular he has worked on the design and analysis of Wait-Free and Self-Stabilizing distributed protocols. Ming Li received his M.S. and Ph.D. in Computer Science from Wayne State University in 1980 and Cornell University 1985, respectively. Currently he is an associate professor at the Computer Science Department at the University of Waterloo. His research interests are in Theory of Computing, Kolmogorov Complexity, and Machine Learning.Supported in part by the Weizmann fellowship and NSF Grant DCR-86-00379Supported in part by ONR Grant N00014-85-k-0445 and Army Research Office Grant DAAL03-86-K-0171 at Harvard University, by NSF Grant kDCR-86-06366 at Ohio State University, and by NSERC Operating Grant OGP0036747. Most of this work was done when the authors were at Aiken Computation Laboratory at Harvard University. The authors also acknowledge the hospitality of the computer science department at York University, Canada     

Computational complexity of optimum multiuser detection

Optimum centralized demodulation of the independent data streams transmitted simultaneously by several users through a Code Division Multiple-Access channel is considered. Each user sends an arbitrary assigned signal waveform, which is linearly modulated by symbols drawn from a finite alphabet. If the users are asynchronous, the optimum multiuser detector can be implemented by a Viterbi algorithm whose time-complexity is linear in the number of symbols transmitted by each user and exponential in the number of users. It is shown that the combinatorial problem of selecting the most likely transmitted data stream given the sufficient statistics (sequence of matched filter outputs), and the signal energies and cross-correlations is nondeterministic polynomial-time hard (NP-hard) in the number of users. And it remains so even if the users are restricted to be symbol-synchronous.The performance analysis of optimum multiuser detection in terms of the set of multiuser asymptotic efficiencies is equivalent to the computation of the minimum Euclidean distance between any pair of distinct multiuser signals. This problem is also shown to be NP-hard and a conjecture on a longstanding open problem in single user data communication theory is presented.This work was partially supported by the National Science Foundation under Grant ECS-8504752, and by the US Army Research Office under Contract DAAL03-87-K-0062.     

On the analysis of cooperation and antagonism in networks of communicating processes

We propose a new method for the analysis of cooperative and antagonistic properties of communicating finite state processes (FSPs). This algebraic technique is based on a composition operator and on the notion of possibility equivalence among FSPs. We demonstrate its utility by showing that potential blocking, termination, and lockout can be decided in polynomial time for loosely connected networks of tree FSPs. Potential blocking and termination are examples of cooperative properties, while lockout is an antagonistic one. For loosely connected networks of (the more general) acyclic FSPs, the cooperative properties become NP-complete and the antagonistic ones PSPACE-complete. For tightly coupled networks of tree FSPs, we also have NP-completeness for the cooperative properties. For the harder case of FSPs with cycles, we provide a natural extension of the method.A preliminary version of this paper appeared as an extended abstract in theProceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, August, 1985, pp. 23–38. P. C. Kanellakis was supported by ONR-DARPA Grant N00014-83-K-0146, NSF Grant DCR-8302391, and by the Office of Army Research under contract DAAG29-84-K-0058. S. A. Smolka was supported by National Science Foundation Grant DCR-8505873.     

Achieving speedups for APL on an SIMD distributed memory machine

The potential speedup for SIMD parallel implementations of APL programs is considered. Both analytical and (simulated) empirical studies are presented. The approach is to recognize that nearly 95% of the operators appearing in APL programs are either scalar primitive, reduction or indexing and so the performance of these operators gives a good estimate of the amount of speedup a full program might receive. Substantial speedups are demonstrated for these operators and the empirical evidence accords with the analytical estimates.This research has been funded by the Office of Naval Research Contract No. N00014-86-K-0264 and the National Science Foundation Grant No. DCR 8416878.     

Convex hulls of objects bounded by algebraic curves

We present an0(n ·d ^o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.Research supported in part by NSF Grant MIP-85 21356, ARO Contract DAA G29-85-C0018 under Cornell MSI, and ONR Contract N00014-88-K-0402. This paper is an updated version of a part of [6].     

Least upper bound on the cost of optimum binary search trees

Summary This paper gives the least upper bound on the weighted path length of an optimum lexicographic (alphabetic) binary search tree as a function of n, given the total weight of the n terminal nodes and the n—1 internal nodes to be one.This research was sponsored by the United States Army under Contract No.: DA-31-124-ARO-D-462, and National Science Foundation Grant GJ-28339.     

Decentralized detection by a large number of sensors

We consider the decentralized detection problem, in whichN independent, identical sensors transmit a finite-valued function of their observations to a fusion center which then decides which one ofM hypotheses is true. For the case where the number of sensors tends to infinity, we show that it is asymptotically optimal to divide the sensors intoM(M-1)/2 groups, with all sensors in each group using the same decision rule in deciding what to transmit. We also show how the optimal number of sensors in each group may be determined by solving a mathematical programming problem. For the special case of two hypotheses and binary messages the solution simplifies considerably: it is optimal (asymptotically, asN→∞) to have all sensors perform an identical likelihood ratio test, and the optimal threshold is very easy to determine numerically. Research supported by the Army Research Office under Contract DAAG-29-84-K-0005 and by the Office of Naval Research under Contract N00014-84-K-0519.     

The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the firstn/logn processor,O(logn)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.Richard Cole was supported in part by NSF Grants DCR-84-01633 and CCR-8702271, ONR Grant N00014-85-K-0046 and by an IBM faculty development award. Uzi Vishkin was supported in part by NSF Grants NSF-CCR-8615337 and NSF-DCR-8413359, ONR Grant N00014-85-K-0046, by the Applied Mathematical Science subprogram of the office of Energy Research, U.S. Department of Energy under Contract DE-AC02-76ER03077 and the Foundation for Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences and Humanities.     

On the parallel-decomposability of geometric problems

There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n ^1/d ) on ad-dimensionaln-processor array), and they all assume that the parallel machine is trying to solve a problem of sizen on ann-processor array. Here we investigate the situation where we have a mesh of sizep and we are interested in using it to solve a problem of sizen >p. The goal we seek is to achieve, when solving a problem of sizen >p, the same speed up as when solving a problem of sizep. We show that for many geometric problems, the same speedup can be achieved when solving a problem of sizen >p as when solving a problem of sizep.The research of M. J. Atallah was supported by the Office of Naval Research under Contracts N00014-84-K-0502 and N00014-86-K-0689, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, the National Science Foundation under Grant DCR-8451393, and the National Library of Medicine under Grant R01-LM05118. Jyh-Jong Tsay's research was partially supported by the Office of Naval Research under Contract N00014-84-K-0502, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, and the National Science Foundation under Grant DCR-8451393.     

Blocking for external graph searching

In this paper we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for completed-ary trees andd-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex. We also show that, for the special case of grid graphs blocked with isothetic hypercubes, there is a provably better speed-up if even a small amount of redundancy is permitted.Support was provided in part by an IBM Graduate Fellowship, by NSF Research Grants CCR-9007851 and IRI-9116451, and by Army Research Office Grant DAAL03-91-G-0035.Support was provided in part by NSF Grants CCR-9003299, CCR-9300079, and IRI-9116843, and by NSF/DARPA Grant CCR-8908092.Support was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, and by Army Research Office Grant DAAL03-91-G-0035.