On the gap between the structural controllability of time-varyingand time-invariant systems

Structural controllability of time-invariant and time-varying systems when the input control sequences have a restricted length k is compared. The dimensions of controllable space coincide in the following three special cases: the input sequences have length k=2; the input sequences have k=n, where n is the size of the system (i.e., the ultimate controllability is the same in both cases); and for every length of input sequences provided that the system has a single input only. It is proved that there may appear a gap for every input length k such that 2< k⩽n/2. The case when n/2<k<n is left open     

Two-dimensional convolution on a pyramid computer

An algorithm for convolving a k×k window of weighting coefficients with an n×n image matrix on a pyramid computer of O(n²) processors in time O(logn+k²), excluding the time to load the image matrix, is presented. If k=Ω (√log n), which is typical in practice, the algorithm has a processor-time product O(n ² k²) which is optimal with respect to the usual sequential algorithm. A feature of the algorithm is that the mechanism for controlling the transmission and distribution of data in each processor is finite state, independent of the values of n and k. Thus, for convolving two {0, 1}-valued matrices using Boolean operations rather than the typical sum and product operations, the processors of the pyramid computer are finite-state     

Out-of-roundness problem revisited

The properties and computation of the minimum radial separation (MRS) standard for out-of-roundness are discussed. Another standard out-of-roundness measurement called the minimum area difference (MAD) center is introduced. Although the two centers have different characteristics, the approach to finding both centers shares many commonalities. An O(n log n+k) time algorithm which is used to compute the MRS center is presented. It also computes the MAD center of a simple polygon G, where n is the number of vertices of G, and k is the number of intersection points of the medial axis and the farthest-neighbor Voronoi diagram of G. The relationship between MRS and MAD is discussed     

Network communication in edge-colored graphs: gossiping

A mechanism for scheduling communications in a network in which individuals exchange information periodically according to a fixed schedule is presented. A proper k edge-coloring of the network is considered to be a schedule of allowed communications such that an edge of color i can be used only at times i modulo k. Within this communication scheduling mechanism, the information exchange problem known as gossiping is considered. It is proved that there is a proper k edge-coloring such that gossip can be completed in a path of n edges in a certain time for n⩾k⩾1. Gossip can not be completed in such a path any earlier under any proper k edge-coloring. In any tree of bounded degree Δ and diameter d, gossip can be completed under a proper Δ edge-coloring in time (Δ-1)d +1. In a k edge-colored cycle of n vertices, other time requirements of gossip are determined     

On time mapping of uniform dependence algorithms into lowerdimensional processor arrays

Most existing methods of mapping algorithms into processor arrays are restricted to the case where n-dimensional algorithms, or algorithms with n nested loops, are mapped into (n-1)-dimensional arrays. However, in practice, it is interesting to map n-dimensional algorithms into (k-1)-dimensional arrays where k<n. A computational conflict occurs if two or more computations of an algorithm are mapped into the same execution time. Based on the Hermite normal form of the mapping matrix, necessary and sufficient conditions are derived to identify mapping without computational conflicts. These conditions are used to find time mappings of n-dimensional algorithms into (k-1)-dimensional arrays, k<n , without computational conflicts. For some applications, the mapping is time-optimal     

The minimal dimension of stable faces required to guaranteestability of a matrix polytope

Considers the problem of determining whether each point in a polytope n×n matrices is stable. The approach is to check stability of certain faces of the polytope. For n⩾3, the authors show that stability of each point in every (2n-4)-dimensional face guarantees stability of the entire polytope. Furthermore, they prove that, for any k⩽n², there exists a k-dimensional polytope containing a strictly unstable point and such that all its subpolytopes of dimension min {k-1,2n-5} are stable     

Optimal resilient distributed algorithms for ring election

The problem of electing a leader in a dynamic ring in which processors are permitted to fail and recover during election is discussed. It is shown that &thetas;(n log n+k_r) messages, counting only messages sent by functional processors, are necessary and sufficient for dynamic ring election, where k_r is the number of processor recoveries experienced     

Fast image labeling using local operators on mesh-connectedcomputers

A new parallel algorithm is proposed for fat image labeling using local operators on image pixels. The algorithm can be implemented on an n×n mesh-connected computer such that, for any integer k in the range [1, log (2n)], the algorithm requires Θ(kn¹k/) bits of local memory per processor and takes Θ(kn) time. Bit-serial processors and communication links can be used without affecting the asymptotic time complexity of the algorithm. The time complexity of the algorithm has very small leading constant factors, which makes it superior to previous mesh computer labeling algorithms for most practical image sizes (e.g. up to 4096×4096 images). Furthermore, the algorithm is based on using stacks that can be realized using very fast shift registers within each processing element     

