The semantics and complexity of parallel programs for vector computations. Part I: A case study using ADA

Recent research in parallel numerical computation has tended to focus on the algorithmic level. Less attention has been given to the programming level where algorithm is matched, to some extent, to computer architecture. This two-part paper presents a three-level approach to parallel programming which distinguishes between mathematical algorithm, program and computer architecture. In part I, we motivate our approach by a case study using the Ada language. In part II, a mathematical concept of parallel algorithm is introduced in terms of partial orders. This serves as the basis of a theory of parallel computation which makes possible a precise semantics and a precise criterion of complexity of parallel programs. It also suggests some notation for specifying parallel numerical algorithms. To illustrate the ideas presented in part II, we concentrate here on parallel numerical computations which have vector spaces as their central data type and which are intended to be executed on a multi-processor system. The Ada language, with its task constructs, allows one to program computer algorithms to be executed on multi-processor systems, rather than on vector (pipelined) architectures. To provide a concrete example of the general problem of programming parallel numerical algorithms for multi-processor computers, we do a case study of how Ada can be used to program the solution of a system of linear equations on such computers. The case study includes an analysis of complexity which addresses the cost of data movement and process control/synchronization as well as the usual arithmetic complexity.Dedicated to Peter Naur on the occasion of his 60th birthdayThis research was partially supported by NSF Grants DCR-8406290 & CCR-8712192.     

Computing parent nodes in threaded binary trees

We give three algorithms for computing the parent of a node in a threaded binary tree, and calculate the average case complexity of each. By comparing these to the unit cost of obtaining the parent of a node with an explicit parent-pointer field, it is possible to balance runtime and storage cost with respect to the task of finding parent nodes in binary trees. The results obtained show that, although the worst case complexity for ann-node tree is obviouslyO(n) for all three algorithms, the average case complexity for two input distributions is asymptotic (from below) to either 3 or 2.     

On the complexity of some arborescences finding problems on a multihop radio network

An arborescence of a multihop radio network is a directed spanning tree (with rootx) such that the edges are directed away from the root. Based upon an arborescence,x canbroadcast a message to other nodes according to the directed edges of the spanning tree. The minimum transmission power arborescence problem is to find an arborescence such that the message can be broadcasted to other nodes by using a minimal amount of transmission power. The minimum delay arborescence problem is to find an arborescence such that a message can be broadcasted to other nodes by using a minimal number of broadcast transmission. In this paper we show that both these problems areNP-complete. The reductions are from the maximum leaf spanning tree problem.Areverse arborescence is similar to an arborescence except that the edges are directed toward the root. Based upon a reverse arborescence, the root node cancollect information from other nodes. In this paper we also show that the reverse minimum transmission power arborescence problem can be solved with the same computational complexity as that of finding a minimum cost spanning tree, and the reverse minimum delay arborescence problem can be solved with the same computational complexity as that of finding a spanning tree.     

A divide-and-conquer algorithm for constructing relative neighborhood graph

AnO(n logn) divide-and-conquer algorithm for finding the relative neighborhood graph RNG(V) of a set V ofn points in Euclidean space is presented. If implemented in parallel, its time complexity isO(n) and it requiresO(logn) processors.     

Finding minimal nested polygons

An algorithm for finding a polygon with minimum number of edges nested in two simplen-sided polygons is presented. The algorithm solves the problem in at mostO(n logn) time, and improves the time complexity of two previousO(n ²) algorithms.The work was supported by NSERC grant OPG0041629.     

A linear time algorithm for the maximum matching problem on cographs

In this paper, we develop a sequential algorithm for the maximum matching problem on cographs. The input is a parse tree of some cograph. The time complexity of our algorithm is linear.Supported by National Science Council of Taiwan, R.O.C. under Grant NSC81-0415-E-005-03.     

A select and insert sorting algorithm

