Parallel algorithms for analyzing activity networks

Parallel algorithms for analyzing activity networks are proposed which include feasibility test, topological ordering of the events, and computing the earliest and latest start times for all activities and hence identification of the critical activities of the activity network. The first two algorithms haveO(logn) time complexity and the remaining one achievesO(logd log logn) time bound, whered is the diameter of the digraph representing the activity network withn nodes. All these algorithms work on a CRCW PRAM and requireO(n ³) processors.     

Fast algorithms for determining (generalized) core groups in social networks

The structure of a large network (graph) can often be revealed by partitioning it into smaller and possibly more dense sub-networks that are easier to handle. One of such decompositions is based on ??k-cores??, proposed in 1983 by Seidman. Together with connectivity components, cores are one among few concepts that provide efficient decompositions of large graphs and networks. In this paper we propose an efficient algorithm for determining the cores decomposition of a given network with complexity ${\mathcal{O}(m)}$ , where m is the number of lines (edges or arcs). In the second part of the paper the classical concept of k-core is generalized in a way that uses a vertex property function instead of degree of a vertex. For local monotone vertex property functions the corresponding generalized cores can be determined in ${\mathcal{O}(m\cdot\max(\Delta,\log{n}))}$ time, where n is the number of vertices and ?? is the maximum degree. Finally the proposed algorithms are illustrated by the analysis of a collaboration network in the field of computational geometry.     

Parallel algorithms for global optimization

In this paper, we report results of implementations of algorithms designed (i) to solve the global optimization problem (GOP) and (ii) to run on a parallel network of transputers. There have always been two alternative approaches to the solution of the GOP, probabilistic and deterministic. Interval methods can be implemented on our network of transputers using Concurrent ADA, and a secondary objective of the tests reported was to investigate the relative computer times required by parallel interval algorithms compared to probabilistic methods.     

Parallel algorithms for permutation graphs

In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM. The weighted clique problem, the weighted independent set problem, the cliques cover problem, and the maximal layers problem are all solved with the same complexities. We can also show that the longest common subsequence problem belongs to the class NC.     

Parallel algorithms for elliptic equations

We describe a number of parallel algorithms for the numerical solution of elliptic equations and present some implementations on the Denelcor HEP Parallel Processor. The equations we study, typical of those encountered in a range of fluid pressure equations, are of the form where the coefficient tensor may represent a density, permeability or dielectric constant. We allow the possibility of discontinuities in , and of line and point sources in F. The equations are discretized using finite elements, with orders ranging from linear to bicubic. We use a tree of increasingly fine grids to achieve parallelism in the course of mesh refinement. We use conjugate gradient methods as well as multigrid methods to solve the resulting algebraic equations within each subgrid. We describe the implementation of these methods as parallel algorithms, and present results of actual performance on the HEP computer. In each case we demonstrate near optimal performance on the HEP, as measured by speedup over the corresponding serial algorithm. We would like to thank both Argonne National Laboratory and Ballistic Research Laboratory for allowing us access to their HEP computers. The operations staffs at both sites gave us unstintingly of their time, even when called on after hours. This research, on an, at times, quite temperamental machine, would never have been completed without their help. We would also like to thank Argonne National Laboratory for the excellent two-day HEP introduction provided us prior to the start of this research. Finally, we wish to thank E. Lusk and R. Overbeek for providing us with copies of their HEP macros.     

Methods for optimizing gas transmission networks

We describe two methods for the optimization of gas transmission networks. The first method reduces the number of variables in the optimization problem by eliminating the pipe-flow variables. The second method solves an optimization problem with the full set of variables to achieve better behaviour. These two methods are compared by a series of tests based on the British Gas NTS (National Transmission System). The results of these tests are reported. By formulating the network problem as an optimization problem we have been able to replace heuristics by well proven methods. The reliability of the algorithm using the reduced set of unknowns varied depending on the size of problem and the type of objective function being minimized. The algorithm using the full set of unknowns had no such difficulties, even though it needs to be used with some care. The algorithm is robust in the sense that when the objective function has the necessary continuities, there is a feasible point and the penalty terms ensure positive curvature, then a solution is found reliably. The algorithm based on the reduced set of unknowns is considerably faster than that using the full set, when it succeeds. The factor between the times taken ranges from 1.2 to 5 (average 3) for the smallest network. For the second case comparison is harder since the reduced set algorithm was given a head start in five cases. For the other five the factor is between 2.3 and 8.3. For the largest problem there is just one case in which the comparison is on equal terms, and here the factor is 18. It is clear that the reliability of the full set algorithm is bought at a considerable cost which rises as the problem gets bigger. The main conclusion is that the Sequential Augmented Lagrange Method yields a reliable algorithm for minimizing objective functions of practical interest based on gas networks such as the British Gas National Transmission System. It is not satisfactory to carry over to the case with machines techniques like those of the nodal and loop methods which work well on networks with no machines.     

