Modelling speedup (n) greater than n

A simple model of parallel computation which is capable of explaining speedups greater than n on n processors is presented. Necessary and sufficient conditions for these exceptional speedups are derived from the model. Several of the contradictory previous results relating to parallel speedup are resolved by using the model     

n-D polynomial matrix equations

Linear matrix equations in the ring of polynomials in n indeterminates (n-D) are studied. General- and minimum-degree solutions are discussed. Simple and constructive, necessary and sufficient solvability conditions are derived. An algorithm to solve the equations with general n-D polynomial matrices is presented. It is based on elementary reductions in a greater ring of polynomials in one indeterminate, having as coefficients polynomial fractions in the other n-1 indeterminates, which makes the use of Euclidean division possible     

Stability of x(t)=Ax(t)+Bx(t-τ)

A stability criterion for linear time-delay systems described by a differential difference equation of the form dx(t)=Ax(t)+Bx(t -τ) is proposed. The result obtained includes information on the size of the delay and therefore can be a delay-dependent stability condition. Its relation to existing delay-independent stability criteria is also discussed     

Solutions of the equation AV+BW=VF andtheir application to eigenstructure assignment in linear systems

Two new simple, complete, analytical, and restriction-free solutions with complete and explicit freedom of the matrix equation AV+BW=VF are proposed. Here [AB] is known and is controllable, and F is in the Jordan form with arbitrary given eigenvalues. Based on the proposed solutions of this matrix equation, a complete parametric approach for eigenstructure assignment in linear systems via state feedback is proposed, and two new algorithms are presented. The proposed solutions of the matrix equation and the eigenstructure assignment result are generalizations of some previous results and are simpler and more effective     

On computing complete histograms of images in log (n)steps using hypercubes

An algorithm for the computation of the histogram of limited-width (such as gray-level) values on a SIMD (single-instructions multiple-data) hypercube multiprocessor is proposed, which does not require the use of a general interconnection capability such as that on the connection machine. The computation of the complete histogram of n such values takes place in a series of log n steps, after which the histogram for value i can be found in the lowest-addressed processor whose address ends in i. The algorithm makes use of the association of suffixes of data values of increasing width with suffixes of processor addresses     

Generalized measures of fault tolerance in n-cube networks

It is shown that for a given p (1<p⩽n ), the n-cube network can tolerate up to p2^(n-p)-1 processor failures and remains connected provided that at most p neighbors of any nonfaulty processor are allowed to fail. This generalizes the result for p=n-1, obtained by A.-M Esfahanian (1989). It is also shown that the n-cube network with n⩾5 remains connected provided that at most two neighbors of any processor are allowed to fail     

On recursive, O(N) partitioning of a digitizedcurve into digital straight segments

A simple online algorithm for partitioning of a digital curve into digital straight-line segments of maximal length is given. The algorithm requires O(N) time and O(1) space and is therefore optimal. Efficient representations of the digital segments are obtained as byproducts. The algorithm also solves a number-theoretical problem concerning nonhomogeneous spectra of numbers     

On a weaker notion of controllability of a language K withrespect to a language L

A necessary and sufficient condition for a prefix-closed language K⊆Σ* to be controllable with respect to another prefix-closed language L⊆Σ* is that K⊆ L. A weaker notion of controllability where it is not required that K⊆L is considered here. If L is the prefix-closed language generated by a plant automaton G, then essentially there exists a supervisor Θ that is complete with respect to G such that L(Θ|G)=K ∩ L if and only if K is weakly controllable with respect to L. For an arbitrary modeling formalism it is shown that the inclusion problem is reducible to the problem of deciding the weaker notion of controllability. Therefore, removing the requirement that K ⊆ L from the original definition of controllability does not help the situation from a decidability viewpoint. This observation is then used to identify modeling formalisms that are not viable for supervisory control of the untimed behaviors of discrete-event dynamic systems     

An algorithm computing the general entry of the nthKronecker power of a matrix

The number of distinct entries among the m²ⁿ entries of the nth Kronecker power of an m×m matrix is derived. An algorithm to find the value of each entry of the Kronecker power is presented     

Some properties of the E matrix in two-view motionestimation

In the eight-point linear algorithm for determining 3D motion/structure from two perspective views using point correspondences, the E matrix plays a central role. The E matrix is defined as a skew-symmetrical matrix (containing the translation components) postmultiplied by a rotation matrix. The authors show that a necessary and sufficient condition for a 3×3 matrix to be so decomposable is that one of its singular values is zero and the other two are equal. Several other forms of this property are presented. Some applications are briefly described     

A treatment of jw-axis model-matching transformation zerosin the optimal H2 and H∞control designs

A model-matching transformation (MMT) zero is defined as a rank-deficiency condition which prevents an H² or H^∞ optimal control problem from being transformed into an equivalent model-matching problem. By imposing saturation constraints and accounting for additive instrument noise in the sensor and actuator signals, all MMT zeros can be eliminated     

A transfer function approach to the problems of discrete-timesystems: H∞-optimal linear control andfiltering

A solution is derived to the problems of H_∞ -optimal linear state regulation and filtering. The solution method for both problems is based on a transfer function approach which applies standard spectral factorization. Return difference relations are given which are extensions of the relations associated with the linear quadratic problem     

Constrained minimum-time path planning for robot manipulators viavirtual knots of the cubic B-spline functions

The B-spline functions are used to generate the constrained minimum-time path for a robot manipulator. The interpolated path via B-spline functions is determined via a unique set of virtual knots so that the robot path can pass every intermediate knot and satisfy the boundary conditions. The local control property of the B-spline functions can also be utilized to simplify the involved computational complexities. The flexible polyhedron search algorithm is used to generate the near minimum-time path with velocity, acceleration, and jerk constraints on every intermediate point. This approach can simplify the formulation and procedures for generating the near minimum-time cubic B-spline path. The use of this method to generate the constrained minimum-time joint trajectories for a PUMA 560 robot is discussed as an example     

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