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     

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 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     

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     

The x-kernel: a platform for accessing internet resources

x-kernel is an experimental operating system for personal workstations that allows uniform access to resources throughout a nationwide internet: an interconnection of networks similar to the TCP/IP internet. This network is also called the National Research and Education Network (NREN). The x-kernel supports a library of protocols, and it accesses different resources with different protocol combinations. In addition, two user-level systems that give users an integrated and uniform interface to resources have been built on top of the x-kernel. These two systems-a file system and a command interpreter-hide differences among the underlying protocols     

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     

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     

The mean resequencing delay forM/HK/∞ systems

The relationship between the mean resequencing delay and variations in packet transmission times is studied. Assuming a Poisson stream of packets, a K-stage hyperexponential transmission time distribution and an infinite number of equal capacity links connecting the source and destination nodes, the authors derive an expression for the mean resequencing delay. This result provides an upper bound on the mean resequencing delay for nodes connected by finitely many links. They observe that for the two-stage and three-stage hyperexponential distribution, the mean resequencing delay varies almost perfectly linearly with the squared coefficient of variation. An asymptotic bound analysis can explain this behavior     

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     

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     

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     

H∞-optimal control with state-feedback

A H_∞-optimal control problem in which the measured outputs are the states of the plant is considered. The main result shows that the infimum of the norm of the closed-loop transfer function using linear static state-feedback equals the infimum of the norm of the closed-loop transfer function over all stabilizing dynamic (even, nonlinear time-varying) state-feedback controllers     

Controller reduction by H∞-balancedtruncation

H_∞-balanced truncation may be used to obtain reduced-order plants or controllers. The plant (possibly unstable) is compensated using a particular robustly stabilizing controller. The two Riccati equations involved are then used to define a set of closed-loop input-output invariants called the H_∞-characteristic values. That part of the plant or controller corresponding to small H_∞-characteristic values is discarded to give a reduced-order plant or controller. By exploiting an intimate connection with coprime factorization, a simple a priori test is derived for the ability of such a reduced-order controller to stabilize the full-order plant. The performance of the resulting closed-loop may also be bounded a priori, i.e. in terms of the prespecified level of robustness and the discarded H_∞-characteristic values     

Correction of the FI result in H∞ controland parameterization of H∞ state feedbackcontrollers

The authors correct the parameterization of the H_∞ controller of the full-information (FI) problem derived by J.C. Doyle et al. (1989). Then they parameterize the H_m0 state feedback controller and explain how dynamical free parameters implied in it are related to constant feedback gains different from the central solution F_∞     

Stabilizability of the systemẋ(t)=Fx(t)+Gu(t-h)

Stabilizability problem for the systemdot{x}(t)= Fx(t) + Gu(t - h)is considered. For appropriate discrete modelx_{k+1} = Ax_{k} + Bu_{k-1}the feedback controller which has the formu_{k} =Sigmamin{i=0}max{l}F_{i}x_{k-i}is proposed. It is proven that controllability of the pair (A,B) and cyclicity of theAmatrix imply stabilizability. Some extensions and applications are also mentioned.     

Two-degree-of-freedom H∞-optimization ofmultivariable feedback systems

A solution to the two-degree-of-freedom H_∞ -minimization problem that arises in the design of multivariable optimal continuous-time stochastic control systems is derived. A decoupling approach that enables a partially independent design of the prefilter and the feedback controller and yields a simple solution to the optimization problem is applied. This solution is obtained by transforming the optimization problem into two standard form (four-block) problems