Decomposition algorithms for generalized potential games

We analyze some new decomposition schemes for the solution of generalized Nash equilibrium problems. We prove convergence for a particular class of generalized potential games that includes some interesting engineering problems. We show that some versions of our algorithms can deal also with problems lacking any convexity and consider separately the case of two players for which stronger results can be obtained.     

New algorithms for generalized network flows

This paper, of which a preliminary version appeared in ISTCS'92, is concerned with generalized network flow problems. In a generalized network, each edgee = (u, v) has a positive flow multipliera _e associated with it. The interpretation is that if a flow ofx _e enters the edge at nodeu, then a flow ofa _e x _e exits the edge atv. The uncapacitated generalized transshipment problem (UGT) is defined on a generalized network where demands and supplies (real numbers) are associated with the vertices and costs (real numbers) are associated with the edges. The goal is to find a flow such that the excess or deficit at each vertex equals the desired value of the supply or demand, and the sum over the edges of the product of the cost and the flow is minimized. Adler and Cosares [Operations Research 39 (1991) 955–960] reduced the restricted uncapacitated generalized transshipment problem, where only demand nodes are present, to a system of linear inequalities with two variables per inequality. The algorithms presented by the authors in [SIAM Journal on Computing, to appear result in a faster algorithm for restricted UGT.Generalized circulation is defined on a generalized network with demands at the nodes and capacity constraints on the edges (i.e., upper bounds on the amount of flow). The goal is to find a flow such that the excesses at the nodes are proportional to the demands and maximized. We present a new algorithm that solves the capacitated generalized flow problem by iteratively solving instances of UGT. The algorithm can be used to find an optimal flow or an approximation thereof. When used to find a constant factor approximation, the algorithm is not only more efficient than previous algorithms but also strongly polynomial. It is believed to be the first strongly polynomial approximation algorithm for generalized circulation. The existence of such an approximation algorithm is interesting since it is not known whether the exact problem has a strongly polynomial algorithm.Corresponding author. Research was done while the first author was attending Stanford University and IBM Almaden Research Center. Research partially supported by ONR-N00014-91-C-0026 and by NSF PYI Grant CCR-8858097, matching funds from AT&T and DEC.Research partially supported by ONR-N00014-91-C-0026.     

Parallel algorithms for solving retrieval equations

Translated from Vychislitel'nye Kompleksy i Modelirovanie Slozhnykh Sistem, pp. 28–36, Moscow State University, 1989.     

Parallel comparison algorithms for approximation problems

Suppose we haven elements from a totally ordered domain, and we are allowed to performp parallel comparisons in each time unit (=round). In this paper we determine, up to a constant factor, the time complexity of several approximation problems in the common parallel comparison tree model of Valiant, for all admissible values ofn, p and , where is an accuracy parameter determining the quality of the required approximation. The problems considered include the approximate maximum problem, approximate sorting and approximate merging. Our results imply as special cases, all the known results about the time complexity for parallel sorting, parallel merging and parallel selection of the maximum (in the comparison model), up to a constant factor. We mention one very special but representative result concerning the approximate maximum problem; suppose we wish to find, among the givenn elements, one which belongs to the biggestn/2, where in each round we are allowed to askn binary comparisons. We show that log^* n+O(1) rounds are both necessary and sufficient in the best algorithm for this problem.Research supported in part by Allon Fellowship, by a Bat Sheva de Rothschild grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

Parallel geometric algorithms for multi-core computers

Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the goal of exploiting the additional computing power. The algorithms we describe are (a) 2-/3-dimensional spatial sorting of points, as is typically used for preprocessing before using incremental algorithms, (b) d-dimensional axis-aligned box intersection computation, and finally (c) 3D bulk insertion of points into Delaunay triangulations, which can be used for mesh generation algorithms, or simply for constructing 3D Delaunay triangulations. For the latter, we introduce as a foundational element the design of a container data structure that both provides concurrent addition and removal operations and is compact in memory. This makes it especially well-suited for storing large dynamic graphs such as Delaunay triangulations.We show experimental results for these algorithms, using our implementations based on the Computational Geometry Algorithms Library (CGAL). This work is a step towards what we hope will become a parallel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention.     

Parallel algorithms for nonlinear programming problems

