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     

One more counterexample in n-D systems-unimodular versuselementary operations

By a simple counterexample, it is shown that there are unimodular matrices which cannot be written as products of elementary matrices in the ring of n-D polynomials. As a consequence, some methods for the solution of n-D matrix polynomial equations published recently, which are based on the elementary operations in the ring of n-D polynomials, do not work     

The graph topology on nth-order systems is quotientEuclidean

It is shown that on the set of m-input p-output minimal nth-order state-space systems the graph topology and the induced Euclidean quotient topology are identified. The author considers the set L_n^p×m of m -input p-output nth-order minimal state-space systems. The author presents three lemmas and a corollary from which a theorem is proved stating that the graph topology and the quotient Euclidean topology are identical on a quotient space L_n ^p×m/~. Since the graph topology is constructed to be weak, and the quotient Euclidean topology is intuitively strong, this result is unexpected     

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     

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     

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     

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     

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     

M-dimensional Cayley-Hamilton theorem

The theorem states that every block square matrix satisfies its own m-D (m-dimensional, m⩾1) matrix characteristic polynomial. The exact statement and a simple proof of this theorem are given. The theorem refers to a matrix A subdivided into m blocks, and hence having dimension at least m. The conclusion is that every square matrix A with dimension M satisfies several m-D characteristic matrix polynomials with degrees N₁ . . ., N _m, such that N₁+ . . . +N_m ⩽M     

Computational aspects of the bilinear transformation basedalgorithm for S-plane to Z-plane mapping

The author analyzes the computational complexity of an algorithm by F.D. Groutage et al. (ibid., vol.AC-32, no.7, p.635-7, July 1987) for performing the transformation of a continuous transfer function to a discrete equivalent by a bilinear transformation. Groutage et al. defend their method by noting that their technique is not limited to the bilinear transformation. Rather, it can be extended to any higher-order integration rule (Simpson, Runge-Kutta, etc.), or to any higher-order expansion of the ln function. In general, using the method, s can be any appropriate mapping function s=f (z)     

A smoothly parameterized family of stabilizable, observable linearsystems containing realizations of all transfer functions of McMillandegree not exceeding n

It is shown that there is a continuously parameterized family F of n-dimensional single-input single-output (SISO) stabilizable detectable linear system Σ(p) which contains at least one realization of each reduced, strictly proper transfer function of McMillan degree not exceeding n. The parameterization map p→Σ(p) is a polynomial function in 2n indeterminates from an open convex polyhedron in R²ⁿ to the linear space of all SISO n-dimensional linear systems     

L2-gain analysis of nonlinear systems andnonlinear state-feedback H∞ control

Previously obtained results on L2-gain analysis of smooth nonlinear systems are unified and extended using an approach based on Hamilton-Jacobi equations and inequalities, and their relation to invariant manifolds of an associated Hamiltonian vector field. On the basis of these results a nonlinear analog is obtained of the simplest part of a state-space approach to linear H_∞ control, namely the state feedback H_∞ optimal control problem. Furthermore, the relation with H_∞ control of the linearized system is dealt with     

Mixed H2/H∞ control:a convex optimization approach

The problem of finding an internally stabilizing controller that minimizes a mixed H₂/H_∞ performance measure subject to an inequality constraint on the H_∞ norm of another closed-loop transfer function is considered. This problem can be interpreted and motivated as a problem of optimal nominal performance subject to a robust stability constraint. Both the state-feedback and output-feedback problems are considered. It is shown that in the state-feedback case one can come arbitrarily close to the optimal (even over full information controllers) mixed H₂/H_∞ performance measure using constant gain state feedback. Moreover, the state-feedback problem can be converted into a convex optimization problem over a bounded subset of (n×n and n ×q, where n and q are, respectively, the state and input dimensions) real matrices. Using the central H_∞ estimator, it is shown that the output feedback problem can be reduced to a state-feedback problem. In this case, the dimension of the resulting controller does not exceed the dimension of the generalized plant     

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     

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     

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