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     

The design of a precompensator for multivariable adaptive control-anetwork-theoretic approach

A network-theoretic approach to the design of a dynamic precompensator C(s) for a multiinput, multioutput plant T(s) is considered. The design is based on the relative degree of each element of T(s). Specifically, an efficient algorithm is presented for determining whether a given plant T(s) has a diagonal precompensator C( s) such that, for almost all cases, T(s)C (s) has a diagonal interactor. The algorithm also finds any optimal precompensator, in the sense that the total relative degree is minimal. The algorithm can be easily modified to work even when a T(s) represented by a nonsquare matrix is given     

Balanced realization of stable transfer function matrices

Simple formulas are presented to compute the internally balanced minimal realization and the singular decomposition of the Hankel operator of a given continuous-time p×m stable transfer function matrix E(s)/d(s). The proposed formulas involve the Schwarz numbers of d(s) and the singular eigenvalues-eigenmatrices of a suitable finite matrix. Similar results are also obtained for a given discrete-time transfer function matrix     

Minimal realization of transfer function matrices via oneorthogonal transformation

The minimal realization of a given arbitrary transfer function matrix G(s) is obtained by applying one orthogonal similarity transformation to the controllable realization of G( s). The similarity transformation is derived by computing the QR or the singular value decomposition of a matrix constructed from the coefficients of G(s). It is emphasized that the procedure has not been proved to be numerically stable. Moreover, the matrix to be decomposed is larger than the matrices factorized during the step-by-step procedures given     

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     

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     

Vibrational feedback control in the problem of acoustic stability

The problem of absolute stability in a vibrational feedback controller is introduced and discussed. It is shown that for any rational G(s)=n(s)/d(s ) with d(s) Hurwitz and deg d(s) -deg n(s)=1 there exists a linear dynamic periodic controller that ensures, in a certain sense, the infinite sector of absolute stability. This implies that an additional dynamical element, inserted in the feedback loop, may lead to improvements in the robustness of nonlinear systems     

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     

A frame approach to the H∞ superoptimal solution

A frame approach to the H_∞ superoptimal solution which offers computational improvements over existing algorithms is given. The approach is based on interpreting s numbers as the largest gains between appropriately defined spaces. Some useful bounds on Hankel singular values and s numbers are derived     

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     

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     

Strict aperiodic property of polynomials with perturbedcoefficients

Let a family of polynomials be P(s)=t ₀sⁿ+t₁s ⁿ±¹ + . . . + t_n where 0<a_j⩽t_j⩽b _j. V.L. Kharitonov (1978) derived a necessary and sufficient condition for the above equation to have only zeros in the open left-half plane. The present authors derive some similar results for the equation to be strictly aperiodic (distinct real roots)     

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)     

Computing the width of a set

For a set of points P in three-dimensional space, the width of P, W (P), is defined as the minimum distance between parallel planes of support of P. It is shown that W(P) can be computed in O(n log n +I) time and O(n) space, where I is the number of antipodal pairs of edges of the convex hull of P, and n is the number of vertices; in the worst case, I=O( n²). For a convex polyhedra the time complexity becomes O(n+I). If P is a set of points in the plane, the complexity can be reduced to O(nlog n). For simple polygons, linear time suffices     

The LQG optimal regulation problem for systems with perfectmeasurements: explicit solution, properties, and application topractical designs

The continuous-time stationary linear-quadratic-Gaussian (LQG) optimal regulation problem is considered where the measurements are free of white noise components. A simple direct solution in the s-domain is derived for the optimal controller for general linear, time-variant right-invertible or left-invertible systems. The explicit expressions that are found for the controller transference and for the regulator return-ratio matrix can be used to obtain a practical suboptimal design in the s-domain. These expressions are applied to derive simple conditions for the precise recovery of the return-ratio matrix of the LQG regulator     

Multifrequency Pade approximation via Jordan continued-fractionexpansion

The multifrequency Pade approximation of transfer functions is performed via the Jordan-type continued-fraction expansion. An efficient algorithm that requires no complex algebra is derived for expanding a transfer function into a Jordan continued fraction about arbitrary points s=±jω_j on the imaginary axis of the s-plane. Also derived is a forward inversion algorithm for inverting a multifrequency Jordan continued-fraction expansion into a rational form. The algorithms presented are amenable for obtaining a family of frequency-response matched models of different orders for a high-order transfer function via a single set of computations     

Comments on `Conditions for stable zeros of sampled systems' by M.Ishitobi

The commenter argues that the result of the above-titled work (see ibid., vol.37, no.10, p.1558-1561, Oct. 1992) is incorrect. It is pointed out that when sampling a continuous-time system G(s ) using zero-order hold, the zeros of the resulting discrete-time system H(z) become complicated functions of the sampling interval T. The system G(s) has unstable continuous-time zeros, s=0.1±i. The zeros of the corresponding sampled system start for small T from a double zero at z=1 as exp(T(0.1±i )), i.e., on the unstable side. For T>1.067 . . . the zeros become stable. The criterion function of the above-titled work, F(T)=G*(jω_s/2)= H(-1)T/2, is, however, positive for all T, indicating only stable zeros. The zero-locus crosses the unit circle at complex values     

Robust stabilizability for linear systems with both parametervariation and unstructured uncertainty

The authors consider the problem of finding a single compensator which stabilizes a plant having both parameter variation and high-frequency unstructured uncertainty. An uncertain system model is proposed to characterize plants containing those two different uncertainties. Closed-loop stability criteria are then proposed for the model. Robust stabilizability for single-input single-output (SISO) systems is studied. A number of assumptions describing the set of admissable SISO plants are imposed. The satisfaction of these assumptions guarantees the existence of a proper stable compensator C(s) achieving robust stabilization. The algorithm used for controller design is recursive in nature and allows the designer to select one compensator coefficient at a time. Also, the minimum order of the desired stabilizer C(s) depends only on the largest relative degree of the nominal plants, which often leads to a lower-order compensator     

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     

Systolic computation of multivariable frequency response

An algorithm intended for software implementation on a programmable systolic/wavefront computer is presented for the computation of a complex-valued frequency-response matrix G. Typically, real-valued state-space model matrices are given and the calculation of G must be performed for a very large number of values of the scalar frequency parameter. The algorithm is an orthogonal version of an algorithm described previously by A.J. Laub (ibid., vol.26, no.4, p.407-8, 1981). The system matrix A is reduced initially to an upper Hessenberg form which is preserved as the frequency varies subsequently. A systolic QR factorization of a certain complex-valued matrix is then implemented for effecting the necessary linear system solution (inversion). The critical computational component is the back solve. This computational component's process dependency graph is embedded optimally in space and time through the use of a nonlinear spacetime transformation. The computational period of the algorithm is O(n) where n is the order of the matrix A