An approach for pole assignment in singular systems

Pole assignment in a singular system Edx/dt=Ax+Bu is discussed. It is shown that the problem of assigning the roots of det(sE-(A +BF)) by applying a proportional feedback u=Fx+r in a given singular system is equivalent to the problem of pole assignment of an appropriate regular system. An immediate application of this result is that procedures and computational algorithms that were originally developed for assigning eigenvalues in regular systems become useful tools for pole assignment in singular systems. The approach provides a useful tool for the combined problem of eliminating impulsive behavior and stabilizing a singular system     

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     

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     

Optimal dynamic scheduling in Jackson networks

A Jackson-like network that supports J types of interactive traffic (e.g., interactive messages) as well as I types of noninteractive traffic (e.g., file transfers, facsimile) is considered. The service-time distributions and the internal routing are homogeneous for all traffic types but can be node (queue) dependent. The problem is to find a scheduling control that minimizes a weighted sum of the average end-to-end delay for the interactive types and at the same time ensures that the average end-to-end delays for the interactive types will be below given design constraints. Conservation laws are first established and shown to yield the base of a polymatroid. The optimal control problem is then transformed into a linear program with the feasible region being the polymatroid base truncated by delay constraints. An optimal control is identified that partitions the traffic types into I+r (0⩽r⩽J) ordered groups and applies a strict priority rule among the groups. An algorithm is developed that does the grouping and solves the optimization problem. A decentralized implementation of the optimal control is also discussed     

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     

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

Functional and topological relations among banyan multistagenetworks of differing switch sizes

Relations among banyan multistage interconnection networks (MINs) of differing switch sizes are studied. If two N×N networks W and W' have switch sizes r and s, respectively, and if r>s, then W realizes a larger number of permutations than W'. Consequently, the two networks can never be equivalent. However, W may realize all the permutations of W', in which case W is said to functionally cover W' in the strict sense. More generally, W is said to functionally cover W' in the wide sense if the terminals of W can be relabeled so that W realizes all the permutations of W'. Functional covering is topologically characterized, and an optimal algorithm to decide strict functional covering is developed     

Linear periodic systems: eigenvalue assignment using discreteperiodic feedback

The eigenvalue assignment problem of a T-periodic linear system using discrete periodic state feedback gains is discussed. For controllable systems, an explicit formula for the feedback law is given that can be used for the arbitrary assignment of the eigenvalues of Φ_c1(T,0), the closed-loop state transition matrix from 0 to T. For the special case of periodic systems controllable over one period, this control law can be used to obtain any desired Φ_c1(T,0)     

Linear and nonlinear algorithms for identification in H∞ with error bounds

A linear algorithm and a nonlinear algorithm for the problem of system identification in H_∞ posed by Helmicki et al. (1990) for discrete-time systems are presented. The authors derive some error bounds for the linear algorithm which indicate that it is not robustly convergent. However, the worst-case identification error is shown to grow as log(n), where n is the model order. A robustly convergent nonlinear algorithm is derived, and bounds on the worst-case identification error (in the H_∞ norm) are obtained     

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     

A sufficient condition for simultaneous stabilization

The condition under which it is possible to find a single controller that stabilizes k single-input single-output linear time-invariant systems p_i(s) (i=1,. . .,k) is investigated. The concept of avoidance in the complex plane is introduced and used to derive a sufficient condition for k systems to be simultaneously stabilizable. A method for constructing a simultaneous stabilizing controller is also provided and is illustrated by an example     

New results in fuzzy clustering based on the concept ofindistinguishability relation

The issue of validity in clustering is considered and a definition of fuzzy r-cluster that extends E. Ruspini's definition (1982) is proposed. This definition is based on an indistinguishability relation based on the concept of t-norm. The fuzzy r-cluster's metrical properties are studied through the dual concept of t-conorm that leads to G-pseudometrics. From the concept of G-pseudometric, fuzzy r-clusters and fuzzy cluster coverages are defined. The authors propose a measure of cluster validity based on the concept of fuzzy coverage. The basic idea of the approach presented is that the smaller the difference between the degrees of membership and the degrees of indistinguishability, the better the clustering     

Observers for discrete singular systems

The author considers the design of observers for the discrete singular system Ex(k+1)=Ax(k)+Bu (k), y(k)=Cx(k), placing special emphasis on the problems of state reconstruction and minimal-time state reconstruction. It is shown that for a singular system, finite poles can be moved to infinity by state feedback and the state can be reconstructed by causal observers     

An improved covariance assignment theory for discrete systems

For discrete systems, the set of all state covariances X which can be assigned to the closed-loop system via a dynamic controller is characterized explicitly. For any assignable state covariance X , the set of all controllers that assign this X to the closed-loop system is parameterized with an arbitrary orthonormal matrix U of proper dimension     

The generation of discrete-time q-Markov covers via inversesolution of the Lyapunov equation

A new method for generating q-Markov covers for SISO discrete-time systems is proposed. It is based on computing first the impulse-response Gramian from the Markov parameters and covariances, and then solving the Lyapunov equation inversely to get the system matrices in controllability canonical form. The conditions for existence of q-Markov covers are also derived. The method is illustrated by a numerical example and is shown to be computationally simple     

Constant time algorithms for the transitive closure and somerelated graph problems on processor arrays with reconfigurable bussystems

The transitive closure problem in O(1) time is solved by a new method that is far different from the conventional solution method. On processor arrays with reconfigurable bus systems, two O (1) time algorithms are proposed for computing the transitive closure of an undirected graph. One is designed on a three-dimensional n×n×n processor array with a reconfigurable bus system, and the other is designed on a two-dimensional n²×n² processor array with a reconfigurable bus system, where n is the number of vertices in the graph. Using the O(1) time transitive closure algorithms, many other graph problems are solved in O(1) time. These problems include recognizing bipartite graphs and finding connected components, articulation points, biconnected components, bridges, and minimum spanning trees in undirected graphs     

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)     

Feedback control for linear time-invariant systems with state andcontrol bounds in the presence of disturbances

The problem of the stabilizing linear control synthesis in the presence of state and input bounds for systems with additive unknown disturbances is considered. The only information required about the disturbances is a finite convex polyhedral bound. Discrete- and continuous-time systems are considered. The property of positive D -invariance of a region is introduced, and it is proved that a solution of the problem is achieved by the selection of a polyhedral set S and the computation of a feedback matrix K such that S is positively D-invariant for the closed-loop system. It is shown that if polyhedral sets are considered, the solution involves simple linear programming algorithms. However, the procedure suggested requires a great amount of computational work offline if the state-space dimension is large, because the feedback matrix K is obtained as a solution of a large set of linear inequalities. All of the vertices of S are required     

Model reduction via balanced realizations: an extension andfrequency weighting techniques

Two model-reduction methods for discrete systems related to balanced realizations are described. The first is a technique which utilizes the least controllable and observable subsystem in deriving a balanced discrete reduced-order model. For this technique as L ^∞ norm bound on the reduction error is given. The second method is a frequency-weighting technique for discrete- and continuous-time systems where the input-normal or output-normal realizations are modified to include a simple frequency weighting. For this technique, L^∞ norm bounds on the weighted reduction errors are obtained