A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

Path problems in skew-symmetric graphs

We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for the skew-symmetric path problems and use them to design efficient algorithms for these problems. The algorithms presented are competitive with the fastest algorithms for the standard problems.This research was done while the first author was at Stanford University Computer Science Department, supported in part by ONR Office of Naval Research Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation.This research was done while the second author was visiting Stanford University Computer Science Department and supported by the above mentioned NSF and Powell Foundation Grants.     

OnG 2 continuous cubic spline interpolation

In this paper the interpolation byG ² continuous planar cubic Bézier spline curves is studied. The interpolation is based upon the underlying curve points and the end tangent directions only, and could be viewed as an extension of the cubic spline interpolation to the curve case. Two boundary, and two interior points are interpolated per each spline section. It is shown that under certain conditions the interpolation problem is asymptotically solvable, and for a smooth curvef the optimal approximation order is achieved. The practical experiments demonstrate the interpolation to be very satisfactory. Supported in prat by the Ministry of Science and Technology of Slovenjia, and in part by the NSF and SF of National Educational Committee of China.     

On the relation between quadratic termination and convergence properties of minimization algorithms

Summary It is shown that the theory developed in part I of this paper [22] can be applied to some well-known minimization algorithms with the quadratic termination property to prove theirn-step quadratic convergence. In particular, some conjugate gradient methods, the rank-1-methods of Pearson and McCormick (see Pearson [18]) and the large class of rank-2-methods described by Oren and Luenberger [16, 17] are investigated.This work was supported in part at Stanford University, Stanford, California, under Energy Research and Development Administration, Contract E(04-3) 326 PA No. 30, and National Science Foundation Grant DCR 71-01996 A04 and in part by the Deutsche Forschungsgemeinschaft     

A fast algorithm for scalar Nevanlinna-Pick interpolation

Summary In this paper, we derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Givenn distinct pointsz _i in the unit disk |z|<1 andn complex numbersw _i satisfying the Pick condition for 1in, the new Nevanlinna-Pick interpolation algorithm requires onlyO(n) arithmetic operations to evaluate the interpolatory rational function at a particular value ofz, in contrast to the classical algorithm which requiresO(n ²) arithmetic operations to compute the so-called Fenyves array (which is inherent in the classical algorithm). The new algorithm bypasses the generation of the Fenyves array to speed up the computation, and also yields a parallel scheme requiring onlyO(logn) arithmetic operations on a concurrent-read, exclusive-write parallel random access machine withn processors. We must remark that the rational functionf(z) computed by the new algorithm is one degree higher than the function computed by the classical algorithm.Supported in part by the US Army Research Office Grant No. DAAL03-91-G-0106     

The number of edges of many faces in a line segment arrangement