This paper describes several parallel algorithms for solving nonlinear programming problems. Two approaches where parallelism can successfully be introduced have been explored: a quadratic approximation method based on penalty function and a dual method. These methods are improved by using two algorithms originally proposed for solving unconstrained problems: the parallel variable metric algorithm and the parallel Jacobson-Oksman algorithm. Even though general problems are dealt with, particular emphasis is placed on the potential of these parallel methods for separable programming problems. The numerical effectiveness of the algorithms is demonstrated on a set of test problems using a Cray-1S vector computer and serial computers (with respect to sequential versions of the same methods).These studies were sponsored in part by the CERT. The author would particularly like to thank Ph. Berger (LSI-ENSEEIHT), the researchers of the DERI (CERT) and of the Groupe Structures, Aerospatiale, for their assistance.     

Iterative algorithms for generalized monotone variational inequalities

We propose some new iterative methods for solving the generalized variational inequalities where the underlying operator T is monotone. These methods may be viewed as projection-type methods. Convergence of these methods requires that the operator T is only monotone. The methods and the proof of the convergence are very simple. The results proved in this paper also represent a significant improvement and refinement of the known results.     

Iterative algorithms for generalized mixed equilibrium problems

In this paper, we consider a generalized mixed equilibrium problem in real Hilbert space. Using the auxiliary principle, we define a class of resolvent mappings. Further, using fixed point and resolvent methods, we give some iterative algorithms for solving generalized mixed equilibrium problem. Furthermore, we prove that the sequences generated by iterative algorithms converge weakly to the solution of generalized mixed equilibrium problem. These results require monotonicity (θ-pseudo monotonicity) and continuity (Lipschitz continuity) for mappings.     

Parallel algorithms for Gröbner-basis construction

The problem of the Gröbner-basis construction is important both from the theoretical and applied points of view. As examples of applications of Gröbner bases, one can mention the consistency problem for systems of nonlinear algebraic equations and the determination of the number of solutions to a system of nonlinear algebraic equations. The Gröbner bases are actively used in the constructive theory of polynomial ideals and at the preliminary stage of numerical solution of systems of nonlinear algebraic equations. Unfortunately, many real examples cannot be processed due to the high computational complexity of known algorithms for computing the Gröbner bases. However, the efficiency of the standard basis construction can be significantly increased in practice. In this paper, we analyze the known algorithms for constructing the standard bases and consider some methods for increasing their efficiency. We describe a technique for estimating the efficiency of paralleling the algorithms and present some estimates.     

Parallel algorithms for solving large linear systems

The solution of linear systems continues to play an important role in scientific computing. The problems to be solved often are of very large size, so that solving them requires large computer resources. To solve these problems, at least supercomputers with large shared memory or massive parallel computer systems with distributed memory are needed.

This paper gives a survey of research on parallel implementation of various direct methods to solve dense linear systems. In particular are considered: Gaussian elimination, Gauss-Jordan elimination and a variant due to Huard (1979), and an algorithm due to Enright (1978), designed in relation to solving (stiff) ODEs, such that stepsize and other method parameters can easily be varied.

Some theoretical results are mentioned, including a new result on error analysis of Huard's algorithm. Moreover, practical considerations and results of experiments on supercomputers and on a distributed-memory computer system are presented.     

Parallel variable metric algorithms for unconstrained optimization

We classify Straeter's ideas for parallel unconstrained optimization and apply them to Huang's class of updating formulas. Straeter's rank-one updating formula appears to be the only parallel extension within Huang's class with the property of quadratic termination. We also develop a parallel extension of Broyden's (1965) rank-one updating formula and prove quadratic termination. Finally, we present numerical results, obtained by testing the algorithms on several standard example problems.     

A review of methods and algorithms for optimizing construction scheduling

Optimizing construction project scheduling has received a considerable amount of attention over the past 20 years. As a result, a plethora of methods and algorithms have been developed to address specific scenarios or problems. A review of the methods and algorithms that have been developed to examine the area of construction schedule optimization (CSO) is undertaken. The developed algorithms for solving the CSO problem can be classified into three methods: mathematical, heuristic and metaheuristic. The application of these methods to various scheduling problems is discussed and implications for future research are identified.     

A parallel algorithm for generalized networks

This paper presents an application of parallel computing techniques to the solution of an important class of planning problems known as generalized networks. Three parallel primal simplex variants for solving generalized network problems are presented. Data structures used in a sequential generalized network code are briefly discussed and their extension to a parallel implementation of one of the primal simplex variants is given. Computational testing of the sequential and parallel codes, both written in Fortran, was done on the CRYSTAL multicomputer at the University of Wisconsin, and the computational results are presented. Maximum efficiency occurred for multiperiod generalized network problems where a speedup approximately linear in the number of processors was achieved.This research was supported in part by NSF grants DCR-8503148 and CCR-8709952 and by AFOSR grant AFOSR-86-0194.