A note on a classical bound for the moduli of all zeros of apolynomial

Considers the monic polynomial f(z):=z ⁿ+a_n-1z^n-1+. . .+a₀ in the complex variable z with complex coefficients. Under the assumption that the nonleading coefficients of f lie in the disk |z|⩽A the authors give an estimate for the smallest disk |z|⩽R containing all zeros of f. The estimate has a guaranteed precision of a few percent. They proceed similarly to obtain a zero-free disk |z |⩽r     

Performance evaluation of dynamic sharing of processors intwo-stage parallel processing systems

The performance of job scheduling is studied in a large parallel processing system where a job is modeled as a concatenation of two stages which must be processed in sequence. P_i is the number of processors required by stage P as the total number of processors in the system. A large parallel computing system is considered where Max(P₁, P₂)⩾P≫1 and Max(P₁ , P₂)≫Min(P₁, P₂). For such systems, exact expressions for the mean system delay are obtained for various job models and disciplines. The results show that the priority should be given to jobs working on the stage which requires fewer processors. The large parallel system (i.e. P≫1) condition is then relaxed to obtain the mean system time for two job models when the priority is given to the second stage. Moreover, a scale-up rule is introduced to obtain the approximated delay performance when the system provides more processors than the maximum number of processors required by both stages (i.e. P>Max(P₁, P₂)). An approximation model is given for jobs with more than two stages     

Matrix inequalities applicable to estimating solution sizes ofRiccati and Lyapunov equations

Simultaneous summation upper bounds for the eigenvalues of the matrix product XY are presented, where X, Y ϵ R^nxn, with Y symmetric and X arbitrary. These bounds are a generalization of tr (XY) bounds; the requirements on Y are relaxed, and the bound for tr (XY) is stronger than those shown in the literature     

On quantization errors in computer vision

The author considers the error resulting in the computation of multivariable functions h(X₁, X, . . ., X_n), where all the X_is are only available in the quantized form. In image processing and computer vision problems, the variables are typically a mixture of the spatial coordinates and the intensity levels of objects in an image. A method is introduced using a first-order Taylor series expansion together with a periodic extension of the resulting expression and its Fourier series representation so that the moments and the probability distribution function of the error can be computed in closed form. This method only requires that the joint probability density function of X_i s be known and makes no assumption on the behavior on the quantization errors of the variables. Examples are also given where these results are applied     

A geometric approach to the theory of 2-D systems

The authors develop a geometric approach to the theory of 2-D (two-dimensional) systems, defining in a suitable way the notion of (A_1.2, B_1.2)-invariant subspaces and of controlled invariant subspaces. Such subspaces are shown to have good computational and feedback properties, which make them useful in application. In particular, sufficient conditions and constructive procedures are obtained for the solutions of disturbance decoupling and model matching problems. Moreover, it is shown that certain structural properties of a 2-D system can be described by means of a set of indexes defined in geometric terms, and that such structural indexes can be used to reformulate the sufficient condition for model matching     

Simultaneous controller design for linear time-invariant systems

The use of generalized sampled-data hold functions (GSHF) in the problem of simultaneous controller design for linear time-invariant plants is discussed. This problem can be stated as follows: given plants P₁, P₂, . . ., P_N , find a controller C which achieves not only simultaneous stability, but also simultaneous optimal performance in the N given systems. By this, it is meant that C must optimize an overall cost function reflecting the closed-loop performance of each plant when it is regulated by C. The problem is solved in three aspects: simultaneous stabilization, simultaneous optimal quadratic performance, and simultaneous pole assignment in combination with simultaneous intersampling performance     

A formal analysis of the fault-detecting ability of testing methods

Several relationships between software testing criteria, each induced by a relation between the corresponding multisets of subdomains, are examined. The authors discuss whether for each relation R and each pair of criteria, C₁ and C₂ , R(C₁, C₂) guarantees that C₁ is better at detecting faults than C₂ according to various probabilistic measures of fault-detecting ability. It is shown that the fact that C ₁ subsumes C₂ does not guarantee that C₁ is better at detecting faults. Relations that strengthen the subsumption relation and that have more bearing on fault-detecting ability are introduced     

A simulation-based estimator for hidden Markov random fields

An estimator for estimating the parameters of a Markov random field X from inaccurate observations is introduced. The author considers first a Markov (Gibbs) random field X={X_i,j} on a lattice L={(i ,j): i=1,2,. . .,n; j=1,2,. . .,m}. The marginal distributions of (X_i,j, X_i+u,j+v) (u,v=-1,0,1) are first estimated from an image. Then, random fields X* are simulated with the probability of X*_i+u,j+v)=b nearly equal to the estimate of P{X_i,j=X _i+u,=b}. A simulation method similar to the Gibbs sampler is used. The parameters of the Markov random field model are estimated from the X*'s with the pseudolikelihood method     

Rational approximation of L1 optimalcontrollers for SISO systems

The L₁ optimal control problem with rational controllers for continuous-time systems is considered in which it is shown that the optimal L₁ performance index with rational controllers is equal to that of irrational controllers. A sequence of rational controllers that approximates the optimal index is constructed. Convergence properties of such a sequence are studied. That the corresponding sequence of objective transfer functions is shown to converge in weak-* topology in BV(R₊) in the time domain and uniformly in a wider sense in the frequency domain     

Distributed detection with consulting sensors and communicationcost