We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m ^2/3 n ^2/3+n(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is (m ^2/3 n ^2/3+n(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m ^2/3 t ^1/3+n(t/n)+nmin{logm,logt/n}), almost matching the lower bound of (m ^2/3 t ^1/3+n(t/n)) demonstrated in this paper.Work on this paper by the first and fourth authors has been partially supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484. Work by the first author has also been supported by an AT&T Bell Laboratories Ph.D. scholarship at New York University and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center (NSF-STC88-09648). Work by the second author has been supported by NSF under Grants CCR-87-14565 and CCR-89-21421. Work by the fourth author has additionally been supported by grants from the U.S.-Israeli Binational Science Foundation, the NCRD (the Israeli National Council for Research and Development) and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli National Academy of Sciences.     

A greedy algorithm for the optimal basis problem

The following problem is considered. Givenm+1 points {x _i }₀ ^m inR ⁿ which generate anm-dimensional linear manifold, construct for this manifold a maximally linearly independent basis that consists of vectors of the formx _i −x _j . This problem is present in, e.g., stable variants of the secant and interpolation methods, where it is required to approximate the Jacobian matrixf′ of a nonlinear mappingf by using values off computed atm+1 points. In this case, it is also desirable to have a combination of finite differences with maximal linear independence. As a natural measure of linear independence, we consider the hadamard condition number which is minimized to find an optimal combination ofm pairs {x _i ,x _j }. We show that the problem is not NP-hard, but can be reduced to the minimum spanning tree problem, which is solved by the greedy algorithm inO(m ²) time. The complexity of this reduction is equivalent to onem×n matrix-matrix multiplication, and according to the Coppersmith-Winograd estimate, is belowO(n ^2.376) form=n. Applications of the algorithm to interpolation methods are discussed. Part of the work was done while the author was visiting DIMACS, an NSF Science and Technology Center funded under contract STC-91-19999; DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and Bellcore, NJ, USA.     

Improved processor bounds for combinatorial problems in RNC

Our main result improves the known processor bound by a factor ofn ⁴ (maintaining the expected parallel running time,O(log³ n)) for the following important problem:find a perfect matching in a general or in a bipartite graph with n vertices. A solution to that problem is used in parallel algorithms for several combinatorial problems, in particular for the problems of finding i) a (perfect) matching of maximum weight, ii) a maximum cardinality matching, iii) a matching of maximum vertex weight, iv) a maximums-t flow in a digraph with unit edge capacities. Consequently the known algorithms for those problems are substantially improved.The results of this paper have been presented at the 26-th Annual IEEE Symp. FOCS, Portland, Oregon (October 1985).Partially supported by NSF Grants MCS 8303139 and DCR 8511713.Supporeted by NSF Grants MCS 8203232 and DCR 8507573.     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

Partitioning mathematical programs for parallel solution

This paper describes heuristics for partitioning a generalM × N matrix into arrowhead form. Such heuristics are useful for decomposing large, constrained, optimization problems into forms that are amenable to parallel processing. The heuristics presented can be easily implemented using publicly available graph partitioning algorithms. The application of such techniques for solving large linear programs is described. Extensive computational results on the effectiveness of our partitioning procedures and their usefulness for parallel optimization are presented. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.This material is based on research supported by National Science Foundation Grants CCR-9157632 and CDA-9024618, the Air Force Office of Scientific Research Grant F49620-94-1-0036 and the AT&T Foundation.     

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.     

On the rate of convergence in the entropic central limit theorem

We study the rate at which entropy is produced by linear combinations of independent random variables which satisfy a spectral gap condition.Mathematics Subjects Classification (2000):94A17; 60F05Supported in part by the EU Grant HPMT-CT-2000-00037, The Minkowski center for Geometry and the Israel Science Foundation.Supported in part by NSF Grant DMS-9796221.Supported in part by EPSRC Grant GR/R37210.Supported in part by the BSF, Clore Foundation and EU Grant HPMT-CT-2000-00037.     

Triangles in space or building (and analyzing) castles in the air

