Recursive mesh refinement on hypercubes

Adaptive methods for PDEs can be viewed as a graph problem. An efficient parallel implementation of adaptive PDE methods then requires distributing the nodes of the associated graph uniformly across the processors so that the resulting cost of communication between processors is low.We solve this problem in two phases: labeling of graph nodes and subsequent mapping of these labels onto processors. We describe a new form of Gray-code which we call aninterleaved Gray-code that allows easy labeling of graph nodes when the maximal level of refinement is unknown, allows easy determination of nearby nodes in the graph, is completely deterministic, and often (in a well-defined sense) distributes the graph uniformly across a hypercube. The theoretical results are supported by computational experiments on the Connection Machine.The work presented in this paper was supported by the Office of Naval Research under contract N00014-85-K-0461, by the Army Research Office under contract DAAL03-86-K-0158, by the Office of Naval Research under contract number N00014-86-K-0310 and the National Science Foundation under contract number DCR 8521451. Part of this work was performed while the second author was in residence at the Computer Science and Systems Division of Harwell Laboratory, United Kingdom.     

Necessary and sufficient conditions for the existence of complementary solutions and characterizations of the matrix classesQ andQ 0

We simplify a result by Mangasarian on the existence of solutions to the linear complementarity problem. The simplified condition gives a new geometric interpretation of the result. When used to characterize the matrix classesQ andQ ₀, our condition suggests a finitely checkable sufficient condition forP andP ₀.This work was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0173, and by general research development funds provided by the Georgia Institute of Technology.     

Simplified Voronoi diagrams

We are interested in Voronoi diagrams as a tool in robot path planning, where the search for a path in anr-dimensional space may be simplified to a search on an (r–1)-dimensional Voronoi diagram. We define a Voronoi diagramV based on a measure of distance which is not a true metric. This formulation has lower algebraic complexity than the usual definition, which is a considerable advantage in motion-planning problems with many degrees of freedom. In its simplest form, the measure of distance between a point and a polytope is the maximum of the distances of the point from the half-spaces which pass through faces of the polytope. More generally, the measure is defined in configuration spaces which represent rotation. The Voronoi diagram defined using this distance measure is no longer a strong deformation retract of free space, but it has the following useful property: any path through free space which starts and ends on the diagram can be continuously deformed so that it lies entirely on the diagram. Thus it is still complete for motion planning, but it has lower algebraic complexity than a diagram based on the Euclidean metric.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. John Canny was supported by an IBM fellowship. Bruce Donald was funded in part by a NASA fellowship administered by the Jet Propulsion Laboratory.     

Edge-clique graphs

The edge-clique graphK(G) of a graphG is that graph whose vertices correspond to the edges ofG and where two vertices ofK(G) are adjacent whenever the corresponding edges ofG belong to a common clique. It is shown that every edge-clique graph is a clique graph, and that ifG is either an interval graph or a line graph, then so too isK(G). An algorithm is provided for determining whether a graph is an edge-clique graph. A new graph called the STP graph is introduced and a relationship involving this graph, the edge-clique graph, and the line graph is presented. The STP graphs are also characterized.Research supported in part by Office of Naval Research Contract N00014-88-K-0018.Research supported in part by Office of Naval Research Contract N00014-88-K-0163.     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

A new approach to the dynamic maintenance of maximal points in a plane

A pointp _i=(x _i, y_i) in thex–y plane ismaximal if there is no pointp _j=(x _j, y_j) such thatx _j>x_i andy _j>y_i. We present a simple data structure, a dynamic contour search tree, which contains all the points in the plane and maintains an embedded linked list of maximal points so thatm maximal points are accessible inO(m) time. Our data structure dynamically maintains the set of points so that insertions takeO(logn) time, a speedup ofO(logn) over previous results, and deletions takeO((logn)²) time.The research of the first author was partially supported by the National Science Foundation under Grant No. DCR-8320214 and by the Office of Naval Research on Contract No. N 00014-86-K-0689. The research of the second author was partially supported by the Office of Naval Research on Contract No. N 00014-86-K-0689.     

Effect of model uncertainty on some optimal routing problems

We study the effect of model uncertainties on optimal routing in a system of parallel queues. The uncertainty arises in modeling the service time distribution for the customers (jobs, packets) to be served. For a Poisson arrival process and Bernoulli routing, the optimal mean system delay generally depends on the variance of this distribution. However, as the input traffic load approaches the system capacity, the optimal routing assignment and corresponding mean system delay are shown to converge to a variance-invariant point. The implications of these results are examined in the context of gradient-based routing algorithms. An example of a model-independent algorithm using on-line gradient estimation is also included and its performance compared with that of model-based algorithms.This work was supported in part by the National Science Foundation under Grant ECS-88-01912, by the Office of Naval Research under Contract N00014-87-K-0304, and by NASA under Contract NAG 2-595.     