A general sorting algorithm, having the well knownO(n ²) algorithmsStraight Insertion Sort andSelection Sort as special cases, is described. This algorithm is analyzed in the case that certain choices in the algorithm are done randomly, and this yields an algorithm that has an average complexity ofO(n ^1.5) and a worst case complexity ofO(n ²). However, making random choices (by some random number generator) is time consuming, and a simple quasi-random scheme is therefore implemented. Test runs indicate that also this version has average complexity ofO(n ^1.5), and it even seems to perform better than the version using real random choices (even if we disregard the time used for the random choices). This version also needs very little administrative overhead, and it therefore compares favourably to many other sorting algorithms for small and medium sized arrays.     

The effect of table expansion on the program complexity of perfect hash functions

It has been shown by various researchers that designing a perfect hashing function for a fixed set ofn elements requires (n) bits in the worst case. A possible relaxation of this scheme is to partition the set into pages, and design a hash function which maps keys to page addresses, requiring subsequent binary search of the page. We have shown elsewhere that (nk/2 ^k+1)(1 +o(1)) bits are necessary and sufficient to describe such a hash function where the pages are of size 2 ^k . In this paper we examine the additional scheme of expanding the address space of the table, which does substantially improve the hash function complexity of perfect hashing, and show that in contrast, it does not reduce the hash function complexity of the paging scheme.Research supported by NSF Grant CCR-9017125 and by a grant from Texas Instruments.     

Quotient tree partitioning of undirected graphs

The partitioning of the vertices of an undirected graph, in a way that makes its quotient graph a tree, mirrors a way of permuting a square symmetric matrix to allow its factoring with little fill-in. We analyze the complexity of finding the best partitioning and show that it is NP-complete. We also give a new and simpler implementation of an algorithm that finds a maximal quotient tree.     

On the Complexity of Computing Error Bounds

We consider the cost of estimating an error bound for the computed solution of a system of linear equations, i.e., estimating the norm of a matrix inverse. Under some technical assumptions we show that computing even a coarse error bound for the solution of a triangular system of equations costs at least as much as testing whether the product of two matrices is zero. The complexity of the latter problem is in turn conjectured to be the same as matrix multiplication, matrix inversion, etc. Since most error bounds in practical use have much lower complexity, this means they should sometimes exhibit large errors. In particular, it is shown that condition estimators that: (1) perform at least one operation on each matrix entry; and (2) are asymptotically faster than any zero tester, must sometimes over or underestimate the inverse norm by a factor of at least , where n is the dimension of the input matrix, k is the bitsize, and where either or grows faster than any polynomial in n . Our results hold for the RAM model with bit complexity, as well as computations over rational and algebraic numbers, but not real or complex numbers. Our results also extend to estimating error bounds or condition numbers for other linear algebra problems such as computing eigenvectors. September 10, 1999. Final version received: August 23, 2000.     

On finding a worst-case optimal Fourth Normal Form database decomposition

Although several Fourth Normal Form (4NF) decomposition algorithms have been published, the problem's computational complexity remains an open question. Part of the difficulty is that no one has established an upper bound on the size of a 4NF decomposition scheme for a given number of attributes. We prove such an upper bound and we present an algorithm which is worst-case optimal: it never produces a 4NF decomposition scheme that is larger than the upper bound.     

Minimal perfect hashing in polynomial time

We present a universally applicable algorithm for generating minimal perfect hashing functions. The method has (worst case) polynomial time complexity in units of bit operations. An adjunct algorithm for reducing parameter magnitudes in the generated hash functions is given. This probabilistic method makes hash function parameter magnitudes independent of argument (input key) magnitudes.     

Scanline algorithms on a grid

A number of important problems in computational geometry are solved efficiently on 2- or 3-dimensional grids by means of scanline techniques. In the time complexity of solutions to the maximal elements and closure problems, a factor logn is substituted by loglogn, wheren is the number of elements. Next, by using a data structure introduced in the paper, the interval trie, previous solutions to the rectangle intersection and connected component problems are improved upon. Finally, a fast intersection finding algorithm for arbitrarily oriented line segments is presented.     

Analysis and benchmarking of two parallel sorting algorithms: Hyperquicksort and quickmerge

