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 γ     

A distributed M-ary hypothesis testing problem withcorrelated observations

The distributed M-ary hypothesis testing problem of detecting one of M₀ events by an (N+1)-person hierarchical team, when the observations are correlated, is examined. In this problem, each of the N subordinate decision makers (DMs) transmits one of a prespecified set of messages based on their data to a primary decision maker who, in turn, combines the messages with his or her own data to make the final team decision. The necessary conditions for the optimal decision rules of the DMs are derived. A nonlinear Gauss-Seidel iterative algorithm is developed for the person-by-person optimal decision rules, and its monotonic convergence to the person-by-person optimum is established. A fast approximation algorithm is proposed for computing certain conditional probabilities arising in the person-by-person optimal decision rules. The algorithms are illustrated with several examples, and implications for distributed organizational designs are pointed out     

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     

Odd even shifts in SIMD hypercubes

A linear-time algorithm is developed to perform all odd (even) length circular shifts of data in an SIMD (single-instruction-stream, multiple-data-stream) hypercube. As an application, the algorithm is used to obtain an O(M²+log N) time and O(1) memory per processor algorithm to compute the two-dimensional convolution of an N×N image and an M×M template on an N² processor SIMD hypercube. This improves the previous best complexity of O(M² log M+log N)     

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     

Convolution on mesh connected multicomputers

An efficient parallel algorithm is presented for convolution on a mesh-connected computer with wraparound. The algorithm does not require a broadcast feature for data values, as assumed by previously proposed algorithms. As a result, the algorithm is applicable to both SIMD and MIMD meshes. For an N×N image and a M×M template, the previous algorithms take O (M²q) time on an N×N mesh-connected multicomputer (q is the number of bits in each entry of the convolution matrix). The algorithms have complexity O(M²r), where r=max {number of bits in an image entry, number of bits in a template entry}. In addition to not requiring a broadcast capability, these algorithms are faster for binary images     

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     

Simple algorithms and architectures for B-spline interpolation

It is proved that the Toeplitz binary value matrix inversion associated with mth-order B-spline interpolation can be implemented using only 2(m+1) additions. Pipelined architectures are developed for real-time B-spline interpolation based on simple running average filters. It is shown that an ideal interpolating function, which is approximated by a truncated sinc function with M half cycles, can be implemented using B-splines with M+2 multiplies. With insignificant loss of performance, the coefficients at the knots of the truncated sinc function can be approximated using coefficients which are powers of two. The resulting implementation requires only M+4m+6 additions. It is believed that the truncated sinc function approximated by zero-order B-spline functions actually achieves the best visual performance     

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, ∞)     

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     

Parallel binary search

Two arrays of numbers sorted in nondecreasing order are given: an array A of size n and an array B of size m, where n<m. It is required to determine, for every element of A, the smallest element of B (if one exists) that is larger than or equal to it. It is shown how to solve this problem on the EREW PRAM (exclusive-read exclusive-write parallel random-access machine) in O(logm logn/log log m) time using n processors. The solution is then extended to the case in which fewer than n processors are available. This yields an EREW PRAM algorithm for the problem whose cost is O(n log m, which is O(m)) for n⩽m/log m. It is shown how the solution obtained leads to an improved parallel merging algorithm     

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     

Damping margins of polynomials with perturbed coefficients

Considers the polynomial P(s)=t₀ Sⁿ+t₁ S^n-1 +···+t_n where 0<a _j⩽t_j⩽b_j. Recently, V.L. Kharitonov (1978) derived a necessary and sufficient condition for this polynomial to have only zeros in the open left-half plane. Two lemmas are derived to investigate the existence of theorems similar to the theorem of Kharitonov. Using these lemmas, the theorem of Kharitonov is generalized for P(s) to have only zeros within a sector in the complex plane. The aperiodic case is also considered     

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     

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     

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     

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     

An efficiently computable metric for comparing polygonal shapes

A method for comparing polygons that is a metric, invariant under translation, rotation, and change of scale, reasonably easy to compute, and intuitive is presented. The method is based on the L₂ distance between the turning functions of the two polygons. It works for both convex and nonconvex polygons and runs in time O(mn log mn), where m is the number of vertices in one polygon and n is the number of vertices in the other. Some examples showing that the method produces answers that are intuitively reasonable are presented     

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     

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