A differential transformation technique for the analysis of a class of non-linear time varying systems

The scope of the differential transformation technique, developed earlier for the study of non-linear, time invariant systems, has been extended to the domain of time-varying systems by modifications to the differential transformation laws proposed therein. Equivalence of a class of second-order, non-linear, non-autonomous systems with a linear autonomous model of second order is established through these transformation laws. The feasibility of application of this technique in obtaining the response of such non-linear time-varying systems is discussed.

An adaptive cascade compensator for a wide class of stable minimum or nonminimum phase plants through time moment estimation

Model Reference Adaptive Control (MRAC) of a wide repertoire of stable Linear Time Invariant (LTI) systems is addressed here. Even an upper bound on the order of the finite-dimensional system is unavailable. Further, the unknown plant is permitted to have both minimum phase and nonminimum phase zeros. Model following with reference to a completely specified reference model excited by a class of piecewise continuous bounded signals is the goal. The problem is approached by taking recourse to the time moments representation of an LTI system. The treatment here is confined to Single-Input Single-Output (SISO) systems. The adaptive controller is built upon an on-line scheme for time moment estimation of a system given no more than its input and output. As a first step, a cascade compensator is devised. The primary contribution lies in developing a unified framework to eventually address with more finesse the problem of adaptive control of a large family of plants allowed to be minimum or nonminimum phase. Thus, the scheme presented in this paper is confined to lay the basis for more refined compensators-cascade, feedback and both-initially for SISO systems and progressively for Multi-Input Multi-Output (MIMO) systems. Simulations are presented.

Linear time geometrical design rule checker based on quadtree representation of VLSI mask layouts

An efficient geometrical design rule checker is proposed, based on operations on quadtrees, which represent VLSI mask layouts. The time complexity of the design rule checker is O(N), where N is the number of polygons in the mask. A pseudoPascal description is provided of all the important algorithms for geometrical design rule verification.

Two-level k-means clustering algorithm for k-tau relationship establishment and linear-time classification

Partitional clustering algorithms, which partition the dataset into a pre-defined number of clusters, can be broadly classified into two types: algorithms which explicitly take the number of clusters as input and algorithms that take the expected size of a cluster as input. In this paper, we propose a variant of the k-means algorithm and prove that it is more efficient than standard k-means algorithms. An important contribution of this paper is the establishment of a relation between the number of clusters and the size of the clusters in a dataset through the analysis of our algorithm. We also demonstrate that the integration of this algorithm as a pre-processing step in classification algorithms reduces their running-time complexity.

Linear time algorithms for Abelian group isomorphism and related problems

We consider the problem of determining if two finite groups are isomorphic. The groups are assumed to be represented by their multiplication tables. We present an O(n) algorithm that determines if two Abelian groups with n elements each are isomorphic. This improves upon the previous upper bound of O(n log n) [Narayan Vikas, An O(n) algorithm for Abelian p-group isomorphism and an O(n log n) algorithm for Abelian group isomorphism, J. Comput. System Sci. 53 (1996) 1-9] known for this problem. We solve a more general problem of computing the orders of all the elements of any group (not necessarily Abelian) of size n in O(n) time. Our algorithm for isomorphism testing of Abelian groups follows from this result. We use the property that our order finding algorithm works for any group to design a simple O(n) algorithm for testing whether a group of size n, described by its multiplication table, is nilpotent. We also give an O(n) algorithm for determining if a group of size n, described by its multiplication table, is Abelian. (C) 2007 Elsevier Inc. All rights reserved.

Approximate linear time ML decoding on tail-biting trellises in two rounds

A linear time approximate maximum likelihood decoding algorithm on tail-biting trellises is presented, that requires exactly two rounds on the trellis. This is an adaptation of an algorithm proposed earlier with the advantage that it reduces the time complexity from O(m log m) to O(m) where m is the number of nodes in the tail-biting trellis. A necessary condition for the output of the algorithm to differ from the output of the ideal ML decoder is deduced and simulation results on an AWGN channel using tail-biting trellises for two rate 1/2 convolutional codes with memory 4 and 6 respectively, are reported.

Some recent results on the stability of linear time varying systems