We analyze the computational and communication complexity of four sorting algorithms as implemented on a hypercube multicomputer: two variants of hyperquicksort and two variants of quickmerge. Based upon this analysis, machine-specific parameters can be used to determine when each algorithm requires less communication time than the others. We present benchmark results of the four algorithms on a 64-processor NCube/7. The benchmarking provides experimental evidence that hyperquicksort divides the values to be sorted more evenly among the processors than quickmerge. Because it does a better job balancing work between processors, hyperquicksort proves to be uniformly superior to quickmerge.     

A new decidable Horn fragment of predicate calculus

We describe an extension of the class ∀∃ of Horn formulas in predicate calculus. We prove the decidability of this class. We describe complexity characteristics such that fixing them splits this extended class into polynomially decidable subclasses. Fixing the maximum arity of predicates splits our class into subclasses belonging to NP. Bibliography: 11 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 147–162.     

Amortized analysis of some disk scheduling algorithms: SSTF,SCAN, andN-StepSCAN

The amortized analysis is a useful tool for analyzing the time-complexity of performing a sequence of operations. The disk scheduling problem involves a sequence of requests in general. In this paper, the performances of representative disk scheduling algorithms,SSTF, SCAN, andN-StepSCAN, are analyzed in the amortized sense. A lower bound of the amortized complexity for the disk scheduling problem is also derived. According to our analysis,SCAN is not only better thanSSTF andN-StepSCAN, but also an optimal algorithm. Various authors have studied the disk scheduling problem based on some probability models and concluded that the most acceptable performance is obtained fromSCAN. Our result therefore supports their conclusion.This research was supported by the National Science Council, Taiwan R. O. C. under contract: NSC80-0408-E009-11.     

Assessment of approximate algorithms: The error measure's crucial role

Initially, the distinction between exact and approximate algorithms is accounted for. We then consider a broad class of decision problems including the so-called account location ork-plant location problem (kPLP), and show that the choice of an appropriate reference value is critical; even an apparent plausible choice may lead to disputable conclusions.A family of data instances forkPLP is presented for which the relative duality gap approaches one. Consequently, for this class of optimization problems, no error measure on the upper bound should permit a characterization of the strong linear programming relaxation as good.     

Analysis of recursive batched interpolation search

For an ordered file of records with uniformly distributed key values, we examine an existing batched searching algorithm based on recursive use of interpolation searches. The algorithm, called Recursive Batched Interpolation Search (RBIS) in this paper, uses a divide-and-conquer technique for batched searching. The expected-case complexity of the algorithm is shown to beO(m loglog (2n/m) +m), wheren is the size of the file andm is the size of the query batch. Simulations are performed to demonstrate the savings of batched searching using RBIS. Also, simulations are performed to compare alternative batched searching algorithms which are based on either interpolation search or binary search. When the file's key values are uniformly distributed, the simulation results confirm that interpolation-search based algorithms are superior to binary-search based algorithms. However, when the file's key values are not uniformly distributed, a straight-forward batched interpolation search deteriorates quickly as the batch size increases, but algorithm RBIS still outperforms binary-search based algorithms when the batch size passes a threshold value.     

Scheduling theory problems of type n¦1∥σci(t)

The class of problems n¦1∥σc_i(t) is considered for special sets of penalty functions c_i(t). Using the structural properties of the sets of functions c_i(t), one selects subclasses of problems which possess a polynomial complexity.     

Unifications,deunifications, and their complexity

The execution of a Prolog program can be viewed as a sequence of unifications and backtracks over unifications. We study the time requirement of executing a sequence of such operations (the unify-deunify problem). It is shown that the well-known set union problem is reducible to this problem, even in the case when no function symbols are allowed (the Datalog unify-deunify problem). As the set union problem requires nonlinear time on a large class of algorithms, the same holds for the unify-deunify problem. Thus the linearity of single unifications does not give a complete picture of the time complexity of Prolog primitives. We discuss the methods for executing sequences of Datalog unifications used in Prolog interpreters and show that some of them require even quadratic time in the worst case. Complementing these results, we show that if the number of variables occurring in one clause is bounded by a constant, then the Datalog unify-deunify problem can be solved in linear time.A preliminary version of this paper appeared in the Third International Conference on Logic Programming, London, July 1986. This work was supported by the Academy of Finland and by TEKES.