We show that the total combinatorial complexity of all non-convex cells in an arrangement ofn (possibly intersecting) triangles in 3-space isO(n ^7/3 logn) and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement and an alternative less efficient, but still subcubic algorithm for calculating all non-convex cells, analyze some special cases of the problem where improved bounds (and faster algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.Work on this paper by the first author has been supported by an AT&T Bell Laboratories PhD Scholarship. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, the IBM Corporation, and by a research grant from the NCRD — the Israeli National Council for Research and Development. A preliminary version of this paper has appeared inProc. 4th ACM Symp. on Computational Geometry, Urbana, Illinois, 1988.     

Quasi-planar graphs have a linear number of edges

A graph is calledquasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph withn vertices isO(n).Work on this paper by Pankaj K. Agarwal, Boris Aronov and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work on this paper by Pankaj K. Agarwal has also been supported by NSF Grant CCR-93-01259, by an Army Research Office MURI grant DAAH04-96-1-0013, by an NYI award, and by matching funds from Xerox Corporation. Work on this paper by Boris Aronov has also been supported by NSF Grant CCR-92-11541 and by a Sloan Research Fellowship. Work on this paper by János Pach, Richard Pollack, and Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-94-24398. Work by János Pach was also supported by Grant OTKA-4269 and by a CUNY Research Award. Work by Richard Pollack was also supported by NSF Grants CCR-94-02640 and DMS-94-00293. Work by Micha Sharir was also supported by NSF Grant CCR-93-11127, by a Max-Planck Research Award, and by grants from the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Part of the work on this paper was done during the participation of the first four authors in the Special Semester on Computational and Combinatorial Geometry organized by the Mathematical Research Institute of Tel Aviv University, Spring 1995.     

The analysis of a nested dissection algorithm

Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn ^1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n ^3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n ^3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn ^1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn ^1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688     

Performance Study and Analysis of Parallel Multilevel Preconditioners

The significant gap between peak and realized performance of parallel systems motivates the need for performance analysis. In order to predict the performance of a class of parallel multilevel ILU preconditioner (PBILUM), we build two performance prediction models for both the preconditioner construction phase and the solution phase. These models combine theoretical features of the preconditioners with estimates on computation cost, communications overhead, etc. Experimental simulations show that our model predication based on certain reasonable assumptions is close to the simulation results. The models may be used to predict the performance of this class of parallel preconditioners.*The research work of the authors was supported in part by the U.S. National Science Foundation under grants CCR-9988165, CCR-0092532, ACR-0202934, and ACR-234270, by the U.S. Department of Energy Office of Science under grant DE-FG02-02ER45961, by the Kentucky Science & Engineering Foundation under grant KSEF-02-264-RED-002.     

Mathematical foundations of nonsmooth embedding methods

This paper establishes a mathematical foundation for application of the well known classical embedding approach to a class of nonsmooth functions, using a recently developed analogue of the derivative in cases where the functions involved fail to be differentiable in the usual sense. As part of this development we show how to obtain an extension to this case of the classical Hadamard theorem giving conditions for a map of ⁿ to itself to be a homeomorphism.The research reported here was sponsored by the National Science Foundation under Grant CCR-8801489, and by the Air Force Systems Command, USAF, under Grants AFOSR-88-0090 and AFOSR-89-0058. The US Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

Shortest paths algorithms: Theory and experimental evaluation

We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theoretical results suggested by the experimental data. Our computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form an environment for testing the performance of shortest paths algorithms. The interaction between the experimental evaluation of algorithm behavior and the theoretical analysis of algorithm performance plays an important role in our research. This work was done while Boris V. Cherkassky was visiting Stanford University Computer Science Department and supported by the NSF and Powell Foundation grants mentioned below. Andrew V. Goldberg was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation. Corresponding author. This work was done while Tomasz Radzik was a Postdoctoral Fellow at SORIE, Cornell University, and supported by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550, and by the Packard Fellowship of éva Tardos.     

Fitting scattered data on spherelike surfaces using tensor products of trigonometric and polynomial splines

Summary A method is presented for fitting a function defined on a general smooth spherelike surfaceS, given measurements on the function at a set of scattered points lying onS. The approximating surface is constructed by mapping the surface onto a rectangle, and using a tensor-product of polynomial splines with periodic trigonometric splines. The use of trigonometric splines allows a convenient solution of the problem of assuring that the resulting surface is continuous and has continuous tangent planes at all points onS. Two alternative algorithms for computing the coefficients of the tensor fit are presented; one based on global least-squares, and the other on the use of local quasi-interpolators. The approximation order of the method is established, and the numerical performance of the two algorithms is compared.Supported in part by the National Science Foundation under Grant DMS-8902331 and by the Alexander von Humboldt Foundation     

Matching is as easy as matrix inversion

We present a new algorithm for finding a maximum matching in a general graph. The special feature of our algorithm is that its only computationally non-trivial step is the inversion of a single integer matrix. Since this step can be parallelized, we get a simple parallel (RNC ²) algorithm. At the heart of our algorithm lies a probabilistic lemma, the isolating lemma. We show other applications of this lemma to parallel computation and randomized reductions. Work done while visiting MSRI, Berkeley, in Fall 1985. Supported by NSF Grant BCR 85-03611 and an IBM Faculty Development Award.