Oblique projections: Formulas,algorithms, and error bounds

When an orthogonal projection is to be computed using data acquired by distributed sensors, it is often necessary to process each sensor's data locally and then transmit the results to a central facility for final processing. The most efficient way to do this is to compute oblique projections locally. This choice makes the final processing a matter of summing the oblique projections. In this paper we derive new formulas, and iterative algorithms and associated error bounds, for oblique projections in arbitrary Hilbert spaces. This work was supported by the Office of Naval Research under Contract N00014-85-K-0255.     

A new explanation of the glitch phenomenon

Summary We consider a discrete model for asynchronous circuits and show that, under very mild restrictions, this model excludes the existence of glitch-free arbiters. This result contradicts a long standing conjecture that the nonexistence of glitch-free arbiters is due to the continuous nature of such circuits.Work supported in part by Office of Naval Research Contract N00014-89-J-1913     

The complexity of planar compliant motion planning under uncertainty

We consider the computational complexity of planning compliant motions in the plane, given geometric bounds on the uncertainty in sensing and control. We can give efficient algorithms for generating and verifying compliant motion strategies that are guaranteed to succeed as long as the sensing and control uncertainties lie within the specified bounds. We also consider the case where a compliant motion plan is required to succeed over some parametric family of geometries. While these problems are known to be intractable in three dimensions, we identify tractable subclasses in the plane.This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's Artificial Intelligence research is provided in part by the Office of Naval Research under Office of Naval Research Contract N00014-81-K-0494 and in part by the Advanced Research Projects Agency under Office of Naval Research Contracts N00014-85-K-0124 and N00014-82-K.-0334. The author was funded in part by a NASA fellowship administered by the Jet Propulsion Laboratory, and in part by the Mathematical Sciences Institute and the National Science Foundation.     

A note on series parallel irreducibility

A new criterion for series-parallel irreducibility is given which makes no reference to underlying semigroups but involves only series-parallel connection operations.Research was sponsored by National Institutes of Health, Grant No. GM-12236-03; Office of Naval Research, Contract No. N00014-67-A-0181-011; and U.S. Army Research Office (Durham), Grant No. DA-31-124-ARO-D-483.     

Error bounds for the method of alternating projections

Given a collection of closed subspaces of a Hilbert space, the method of alternating projections produces a sequence which converges to the orthogonal projection onto the intersection of the subspaces. A large class of problems in medical and geophysical image reconstruction can be solved using this method. A sharp error bound will enable the userto estimate accurately the number of iterations necessary to achieve a desired relative error. We obtain the sharpest possible upper bound for the case of two subspaces, and the sharpest known upper bound for more than two subspaces. This work was supported by the Office of Naval Research under Contract N00014-85-K-0255.     

How to clear a block: A theory of plans

Problems in commonsense and robot planning are approached by methods adapted from program synthesis research; planning is regarded as an application of automated deduction. To support this approach, we introduce a variant of situational logic, called plan theory, in which plans are explicit objects.A machine-oriented deductive-tableau inference system is adapted to plan theory. Equations and equivalences of the theory are built into a unification algorithm for the system. Frame axioms are built into the resolution rule.Special attention is paid to the derivation of conditional and recursive plans. Inductive proofs of theorems for even the simplest planning problems, such as clearing a block, have been found to require challenging generalizations.This research was supported by the National Science Foundation under Grants DCR-82-14523 and DCR-85-12356, by the Defense Advanced Research Projects Agency under Contract N00039-84-C-0211, by the United States Air Force Office of Scientific Research under Contract AFOSR-85-0383, by the Office of Naval Research under Contract N00014-84-C-0706, by United States Army Research under Contract DAJA-45-84-C-0040, and by a contract from the International Business Machines Corporation.Preliminary versions of parts of this paper were presented at the Eighth International Conference on Automated Deduction, Oxford, England, July 1986, and the Workshop on Planning and Reasoning about Actions, Timberline, Oregon, July 1986.     

Towards systolizing compilation