Some theorems derived recently by the authors on the stability of multidimensional linear time varying systems are reported in this paper. To begin with, criteria based on Liapunov�s direct method are stated. These are followed by conditions on the asymptotic behaviour and boundedness of solutions. Finally,L 2 andL ? stabilities of these systems are discussed. In conclusion, mention is made of some of the problems in aerospace engineering to which these theorems have been applied.

Robust Observer Design with Application to Fault Detection

A new scheme for robust estimation of the partial state of linear time-invariant multivariable systems is presented, and it is shown how this may be used for the detection of sensor faults in such systems. We consider an observer to be robust if it generates a faithful estimate of the plant state in the face of modelling uncertainty or plant perturbations. Using the Stable Factorization approach we formulate the problem of optimal robust observer design by minimizing an appropriate norm on the estimation error. A logical candidate is the 2-norm, corresponding to an H�¿ optimization problem, for which solutions are readily available. In the special case of a stable plant, the optimal fault diagnosis scheme reduces to an internal model control architecture.

Class of linear time-varying discrete systems

A class of linear time-varying discrete systems is considered, and closed-form solutions are obtained in different cases. Some comments on stability are also included.

Conservation Properties of the Trapezoidal Rule in Linear Time Domain Analysis of Acoustics and Structures

The trapezoidal rule, which is a special case of the Newmark family of algorithms, is one of the most widely used methods for transient hyperbolic problems. In this work, we show that this rule conserves linear and angular momenta and energy in the case of undamped linear elastodynamics problems, and an ``energy-like measure'' in the case of undamped acoustic problems. These conservation properties, thus, provide a rational basis for using this algorithm. In linear elastodynamics problems, variants of the trapezoidal rule that incorporate ``high-frequency'' dissipation are often used, since the higher frequencies, which are not approximated properly by the standard displacement-based approach, often result in unphysical behavior. Instead of modifying the trapezoidal algorithm, we propose using a hybrid finite element framework for constructing the stiffness matrix. Hybrid finite elements, which are based on a two-field variational formulation involving displacement and stresses, are known to approximate the eigenvalues much more accurately than the standard displacement-based approach, thereby either bypassing or reducing the need for high-frequency dissipation. We show this by means of several examples, where we compare the numerical solutions obtained using the displacement-based and hybrid approaches against analytical solutions.

On the stability of a nonlinear system with periodic coefficients

A quasi-geometric stability criterion for feedback systems with a linear time invariant forward block and a periodically time varying nonlinear gain in the feedback loop is developed.

Relationship between the controllability grammian and closed-loop eigenvalues: the single input case

The controllability grammian is important in many control applications. Given a set of closed-loop eigenvalues the corresponding controllability grammian can be obtained by computing the controller which assigns the eigenvalues and then by solving the Lyapunov equation that defines the grammian. The relationship between the controllability grammian, resulting from state feedback, and the closed-loop eigenvalues of a single input linear time invariant (LTI) system is obtained. The proposed methodology does not require the computation of the controller that assigns the specified eigenvalues. The closed-loop system matrix is obtained from the knowledge of the open-loop system matrix, control influence matrix and the specified closed-loop eigenvalues. Knowing the closed-loop system matrix, the grammian is then obtained from the solution of the Lyapunov equation that defines it. Finally the proposed idea is extended to find the state covariance matrix for a specified set of closed-loop eigenvalues (without computing the controller), due to impulsive input in the disturbance channel and to solve the eigenvalue assignment problem for the single input case.

Matrix method for eigenstructure assignment - The multi-input case with application

The eigenvalue and eigenstructure assignment procedure has found application in a wide variety of control problems. In this paper a method for assigning eigenstructure to a linear time invariant multi-input system is proposed. The algorithm determines a matrix that has eigenvalues and eigenvectors at the desired locations. It is obtained from the knowledge of the open-loop system and the desired eigenstructure. Solution of the matrix equation, involving unknown controller gams, open-loop system matrices, and desired eigenvalues and eigenvectors, results hi the state feedback controller. The proposed algorithm requires the closed-loop eigenvalues to be different from those of the open-loop case. This apparent constraint can easily be overcome by a negligible shift in the values. Application of the procedure is illustrated through the offset control of a satellite supported, from an orbiting platform, by a flexible tether.