Decoupling of square singular systems via proportional statefeedback

Necessary and sufficient conditions for the decoupling of a solvable square singular system Ex˙(t)=Ax(t)+Bu(t ) with output y(t)=Dx(t), through an admissible control law of the form u(t)=Kx(t)+Hr(t) where H is a square nonsingular matrix. It has been shown that for a given singular system that satisfies these conditions, a propagational state feedback exists for which the system's transfer function is a diagonal, nonsingular, and proper rational matrix. The proofs of the main results are constructive and provide a procedure for computing an appropriate proportional state feedback     

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     

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     

An algorithm for the multiinput eigenvalue assignment problem

A very simple and inexpensive algorithm is presented for pole placement in the multiinput case. The algorithm consists of orthogonal reduction to a Block-Hessenberg form and a simple linear recursion. It yields a matrix F such that A+BF has any specified set of eigenvalues whenever the system is controllable. It is extremely easy to program on a computer. The algorithm is not a robust pole-placement algorithm but appears to give comparable results in most well-conditioned cases at a fraction of the cost. It is a direct (noniterative) algorithm and no eigenvalues or singular values are computed. The algorithm does not need any complex arithmetic, even when complex conjugate eigenvalues need to be assigned     

Job scheduling in a partitionable mesh using a two-dimensionalbuddy system partitioning scheme

The job scheduling problem in a partitionable mesh-connected system in which jobs require square meshes and the system is a square mesh whose size is a power of two is discussed. A heuristic algorithm of time complexity O(n(log n+log p)), in which n is the number of jobs to be scheduled and p is the size of the system is presented. The algorithm adopts the largest-job-first scheduling policy and uses a two-dimensional buddy system as the system partitioning scheme. It is shown that, in the worst case, the algorithm produces a schedule four times longer than an optimal schedule, and, on the average, schedules generated by the algorithm are twice as long as optimal schedules     

Geometric structure and feedback in singular systems

The output-nulling (A, E, R(B))-invariant subspaces are defined for singular systems, rigorously justifying the name and demonstrating that special cases of these geometric objects are the familiar subspace of admissible conditions and the supremal (A, E, R(B ))-invariant subspace. A novel singular-system-structure algorithm is used to compute them by numerically efficient means. Their importance for describing the possible closed-loop geometric structure in terms of the open-loop geometric structure is shown. An approach to spectrum assignment in singular systems that is based on a generalized Lyapunov equation is introduced. The equation is used to compute feedback gains to place poles and assign various closed-loop invariant subspaces while guaranteeing closed-loop regularity     

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     

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     

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     

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     

Efficient algorithms for system diagnosis with both processor andcomparator faults

For the comparison-based self-diagnosis of multiprocessor systems, an extended model that considers both processor and comparator faults is presented. It is shown that in this model the system diagnosability is t⩽Zδ/2Z, where δ is the minimum vertex degree of the system graph. However, if the number of faulty comparators is assumed not to exceed the number of faulty processors, the diagnosability of the model reaches t⩽δ. An optimal O(|E|) algorithm, where E is the set of comparators, is given for identifying all faulty processors and comparators, provided that the total number of faulty components does not exceed the system diagnosability, and an O(|E|)² algorithm for the case t⩽δ is also presented. These efficient algorithms determine the faulty processors by calculating each processor's weight, which is mainly defined by the number of adjacent relative tests stating `agreement'. After sorting the processors according to their weights, the algorithms determine all faulty components by separating the sorted processor list     

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     

Decentralized stabilization and pole assignment for general propersystems

Considered is the problem of finding existence conditions and a controller synthesis procedure, using decentralized control, for assigning the poles of a linear time-invariant proper system described by a state-space model (C, A, B, D), where no assumption is made regarding the structure of D. This problem has direct application to the decentralized stabilization problem, decentralized robust servomechanism problem, etc., and is a nontrivial extension to the standard decentralized problem where it is assumed that the direct feedthrough terms either are absent or have a block-diagonal structure     

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     

Direct state-space solution to the discrete-timeH∞ one-block problem

A general state-space representation is used to allow a complete formulation of the H_∞ optimization problem without any invertibility condition on the system matrix, unlike existing solutions. A straightforward approach is used to solve the one-block H_∞ optimization problem. The parameterization of all solutions to the discrete-time H_∞ suboptimal one-block problem is first given in transfer function form in terms of a set of functions in H _∞ that satisfy a norm bound. The parameterization of all solutions is also given as a linear fractional representation     

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     

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     

A new method of image compression using irreducible covers ofmaximal rectangles

The binary-image-compression problem is analyzed using irreducible cover of maximal rectangles. A bound on the minimum-rectangular-cover problem for image compression is given under certain conditions that previously have not been analyzed. It is demonstrated that for a simply connected image, the irreducible cover proposed uses less than four times the number of the rectangles in a minimum cover. With n pixels in a square, the parallel algorithm for obtaining the irreducible cover uses (n/log n) concurrent-read-exclusive write (CREW) processors in O(log n) time