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     

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     

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     

Decomposition of 2-D linear systems into 1-D systems in thefrequency domain

A method is presented for the decomposition of the frequency domain of 2-D linear systems into two equivalent 1-D systems having dynamics in different directions and connected by a feedback system. It is shown that under some assumptions the decomposition problem can be reduced to finding a realizable solution to the matrix polynomial equation X(z₁)P(z₂ )+Q(z₁)Y(z₂ )=D(z₁, z₂). A procedure for finding a realizable solution X(z₁ ), Y(z₂) to the equation is given     

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     

Algorithms and bounds for shortest paths and diameter in faultyhypercubes

In an n-dimensional hypercube Qn, with the fault set |F|<2_n-2, assuming S and D are not isolated, it is shown that there exists a path of length equal to at most their Hamming distance plus 4. An algorithm with complexity O (|F|logn) is given to find such a path. A bound for the diameter of the faulty hypercube Qn-F, when |F|<2_n-2, as n+2 is obtained. This improves the previously known bound of n+6 obtained by A.-H. Esfahanian (1989). Worst case scenarios are constructed to show that these bounds for shortest paths and diameter are tight. It is also shown that when |F|<2n-2, the diameter bound is reduced to n+1 if every node has at least 2 nonfaulty neighbors and reduced to n if every node has at least 3 nonfaulty neighbors     

On the number of digital straight line segments

A closed-form expression has been reported in the literature for L_N, the number of digital line segments of length N that correspond to lines of the form y=ax+β, O⩽α, β<1. The authors prove an asymptotic estimate for L_N that might prove useful for many applications, namely, L_N=N ³/π²+O(N² log N). An application to an image registration problem is given     

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     

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 γ     

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     

Bicoprime factorizations of the plant and their relation to right and left-coprime factorizations

In a general algebraic framework, starting with a bicoprime factorization P=N_prD^-1 N_pl, a right-coprime factorization N_p D_p^-1, a left-coprime factorization D^-1_pN_p, and the generalized Bezout identities associated with the pairs (N_p, D_p) and (D˜ _p, N˜_p) are obtained. The set of all H-stabilizing compensators for P in the unity-feedback configuration S(P, C) are expressed in terms of (N_pr, D, N _pt) and the elements of the Bezout identity. The state-space representation P=C(sI-A)^-1B is included as an example     

Damping ratio of polynomials with perturbed coefficients

Let a family of polynomials be P(s)=t ₀Sⁿ+t₁s ^n-1 . . .+t_n where O<α _j⩽t_j⩽β. Recently, C.B. Soh and C.S. Berger have shown that a necessary and sufficient condition for this equation to have a damping ratio of φ is that the 2ⁿ⁺¹ polynomials in it which have t_k=α_k or t_k=β_k have a damping ratio of φ. The authors derive a more powerful result requiring only eight polynomials to be Hurwitz for the equation to have a damping ratio of φ using Kharitonov's theorem for complex polynomials     

Explicit expressions for cascade factorization of generalnonminimum phase systems

Explicit expressions for two different cascade factorizations of any detectable left invertible nonminimum phase systems are given. The first one is a well known minimum phase/all-pass factorization by which all nonminimum phase zeros of a transfer function G(s) are collected into an all-pass factor V(s), and G (s) is written G_m(s)V$ where G_ms is considered as a minimum phase image of G(s). The second one is a new cascade factorization by which G(s) is rewritten as G_M( s)U(s) where U(s) collects all `awkward' zeros including all nonminimum phase zeros of G( s). Both G_m(s) and G_M(s) retain the given infinite zero structure of G(s). Further properties of G _m(s), G_M(s), and U (s) are discussed. These factorizations are useful in several applications including loop transfer recovery     

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     

Two new estimation algorithms for linear models with unknown butbounded measurement noise

Attention is given to linear systems described by y=A _&thetas;+e where the measurement error vector e is unknown but bounded. Two algorithms for sequential parameter identification are introduced. Their convergence properties are illustrated and compared with those of existing algorithms. A simulation study is carried out using simulated data to investigate the possible practical use of the algorithms. Their performances are compared with those of other offline algorithms as well as with those of the widely used least-squares estimates     

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     

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     

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     

Consensus with dual failure modes

The problem of achieving consensus in a distributed system is discussed. Systems are treated in which either or both of two types of faults may occur: dormant (essentially omission and timing faults) and arbitrary (exhibiting arbitrary behavior, commonly referred to as Byzantine). Previous results showed that are number of dormant faults may be tolerated when there are no arbitrary faults and that, at most, [n-1/3] arbitrary faults may be tolerated when there are no dormant faults (n is the number of processors). A continuum is established between the previous results: an algorithm exists iff n >f_max+2m_max and c >f_max+m_max (where c is the system connectivity), when faults are constrained so that there are at most f_max and at most m_max of these that are arbitrary. An algorithm is given and compared to known algorithms. A method is given to establish virtual links so that the communications graph appears completely connected     

A new realization theory

A realization theory that is based on the Kalman system theory and motivated by the Fuhrmann realization theory is presented. In the Fuhrmann realization theory, the realization state-space is defined by a natural polynomial module K_Q, which is related to a nonsingular polynomial matrix Q. The module K_Q is formed of all f where Q^-1f is strictly proper. In the realization theory proposed, the realization state-space is defined by a different module M_Q, which is formed of properly truncated, strictly proper formal power series of Q^-1f. The realization theory can be used to prove the dual-realization scheme induced by the Fuhrmann realization theory