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     

Decomposing the Laplacian

A correction is made and an elementary derivation is given of Clark's (ibid., vol.11, p.43-57, 1989) decomposition of the Laplacian Δ²f(x,y) into a second directional derivative in the gradient direction of f, and a product of gradient magnitude by curvature of the level curve through f(x,y)     

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     

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 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 VLSI constant geometry architecture for the fast Hartley andFourier transforms

An application-specific architecture for the parallel calculation of the decimation in time and radix 2 fast Hartley (FHT) and Fourier (FFT) transforms is presented. A real sequence with N=2ⁿ data items is considered as input. The system calculates the FHT and the FFT in n and n+1 stages. respectively. The modular and regular parallel architecture is based on a constant geometry algorithm using butterflies of four data items and the perfect unshuffle permutation. With this permutation, the mapping of the algorithm in VLSI technology is simplified and the communications among processors are minimized. Organization of the processor memory based on first-in, first-out (FIFO) queues facilitates a systolic data flow and permits the implementation in a direct way of the complex data movements and address sequences of the transforms. This is accomplished by means of simple multiplexing operations, using hardwired control. The total calculation time is (Nlog₂N)/4Q cycles for the FHT and N(1+log₂N)/4Q cycles for the FFT, where Q is the number of processors ( Q= 2^q, Q⩽N/4)     

A linear programming approach for the weighted graph matchingproblem

A linear programming (LP) approach is proposed for the weighted graph matching problem. A linear program is obtained by formulating the graph matching problem in L₁ norm and then transforming the resulting quadratic optimization problem to a linear one. The linear program is solved using a simplex-based algorithm. Then, approximate 0-1 integer solutions are obtained by applying the Hungarian method on the real solutions of the linear program. The complexity of the proposed algorithm is polynomial time, and it is O(n ⁶L) for matching graphs of size n. The developed algorithm is compared to two other algorithms. One is based on an eigendecomposition approach and the other on a symmetric polynomial transform. Experimental results showed that the LP approach is superior in matching graphs than both other methods     

A novel discrete relaxation architecture

The discrete relaxation algorithm (DRA) is a computational technique that enforces arc consistency (AC) in a constraint satisfaction problem (CSP). The original sequential AC-1 algorithm suffers from O(n³m³) time complexity, and even the optimal sequential AC-4 algorithm is O (n²m²) for an n-object and m-label DRA problem. Sample problem runs show that these algorithms are all too slow to meet the need for any useful, real-time CSP applications. A parallel DRA5 algorithm that reaches a lower bound of O(nm) (where the number of processors is polynomial in the problem size) is given. A fine-grained, massively parallel hardware computer architecture has been designed for the DRA5 algorithm. For practical problems, many orders of magnitude of efficiency improvement can be reached on such a hardware architecture     

A Schur method for balanced-truncation model reduction

It is shown that a not-necessarily-balanced state-space realization of the Moore reduced model can be computed directly without balancing via projections defined in terms of arbitrary bases for the left and right eigenspaces associated with the large eigenvalues of the product PQ of the reachability and controllability Grammians. Two specific methods for computing these bases are proposed, one based on the ordered Schur decomposition of PQ and the other based on the Cholesky factors of P and Q. The algorithms perform reliably even for nonminimal models     

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     

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

Simultaneous stabilization of single-input single-output discretetime systems

The problem of finding one compensator which simultaneously stabilizes a family of single-input-single-output (SISO) discrete-time plants is considered. The family of plants is described by the transfer functions {Pz, q): q∈Q}, which are generated via a z-transformation. A number of assumptions describing the set of allowable plants are then given. These assumptions include some regularity conditions on the plants and a minimum-phase requirement. The satisfaction of these assumptions guarantees the existence of a strictly proper stable compensator C(z) for simultaneous stabilization. An iterative computation method is provided for control design     

Further remarks on potentially global stabilizability

Given a control system with a nonlinear drift term, it is proved that a linear-like criterion for almost-global stabilizability can be stated, at least for control systems of the form x'=f( x)+Bu, where f is a polynomial but not necessarily homogeneous vector field. These stability criteria also allow for the control of the size of the region of attraction     

True 3D animation for displaying VLSI modeling data

The authors report on a flexible system that provides visual feedback to VLSI designers with a novel display method. The basic problem is to display simultaneously two or more functions f ₁, f₂, . . ., each of which depends on the two spatial variables x and y. The method is based on results from visual perception experiments, which indicated that the human visual system can view simultaneously two or more images that are separated in depth, even if they are combined (superimposed) over a common spatial domain. Two display modes have been implemented: a gray-level mode and a contour mode in which only the edges separating adjacent regions are displayed in an effort to make things easier for the user. This depth-separation technique allows the viewer to register spatially the x,y distribution of multiple variables in an animation sequence. The technique can be applied to many other situations in which a single-plane episode involves several variables     

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     

Robust stability and performance via fixed-order dynamiccompensation: the discrete-time case

A discrete-time feedback-control-design problem involving parametric uncertainty is considered. A quadratic bound suggested by recent work on discrete-time state-space H_∞ theory is utilized in conjunction with the guaranteed cost approach to guarantee robust stability with a robust performance bound. The principal result involves sufficient conditions for characterizing robust full- and reduced-order controllers with a worst case H ₁ performance bound     

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     

A note on the survival time of a dynamic system in an interval

The one-dimensional system dx(t=bu(t)dt+(ct ²)^1/2dW(t), where b (≠0) and c (⩾0) are real constants and W(t ) is a standard Brownian motion, is considered. The aim is to obtain the control u* that minimizes the expected value of a cost function with terminal cost equal to 0 or +∞ depending on whether the survival time in a given region is at least equal to or less than a fixed time