Fault-tolerant embedding of complete binary trees in hypercubes

The focus is on the following graph-theoretic question associated with the simulation of complete binary trees by faulty hypercubes: if a certain number of nodes or links are removed from an n-cube, will an (n-1)-tree still exists as a subgraph? While the general problem of determining whether a k-tree, k< n, still exists when an arbitrary number of nodes/links are removed from the n-cube is found to be NP-complete, an upper bound is found on how many nodes/links can be removed and an (n-1)-tree still be guaranteed to exist. In fact, as a corollary of this, it is found that if no more than n-3 nodes/links are removed from an (n-1)-subcube of the n-cube, an (n-1)-tree is also guaranteed to exist     

Balanced parallel sort on hypercube multiprocessors

A parallel sorting algorithm for sorting n elements evenly distributed over 2^d p nodes of a d-dimensional hypercube is presented. The average running time of the algorithm is O((n log n)/p+p log 2n). The algorithm maintains a perfect load balance in the nodes by determining the (kn/p)th elements (k1,. . ., (p-1)) of the final sorted list in advance. These p-1 keys are used to partition the sorted sublists in each node to redistribute data to the nodes to be merged in parallel. The nodes finish the sort with an equal number of elements (n/ p) regardless of the data distribution. A parallel selection algorithm for determining the balanced partition keys in O(p log2n) time is presented. The speed of the sorting algorithm is further enhanced by the distance-d communication capability of the iPSC/2 hypercube computer and a novel conflict-free routing algorithm. Experimental results on a 16-node hypercube computer show that the sorting algorithm is competitive with the previous algorithms and faster for skewed data distributions     

Optimal distributed t-resilient election in completenetworks

The problem of distributed leader election in an asynchronous complete network, in the presence of faults that occurred prior to the execution of the election algorithm, is discussed. Failures of this type are encountered, for example, during a recovery from a crash in the network. For a network with n processors, k of which start the algorithm that uses at most O(n log k +n+kt) messages is presented and shown to be optimal. An optimal algorithm for the case where the identities of the neighbors are known is also presented. It is noted that the order of the message complexity of a t-resilient algorithm is not always higher than that of a nonresilient one. The t-resilient algorithm is a systematic modification of an existing algorithm for a fault-free network     

Stabilization by reduced-order controllers

A recent result by A. Linnemann (Syst. Contr. Lett., vol.11, p.27-32, 1988) gives conditions under which a continuous-time single-loop plant of order n can be stabilized by a reduced-order controller. Specifically, if the Euclidean algorithm is applied to the numerator and denominator polynomials of the transfer function and one of the remainders is a kth-order Hurwitz polynomial, then a stabilizing controller of order n-k-1 exists. The author provides an alternative proof of this result     

Optimal parallel initialization algorithms for a class of priorityqueues

An adaptive parallel algorithm for inducing a priority queue structure on an n-element array is presented. The algorithm is extended to provide optimal parallel construction algorithms for three other heap-like structures useful in implementing double-ended priority queues, namely min-max heaps, deeps, and min-max-pair heaps. It is shown that an n-element array can be made into a heap, a deap, a min-max heap, or a min-max-pair heap in O(log n+(n /p)) time using no more than n/log n processors, in the exclusive-read-exclusive-write parallel random-access machine model     

The external Heapsort

Heapsort is an internal sorting method which sorts an array of n records in place in O(n log n) time. Heapsort is generally considered unsuitable for external random-access sorting. By replacing key comparisons with merge operations on pages, it is shown how to obtain an in-place external sort which requires O(m log m) page references, where m is the number of pages which the file occupies. The new sort method (called Hillsort) has several useful properties for advanced database management systems. Not only does Hillsort operate in place, i.e., no additional external storage space is required assuming that the page table can be kept in core memory, but accesses to adjacent pages in the heap require one seek only if the pages are physically contiguous. The authors define the Hillsort model of computation for external random-access sorting, develop the complete algorithm and then prove it correct. The model is next refined and a buffer management concept is introduced so as to reduce the number of merge operations and page references, and make the method competitive to a basic balanced two-way external merge. Performance characteristics are noted such as the worst-case upper bound, which can be carried over from Heapsort, and the average-case behavior, deduced from experimental findings. It is shown that the refined version of the algorithm which is on a par with the external merge sort     