Summary A scheme for the compilation of imperative or functional programs into systolic programs is demonstrated on matrix composition/decomposition and Gauss-Jordan elimination. Using this scheme, programs for the processor network Warp and for several transputer networks have been generated. Christian Lengauer holds a Dipl. Math. (1976) from the Free University of Berlin, and an M.Sc (1978) and Ph.D. (1982) in Computer Science from the University of Toronto. He was an Assistant Professor of Computer Sciences at The University of Texas at Austin from 1982 to 1989 and is presently a Lecturer in Computer Science at the University of Edinburgh. His past research has been in the areas of systolic design, formal semantics and program construction, and automated theorem proving. Michael Barnett received a B.A. in Computer Science from Brooklyn College/City University of New York in 1985, and is currently a Ph.d. candidate at the University of Texas at Austin, where he has been since 1986. From 1985 to 1986 he worked at IBM's T.J. Watson Research Center. His current research interests include formal methods, programming methodology, and functional programming. Duncan G. Hudson III received the B.A. degree in computer sciences from The University of Texas at Austin in 1987 and the M.S.C.S. degree in computer sciences from The University of Texas at Austin in 1989. He has worked as a Graduate Research Assistant at The University of Texas at Austin in the areas of graphical parallel programming environments, parallel numerical algorithms, and objectoriented programming languages for parallel architectures and as a Software Design Engineer at Texas Instruments in the areas of objectoriented databases and parallel image understanding. He is currently a Ph.D. candidate in the Department of Computer Sciences at The University of Texas at Austin. His current research interests include parallel architectures and algorithms and parallelizing compilers.This research was supported in part by the following funding agencies: through Carnegie-Mellon University by the Defense Advanced Research Projects Agency monitored by the Space and Naval Warfare Systems Command under Contract N00039-87-C-0251 and by the Office of Naval Research under Contracts N00014-87-K-0385 and N00014-87-K-0533; through Oxford University by the Science and Engineering Research Council under Contract GR/E 63902; through the University of Texas at Austin by the Office of Naval Research under Contract N00014-86-K-0763 and by the National Science Foundation under Contract DCR-8610427     

A technique for constructing highly available services

This paper describes a general method for constructing a highly available service for use in a distributed system. It gives a specific implementation of the method and proves the implementation correct. The service consists of replicas that reside at several different locations in a network. It presents its clients with a consistent view of its state, but the view may contain old information. Clients can indicate how recent the information must be. The method can be used in applications satisfying certain semantic constraints. For applications that can use it, the method performs better than other replication techniques.This research was supported in part by the Advanced Research Projects Agency of the Department of Defense, monitored by the Office of Naval Research under Contract No. N00014-83-K.-0125, by the National Science Foundation under Grant No. DCR-8503662, and by the HTI Postdoctoral Fellowship.     

On multiple moving objects

This paper explores the motion-planning problem for multiple moving objects. The approach taken consists of assigning priorities to the objects, then planning motions one object at a time. For each moving object, the planner constructs a configuration space-time that represents the time-varying constraints imposed on the moving object by the other moving and stationary objects. The planner represents this space-time approximately, using two-dimensional slices. The space-time is then searched for a collision-free path. The paper demonstrates this approach in two domains. One domain consists of translating planar objects; the other domain consists of two-link planar articulated arms.This report describes research performed at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Michael Erdmann is supported in part by a fellowship from General Motors Research Laboratories. Tomás Lozano-Pérez is supported by an NSF Presidential Young Investigator grant. Support for the Laboratory's Artificial Intelligence research is provided in part by the System Development Foundation, in part by the Office of Naval Research under Office of Naval Research Contract N00014-81-K-0494, and in part by the Advanced Research Projects Agency under Office of Naval Research Contracts N00014-80-C-0505 and N00014-82-K-0344.     

Distributed match-making

In many distributed computing environments, processes are concurrently executed by nodes in a store- and-forward communication network. Distributed control issues as diverse as name server, mutual exclusion, and replicated data management involve making matches between such processes. We propose a formal problem called distributed match-making as the generic paradigm. Algorithms for distributed match-making are developed and the complexity is investigated in terms of messages and in terms of storage needed. Lower bounds on the complexity of distributed match-making are established. Optimal algorithms, or nearly optimal algorithms, are given for particular network topologies.The work of the second author 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. Current address of both authors: CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.     