On stable laws for estimating functions and derived estimators

Summary Stable laws forM-estimators, maximum likelihood and other estimators and obtained through parallel results for the estimating functions and relative compactness of some related estimating functional processes. Work supported by the Office of Naval Research, Contract No. N00014-83-K-0387.     

Minimizing pseudoconvex functions on convex compact sets

An algorithm is presented which minimizes continuously differentiable pseudoconvex functions on convex compact sets which are characterized by their support functions. If the function can be minimized exactly on affine sets in a finite number of operations and the constraint set is a polytope, the algorithm has finite convergence. Numerical results are reported which illustrate the performance of the algorithm when applied to a specific search direction problem. The algorithm differs from existing algorithms in that it has proven convergence when applied to any convex compact set, and not just polytopal sets.This research was supported by the National Science Foundation Grant ECS-85-17362, the Air Force Office Scientific Research Grant 86-0116, the Office of Naval Research Contract N00014-86-K-0295, the California State MICRO program, and the Semiconductor Research Corporation Contract SRC-82-11-008.     

Two approaches to optimal routing and admission control in systems with real-time traffic

This paper addresses the problem of routing and admission control of real-time traffic in a queueing system where customers must begin service within given deadlines (or complete service within given deadlines), otherwise they are considered lost. Performance in such systems is measured by the probability a customer is lost. For a system ofK parallel servers with a probabilistic routing and admission control scheme, the problem of the optimal routing and admission control is considered and two approaches are presented. Assuming the availability of a closed-form expression for the probability of loss at each server, the problem is solved under general conditions and properties of the optimal flow allocation are given. However, such closed-form expressions are often unavailable. This motivates a second approach, which involves a gradient-based stochastic optimization algorithm with on-line gradient estimation. The gradient estimation problem for loss probabilities is solved through a recently-developed smoothed perturbation analysis (SPA) technique. The effectiveness of on-line stochastic optimization using this type of gradient estimator is demonstrated by combining the SPA algorithm with a sampling-controlled stochastic optimization algorithm for the aforementioned routing and admission control problem.This work was supported in part by the Office of Naval Research under Contract N00014-87-K-0304, by the Rome Air Development Center under Contract F30602-88-D-0027, by NASA under Contract NAG 2-595, and by the National Science Foundation under Grant EID-92-12122.The authors are grateful to Don Towsley for several contributions to Section 2 and to an anonymous reviewer for pointing out a redundant assumption in the proof of Lemma 2.1.     

Canonical representations of partial 2- and 3-trees

We give algorithms constructing canonical representations of partial 2-trees (series parallel graphs) and partial 3-trees. The algorithms can be implemented in log-linear space, or in linear time using quadratic space.Supported in part by a grant from the Swedish Natural Science Research Council.Research supported in part by the Office of Naval Research Contract N00014-86-K-0419.     

Efficient representation of perm groups

This note presents an elementary version of Sims's algorithm for computing strong generators of a given perm group, together with a proof of correctness and some notes about appropriate lowlevel data structures. Upper and lower bounds on the running time are also obtained. (Following a suggestion of Vaughan Pratt, we adopt the convention that perm=permutation, perhaps thereby saving millions of syllables in future research.)Dedicated to the memory of Marshall HallThis research was supported in part by the National Science Foundation under grant CCR-86-10181, and by Office of Naval Research contract N00014-87-K-0502.     

Stopping rules,permutation invariance and sufficiency principle

In the context of sequential (point as well as interval) estimation, a general formulation of permutation-invariant stopping rules is considered. These stopping rules lead to savings in the ASN at the cost of some elevation of the associated risk—a phenomenon which may be attributed to the violation of the sufficiency principle. For the (point and interval) sequential estimation of the mean of a normal distribution, it is shown that such permutation-invariant stopping rules may lead to a substantial saving in the ASN with only a small increase in the associated risk.Work partially supported by (i) Office of Naval Research, Contract Number N00014-85-K-0548, and (ii) Office of Naval Research, Contract Number N00014-83-K-0387.     

Mean stochastic comparison of diffusions

Summary Stochastic bounds are derived for one dimensional diffusions (and somewhat more general random processes) by dominating one process pathwise by a convex combination of other processes. The method permits comparison of diffusions with different diffusion coefficients. One interpretation of the bounds is that an optimal control is identified for certain diffusions with controlled drift and diffusion coefficients, when the reward function is convex. An example is given to show how the bounds and the Liapunov function technique can be applied to yield bounds for multidimensional diffusions.This work was supported by the Office of Naval Research under Contract N00014-82-K-0359 and the U.S. Army Research Office under Contract DAAG29-82-K-0091 (administered through the University of California at Berkeley).     