The stability of a family of polynomials can be deduced from afinite number 0(k3) of frequency checks

Let φ(s,a)=φ₀(s,a)+ a₁φ₁(s)+a₂ φ₂(s)+ . . .+a_kφ _k(s)=φ₀(s)-q(s, a) be a family of real polynomials in s, with coefficients that depend linearly on parameters a_i which are confined in a k-dimensional hypercube Ω_a . Let φ₀(s) be stable of degree n and the φ_i(s) polynomials (i⩾1) of degree less than n. A Nyquist argument shows that the family φ(s) is stable if and only if the complex number φ₀(jω) lies outside the set of complex points -q(jω,Ω_a) for every real ω. In a previous paper (Automat. Contr. Conf., Atlanta, GA, 1988) the authors have shown that -q(jω,Ω_a ), the so-called `-q locus', is a 2k convex parpolygon. The regularity of this figure simplifies the stability test. In the present paper they again exploit this shape and show that to test for stability only a finite number of frequency checks need to be done; this number is polynomial in k, 0(k³), and these critical frequencies correspond to the real nonnegative roots of some polynomials     

Rotator graphs: an efficient topology for point-to-pointmultiprocessor networks

Rotator graphs, a set of directed permutation graphs, are proposed as an alternative to star and pancake graphs. Rotator graphs are defined in a way similar to the recently proposed Faber-Moore graphs. They have smaller diameter, n-1 in a graph with n factorial vertices, than either the star or pancake graphs or the k-ary n-cubes. A simple optimal routing algorithm is presented for rotator graphs. The n-rotator graphs are defined as a subset of all rotator graphs. The distribution of distances of vertices in the n-rotator graphs is presented, and the average distance between vertices is found. The n-rotator graphs are shown to be optimally fault tolerant and maximally one-step fault diagnosable. The n-rotator graphs are shown to be Hamiltonian, and an algorithm for finding a Hamiltonian circuit in the graphs is given     

Parallel binary search

Two arrays of numbers sorted in nondecreasing order are given: an array A of size n and an array B of size m, where n<m. It is required to determine, for every element of A, the smallest element of B (if one exists) that is larger than or equal to it. It is shown how to solve this problem on the EREW PRAM (exclusive-read exclusive-write parallel random-access machine) in O(logm logn/log log m) time using n processors. The solution is then extended to the case in which fewer than n processors are available. This yields an EREW PRAM algorithm for the problem whose cost is O(n log m, which is O(m)) for n⩽m/log m. It is shown how the solution obtained leads to an improved parallel merging algorithm     

Linear and nonlinear algorithms for identification in H∞ with error bounds

A linear algorithm and a nonlinear algorithm for the problem of system identification in H_∞ posed by Helmicki et al. (1990) for discrete-time systems are presented. The authors derive some error bounds for the linear algorithm which indicate that it is not robustly convergent. However, the worst-case identification error is shown to grow as log(n), where n is the model order. A robustly convergent nonlinear algorithm is derived, and bounds on the worst-case identification error (in the H_∞ norm) are obtained     

Constant time algorithms for the transitive closure and somerelated graph problems on processor arrays with reconfigurable bussystems

The transitive closure problem in O(1) time is solved by a new method that is far different from the conventional solution method. On processor arrays with reconfigurable bus systems, two O (1) time algorithms are proposed for computing the transitive closure of an undirected graph. One is designed on a three-dimensional n×n×n processor array with a reconfigurable bus system, and the other is designed on a two-dimensional n²×n² processor array with a reconfigurable bus system, where n is the number of vertices in the graph. Using the O(1) time transitive closure algorithms, many other graph problems are solved in O(1) time. These problems include recognizing bipartite graphs and finding connected components, articulation points, biconnected components, bridges, and minimum spanning trees in undirected graphs     

A linear algorithm for generating random numbers with a givendistribution

Let ξ be a random variable over a finite set with an arbitrary probability distribution. Improvements to a fast method of generating sample values for ξ in constant time are suggested. The proposed modification reduces the time required for initialization to O( n). For a simple genetic algorithm, this improvement changes an O(g n 1n n) algorithm into an O(g n) algorithm (where g is the number of generations, and n is the population size)