Small-μ theorems with frequency-dependent uncertainty bounds

We present conditions, some necessary and some sufficient, valid under weak assumptions, for robust stability and uniform robust stability of uncertain linear time-invariant systems with linear time-invariant uncertainties that are block-diagonal, with known frequency-dependent norm bounds on the diagonal, blocks. Small-μ theorems with frequency-independent uncertainty bounds are recovered as special cases. This research was in part supported by NSF’s Engineering Research Center No. NSFD-CDR-88-03012, and in part by the Office of Naval Research under Contract No. N00014-97-1-0640.     

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.     

ParaGraph: Graph editor support for parallel programming environments

We report here on a graph editor, ParaGraph, that supports massively parallel programming. It provides a flexible mechanism for the concise specification of families of annotated graphs, addressing the problems of user annotation and scale independent graph manipulation. ParaGraph currently serves as the basis for tools supporting communication abstractions in program specification and debugging. Its foundation in an extended form of aggregate rewriting graph grammars makes its adaptation to other parallel programming environments straightforward.The Parallel Programming Environments Project at the University of Massachusetts is supported by the Office of Naval Research under Contract N000014-84-K-0647 and by the National Science Foundation under Grants DCR-8500332 and CCR-8712410.     

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.     

Deadlock-freedom in resource contentions

Summary The paper establishes two necessary and sufficient conditions for the absence of deadlock in resource contentions under the expedient allocation policy. Their equivalence is proved. One of these was discovered independently by Ibaraki and Kameda. The conditions are essentially the condition of the König-Hall Theorem for the existence of a system of distinct representatives. If there are no multiple resources the conditions simplify to the condition for acyclicity of hypergraphs.This work was sponsored by the Defense Advanced Research Projects Agency ARPA Order 3771 and monitored by the Office of Naval Research under Contract N00014-79-C-0597. It was carried out at the California Institute of Technology     

Controllability and stability radii for companion form systems

This paper describes a unifying approach to the computation of certain robustness measures for some calculations involving state space models in control and system theory. These measures include nearness to uncontrollability, nearness to instability, and nearness to unstabilizability and their duals. Specialized results are provided for systems in companion form (controllability canonical form, etc.). It is shown analytically why high-order companion system models have certain undesirable numerical properties. For example, it is shown that almost all highorder companion matrices are nearly singular and almost all high-order controllable canonical forms are nearly uncontrollable. This research was supported by the Office of Naval Research under Contract No. N00014-85-K-0553 and the National Science Foundation (and AFOSR) under Grant No. ECS-8718897.     

A full sensing window Random-Access algorithm for messages with strict delay constraints

We consider the Channel Multiple-Access problem for messages with strict delay constraints. The constraints are represented by an upper bound on the transmission delays. For this problem, and for binary collision-noncollision feedback per slot, we present a simple full sensing window Random-Access algorithm. We analyze the algorithm and we compute the fraction of maintained traffic and the expected delay for the successfully transmitted packet, for various input Poisson intensities and various values of the bound on the transmission delays.This work was supported by the U.S. Office of Naval Research, under Contract ONR-N14-86-K-0742.     

The general maximum matching algorithm of micali and vazirani

We give a clear exposition of the algorithm of Micali and Vazirani for computing a maximum matching in a general graph. This is the most efficient algorithm known for general matching. On a graph withn vertices andm edges this algorithm runs inO(n ^1/2 m) time.Work on this paper has been supported by the Office of Naval Research under Contract N00014-85-K-0570 and by the Eastman Kodak Company.     

Orthogonality of information structures

Summary In the mathematical framework of data spaces the paper develops some important general principles of information structuring. These principles are related to the notions of redundancy of information, completeness of a set of access paths, information sharing and compounding, and virtual access to information. The results are relevant to both sequential and concurrent processing.This research is supported in part by the Office of Naval Research under Contract No. N00014-77-C-0536 through the University of Southern CaliforniaA version of this paper was presented at the Conference on Theoretical Computer Science, University of Waterloo, Waterloo, Ontario, Canada, Aug. 15–17, 1977     

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.