Linear/nonlinear forms and the normal law: Characterization by high order correlations

Summary The problem of characterizing the normal law associated with linear forms and processes, as well as with quadratic forms, is considered. The classical condition of constancy of regression is replaced by a distinct condition of high-order uncorrelatedness. The work of E. Masry was supported by the Office of Naval Research under Contract N00014-84-K-0042.     

Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph

An upper bound is given on the number of acyclic orientations of a graph, in terms of the spectrum of its Laplacian. It is shown that this improves upon the previously known bound, which depended on the degree sequence of the graph. Estimates on the new bound are provided.A lower bound on the number of acyclic orientations of a graph is given, with the help of the probabilistic method. This argument can take advantage of structural properties of the graph: it is shown how to obtain stronger bounds for small-degree graphs of girth at least five, than are possible for arbitrary graphs. A simpler proof of the known lower bound for arbitrary graphs is also obtained.Both the upper and lower bounds are shown to extend to the general problem of bounding the chromatic polynomial from above and below along the negative real axis.Partially supported by the NSF under grant CCR-9404113. Most of this research was done while the author was at the Massachusetts Institute of Technology, and was supported by the Defense Advanced Research Projects Agency under Contracts N00014-92-J-1799 and N00014-91-J-1698, the Air Force under Contract F49620-92-J-0125, and the Army under Contract DAAL-03-86-K-0171.Supported by an ONR graduate fellowship, grants NSF 8912586 CCR and AFOSR 89-0271, and an NSF postdoctoral fellowship.     

Computability and complexity of ray tracing

The ray-tracing problem is, given an optical system and the position and direction of an initial light ray, to decide if the light ray reaches some given final position. For many years ray tracing has been used for designing and analyzing optical systems. Ray tracing is now used extensively in computer graphics to render scenes with complex curved objects under global illumination. We show that ray-tracing problems in some three-dimensional simple optical systems (purely geometrical optics) are undecidable. These systems may consist of either reflective objects that are represented by rational quadratic equations, or refractive objects that are represented by rational linear equations. Some problems in more restricted models are shown to be PSPACE-hard or sometimes in PSPACE. A preliminary version of this paper appeared as “The Computability and Complexity of Optical Beam Tracing” in theProceedings of the 31st Annual Symposium on Foundations of Computer Science, October 1990, Vol. I, pp. 106–114. The research of J. H. Reif and A. Yoshida was supported in part by Air Force Contract No. AFOSR-87-0386, DARPA/ARO Contract No. DAAL03-88-K-0195, DARPA/ISTO Contract No. N00014-88-K-0458, and NASA subcontract 550-63 of primecontract NASS-30428. J.D. Tygar's research was supported in part by the Defense Advanced Research Projects Agency under Contract No. F33615-87-C-1449 and by a National Science Foundation Presidential Young Investigator Award under Contract No. CCR-8858087.     

Equivalent factor matroids of graphs

The factor matroid of a graphG is the matric matroid of the vertex-edge incidence matrix ofG interpreted over the real numbers. This paper presents a constructive characterization of the graphs hat have the same factor matroid as a given 4-connected bipartite graph.Research partially supported by NSF Grant ESS-8307796 and Office of Naval Research Grant N00014-86-K-0689.     

Multi-sample cluster analysis using Akaike's Information Criterion

Summary Multi-sample cluster analysis, the problem of grouping samples, is studied from an information-theoretic viewpoint via Akaike's Information Criterion (AIC). This criterion combines the maximum value of the likelihood with the number of parameters used in achieving that value. The multi-sample cluster problem is defined, and AIC is developed for this problem. The form of AIC is derived in both the multivariate analysis of variance (MANOVA) model and in the multivariate model with varying mean vectors and variance-covariance matrices. Numerical examples are presented for AIC and another criterion calledw-square. The results demonstrate the utility of AIC in identifying the best clustering alternatives. This research was supported by Office of Naval Research Contract N00014-80-C-0408, Task NR042-443 and Army Research Office Contract DAAG 29-82-K-0155, at the University of Illinois at Chicago.     

A shortest path algorithm in robotics and its implementation on the FPS T-20 hypercube

A broad class of problems involving the optimal control of robot arms can be formulated as dynamic programming problems whose structure is particularly attractive for parallel processing. For certain simple cost functions the dynamic programming formulation reduces to determining the shortest path through a network. This algorithm has been implemented on a Floating Point Systems' T-20 hypercube computer. An analysis of the performance of the algorithm provides several important insights into the interplay between problem size and the number of processors in a parallel computer. The results also underscore the potential for parallel computers in real-time control applications.This work was supported in part by the Office of Naval Research, Contract N 00014-86-K-0693.