The problem of distributed detection with consulting sensors in the presence of communication cost associated with any exchange of information (consultation) between sensors is considered. The system considered has two sensors, S1 and S2; S1 is the primary sensor responsible for the final decision u₀ , and S2 is a consulting sensor capable of relaying its decision u₂ to S1 when requested by S 1. The final decision u₀ is either based on the raw data available to S1 only, or, under certain request conditions, also takes into account the decision u₂ of sensor S2. Random and nonrandom request schemes are analyzed and numerical results are presented and compared for Gaussian and slow-fading Rayleigh channels. For each decision-making scheme, an associated optimization problem is formulated whose solution is shown to satisfy certain set design criteria that the authors consider essential for sensor fusion     

Parallel evaluation of attribute grammars

Examines the generation of parallel evaluators for attribute grammars, targeted to shared-memory MIMD computers. Evaluation-time overhead due to process scheduling and synchronization is reduced by detecting coarse-grain parallelism (as opposed to the naive one-process-per-node approach). As a means to more clearly expose inherent parallelism, it is shown how to automatically transform productions of the form X→Y X into list-productions of the form X→Y⁺. This transformation allows for many simplifications to be applied to the semantic rules, which can expose a significant degree of inherent parallelism, and thus further increase the evaluator's performance. Effectively, this constitutes an extension of the concept of attribute grammars to the level of abstract syntax     

An H∞ approach to feedback design withtwo objective functions

The problem of tightly bounding and shaping the frequency responses of two objective functions T_i(s)( i=1,2) associated with a closed-loop system is considered. It is proposed that an effective way of doing this is to minimize (or bound) the function max {∥T₁(s)∥ _∞, ∥T₂(s)∥_∞} subject to internal stability of the closed-loop system. The problem is formulated as an H^∞ control problem, and an iterative solution is given     

Sensitivity and robust stability of general input-output systems

The author considers a general model of an input-output system that is governed by nonlinear operator equations which relate the input, the state, and the output of the system. This model encompasses feedback systems as a special case. Assuming that the governing equations depend on a parameter A which is allowed to vary in a neighborhood of a nominal value A₀ in a linear space, the author studies the dependence of the system behavior on A. A system is considered insensitive if, for any fixed input, the output depends continuously on A. Similarly, the system is robust if it is stable for each A in a neighborhood of A₀. Stability is defined as an appropriate continuity of the input-output operator. The results give various sufficient conditions for insensitivity and robustness. Applications of the theory are discussed, including the estimation of the difference of operator inverses, and the insensitivity and robust stability of a Hilbert network, a feedback-feedforward system, a traditional feedback system, and a time-varying dynamical system described by a linear vector differential equation on (0, ∞)     

Solution to Morgan's problem

A necessary and sufficient condition is presented for the solution of the row-by-row decoupling problem (known as Morgan's problem) in the general case, that is, without any restrictive assumption added to the system to the feedback law u=Fx+Gy (G may be noninvertible). This is a structural condition in terms of invariant lists of integers which are easily computable from a given state realization of the system. These integers are the infinite zero orders (Morse's list I₄) and the essential orders of the system, which only depend on the input-output behavior, and Morse's list I₂ of the system, which depends on the choice of a particular state realization     

A qualitative bound in robustness of stabilization by statefeedback

It is proved that placing the poles of a linear time-invariant system arbitrarily far to the left of the imaginary axis is not possible if small perturbations in the model coefficients are taken into account. Given a nominal controllable system (A₀, B ₀) with one input and at least two states and an open ball around B₀ (no matter how small), there exists a real number γ and a perturbation B within that ball such that for any feedback matrix K placing the eigenvalues of A ₀+B₀K to the left of Res=γ, there is an eigenvalue of A₀+BK with real part not less than γ     

Linear systems with state and control constraints: the theory andapplication of maximal output admissible sets

The initial state of an unforced linear system is output admissible with respect to a constraint set Y if the resulting output function satisfies the pointwise-in-time condition y(t)∈Y, t⩾0. The set of all possible such initial conditions is the maximal output admissible set O_∞. The properties of O_∞ and its characterization are investigated. In the discrete-time case, it is generally possible to represent O_∞ or a close approximation of it, by a finite number of functional inequalities. Practical algorithms for generating the functions are described. In the continuous-time case simple representations of the maximal output admissible set are not available, however, it is shown that the discrete-time results may be used to obtain approximate representations     

Adaptive structuring of binary search trees using conditionalrotations

Consider a set A={A₁,A₂ ,. . ., A_n} of records, where each record is identified by a unique key. The records are accessed based on a set of access probabilities S=[s₁,s₂ ,. . ., s_N] and are to be arranged lexicographically using a binary search tree (BST). If S is known a priori, it is well known that an optimal BST may be constructed using A and S. The case when S is not known a priori is considered. A new restructuring heuristic is introduced that requires three extra integer memory locations per record. In this scheme, the restructuring is performed only if it decreases the weighted path length (WPL) of the overall resultant tree. An optimized version of the latter method, which requires only one extra integer field per record has, is presented. Initial simulation results comparing this algorithm with various other static and dynamic schemes indicates that this scheme asymptotically produces trees which are an order of magnitude closer to the optimal one than those produced by many of the other BST schemes reported in the literature     

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     

Bounds on eigenvalues of matrix products with an application to thealgebraic Riccati equation

Lower and upper summation bounds for the eigenvalues of the product XY are presented, under various restrictions on matrices X, Y∈R^n×n. An application to the algebraic Riccati equation yields a trace lower bound. It is observed that these bounds are tighter than those in the literature     

L1 analysis and design of sampled-data systems

The focus of this work is L₁-optimal control of sampled-data systems. A converging approximation procedure is derived to compute the L_∞-induced norm of closed-loop finite-dimensional linear time-invariant (LTI) sampled-data systems. An approximation method is developed to synthesize L₁-optimal sampled-data regulators. Finally, an example is provided that illustrates the L₁ analysis and design techniques presented