Toward time-varying balanced realization via Riccati equations

This paper presents a new approach for solving balanced realization problems with emphasis on the time-varying case. Instead of calculating the exact solutions for balancing at each time instant, we estimate with arbitrary accuracy the balancing solutions by means of Riccati equations associated with the balancing problems Under uniform boundedness conditions on the controllability and observability grammians and their inverses, the solutions of the Riccati equations exist and converge exponentially as their initial time goes to — to give what we term -balancing solutions. The parameter has the interpretation of the gain of a differential equation. It determines the accuracy of the balancing transformation tracking and the exponential rate of convergence. Their exponentially convergent behavior ensures numerical robustness.Work partially supported by Boeing, and DSTO Australia.Visiting from Akita University, 1-1 Tegatagakuen-cho, Akita, 010, Japan.     

Fractional balanced reduction: model reduction via fractionalrepresentation

A method for the model reduction of finite-dimensional, linear, time-invariant (FDLTI) plants is proposed which uses normalized fractional representations is proposed. The method, dubbed fractional balanced reduction, applies balance and truncate to a special representation of the graph operator of the plant. This operation yields the graph operator of a reduced order plant. The method has such properties as existence of an a priori error bound in the graph metric and preservation of sector containment. Coupling fractional representations with principal component analysis gives a model reduction method that is capable of producing, in a numerically stable way, a good reduced order model using the whole full order model. Sector properties are also preserved-these are useful for deciding stability when nonlinearities are in the loop     

Generalised gramian framework for model/controller order reduction of switched systems

In this article, a general method for model/controller order reduction of switched linear dynamical systems is presented. The proposed technique is based on the generalised gramian framework for model reduction. It is shown that different classical reduction methods can be developed into a generalised gramian framework. Balanced reduction within a specified frequency bound is developed within this framework. In order to avoid numerical instability and also to increase the numerical efficiency, generalised gramian‐based Petrov–Galerkin projection is constructed instead of the similarity transform approach for reduction. The framework is developed for switched controller reduction. To the best of our knowledge, there is no other reported result on switched controller reduction in the literature. The method preserves the stability under an arbitrary switching signal for both model and controller reduction. Furthermore, it is applicable to both continuous and discrete time systems for different classical gramian‐based reduction methods. The performance of the proposed method is illustrated by numerical examples.     

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     

Truncated balanced realization of a stable non-minimal state-space system

In this paper we present a numerically reliable algorithm to compute the balanced realization of a stable state-space system that may be arbitrarily close to being unobservable and/or uncontrollable. The resulting realization, which is known to be a good approximation of the original system, must be minimal and therefore may contain a reduced number of states. Depending on the choice of partitioning of the Hankel singular values, this algorithm can be used either as a form of minimal realization or of model reduction. This illustrates that in finite precision arithmetic these two procedures are closely related. In addition to real matrix multiplication, the algorithm only requires the solution of two Lyapunov equations and one singular value decomposition of an upper-triangular matrix.     

Model reduction via time-interval balanced stochastic truncation for linear time invariant systems

In this article, a new method for model reduction of linear dynamical systems is presented. The proposed technique is from the family of gramian-based relative error model reduction methods. The method uses time-interval gramians in the reduction procedure rather than ordinary gramians and in such a way it improves the accuracy of the approximation within the time interval which is applied. It is proven that the reduced order model is stable when the proposed method applies to a stable system. The method uses a recently proposed inner–outer factorisation algorithm which enhances the numerical accuracy and efficiency. In order to avoid numerical instability and also to further increase the numerical efficiency, projector matrices are constructed instead of the similarity transform approach for reduction. The method is illustrated by a numerical example and finally it is applied to a practical CD player example. The numerical results show that the method is more accurate than ordinary balanced stochastic truncation.     

A realization approach to stochastic model reduction

The problem of discrete-time stochastic model reduction (approximation) is considered. Using the canonical correlation analysis approach of Akaike (1975), a new order-reduction algorithm is developed. Furthermore, it is shown that the inverse of the reduced-order realization is asymptotically stable. Next, an explicit relationship between canonical variables and the linear least-squares estimate of the state vector is established. Using this, a more direct approach for order reduction is presented, and also a new design for reduced-order Kalman filters is developed. Finally, the uniqueness and symmetry properties for the new realization—the balanced stochastic realization—along with a simulation result, are presented.     

A new algorithm for the minimal balanced realization of a transfer function matrix

A new algorithm is proposed here to obtain a minimal balanced realization directly from the transfer function matrix (TFM). This method which employs the singular-value decomposition (SVD) of an infinite block-Hankel matrix requires neither an initial minimal realization nor the solution of a Lyapunov matrix equation. The formulation is solely in terms of the coefficients of the transfer function matrix.     

Identification and model reduction from impulse response data

Two new algorithms for identification and model reduction of stable linear continuous systems are proposed, based on the weighted impulse response gramians (Agathoklis and Sreeram 1988 b). In identification, the model parameters are obtained from the solution of a linear system of equations with coefficients obtained from the numerical evaluation of the weighted impulse response gramians. The reduction technique is based on retaining part of the original weighted impulse response gramians obtained as the solutions to the Lyapunov equation for the original system in controllability canonical form. This yields different stable models for different values of the weighting factor. The model corresponding to zero weighting factor matches the impulse response norm of the original system and its derivatives exactly. Finally, the method is illustrated by a numerical example and is compared with well-known balanced realization techniques.     

Control of systems with I/O delay via reduction to a one-block problem

In this paper, the standard (four-block) H/sup /spl infin// control problem for systems with a single delay in the feedback loop is studied. A simple procedure of the reduction of the problem to an equivalent one-block problem having particularly simple structure is proposed. The one-block problem is then solved by the J-spectral factorization approach, resulting in the so-called dead-time compensator (DTC) form of the controller. The advantages of the proposed procedure are its simplicity, intuitively clear derivation of the DTC form of the H/sup /spl infin// controller, and extensibility to the multiple delay case.     

Model reduction via a quasi-Kalman decomposition

A system theoretic model reduction algorithm is proposed which appears to be simple to work with. The algorithm is based on a quasi-Kalman decomposition.     

A geometric approach to nonlinear dissipative balanced reduction I: exogenous signals

This paper is divided into two parts and provides a unified geometric theory for nonlinear dissipative and Hankel balanced reduction with the help of a framework based on differential geometry, dissipativity theory, Lie-semigroups and sub manifold Hilbert theory. Part I presents a theory for the invariants of the behavior using classical Gauss’ curvature theory. Furthermore, known concepts of the theory of balanced reduction like the Hankel operator, Schmidt decomposition, etc., can be understood in a proper and general perspective.     

A geometric approach to nonlinear dissipative balanced reduction II: internal isometries

This Part II provides structural aspects of the internal signals and operators used in the unified geometric theory for nonlinear dissipative and Hankel balanced reduction using the differential-geometric framework based on dissipativity theory, Lie-semigroups and submanifold Hilbert theory. In particular, a novel characterization of the nonlinear Gramians is presented along with an alternative view of some concepts of the theory of nonlinear balanced reduction and the Hankel operator, namely eigenvalue problems and eigenfunction decomposition, etc.     

Convergence and convergence rate of the balanced realization truncations for infinite-dimensional discrete-time systems

In this paper, we study approximation via balanced realizations for a large class of infinite-dimensional discrete-time linear systems. We give properties of the truncated system and prove that the approximation is L₂-convergent. In the case of nuclear systems, we prove convergence in nuclear norm and give an estimation of the L_∞-convergence rate.     

L1 impulse response error bound for balanced truncation

This paper presents an upper bound in L₁ for the impulse response error between a system and its balanced truncation. It is an a priori bound and can be computed easily. Numerical examples are used to illustrate its applications and to compare with other available error bounds.     

Eigen-solving via reduction to DPR1 matrices

Highly effective polynomial root-finders have been recently designed based on eigen-solving for DPR1 (that is diagonal + rank-one) matrices. We extend these algorithms to eigen-solving for the general matrix by reducing the problem to the case of the DPR1 input via intermediate transition to a TPR1 (that is triangular + rank-one) matrix. Our transforms use substantially fewer arithmetic operations than the QR classical algorithms but employ non-unitary similarity transforms of a TPR1 matrix, whose representation tends to be numerically unstable. We, however, operate with TPR1 matrices implicitly, as with the inverses of Hessenberg matrices. In this way our transform of an input matrix into a similar DPR1 matrix partly avoids numerical stability problems and still substantially decreases arithmetic cost versus the QR algorithm.     

A subspace approach to balanced truncation for model reduction of nonlinear control systems

In this paper, we introduce a new method of model reduction for nonlinear control systems. Our approach is to construct an approximately balanced realization. The method requires only standard matrix computations, and we show that when it is applied to linear systems it results in the usual balanced truncation. For nonlinear systems, the method makes use of data from either simulation or experiment to identify the dynamics relevant to the input–output map of the system. An important feature of this approach is that the resulting reduced‐order model is nonlinear, and has inputs and outputs suitable for control. We perform an example reduction for a nonlinear mechanical system. Copyright © 2002 John Wiley & Sons, Ltd.     

On the selection of the reduced order via balanced state representations

It is shown that a conjecture concerning actual and internal dominance advanced in a previous publication is not in general true. Thus, use of the second-order modes only to select the order of a given SISO high-order system'sHreduced approximant may lead to unsatisfactory results. It is then proposed to use instead certain formulas giving the impulse response energy and the steady-state step response ofH.     

An efficient IP address lookup algorithm based on a small balanced tree using entry reduction

Due to a tremendous increase in internet traffic, backbone routers must have the capability to forward massive incoming packets at several gigabits per second. IP address lookup is one of the most challenging tasks for high-speed packet forwarding. Some high-end routers have been implemented with hardware parallelism using ternary content addressable memory (TCAM). However, TCAM is much more expensive in terms of circuit complexity as well as power consumption. Therefore, efficient algorithmic solutions are essentially required to be implemented using network processors as low cost solutions.Among the state-of-the-art algorithms for IP address lookup, a binary search based on a balanced tree is effective in providing a low-cost solution. In order to construct a balanced search tree, the prefixes with the nesting relationship should be converted into completely disjointed prefixes. A leaf-pushing technique is very useful to eliminate the nesting relationship among prefixes [V. Srinivasan, G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems 17 (1) (1999) 1-40]. However, it creates duplicate prefixes, thus expanding the search tree.This paper proposes an efficient IP address lookup algorithm based on a small balanced tree using entry reduction. The leaf-pushing technique is used for creating the completely disjointed entries. In the leaf-pushed prefixes, there are numerous pairs of adjacent prefixes with similarities in prefix strings and output ports. The number of entries can be significantly reduced by the use of a new entry reduction method which merges pairs with these similar prefixes. After sorting the reduced disjointed entries, a small balanced tree is constructed with a very small node size. Based on this small balanced tree, a native binary search can be effectively used in address lookup issue. In addition, we propose a new multi-way search algorithm to improve a binary search for IPv4 address lookup. As a result, the proposed algorithms offer excellent lookup performance along with reduced memory requirements. Besides, these provide good scalability for large amounts of routing data and for the address migration toward IPv6. Using both various IPv4 and IPv6 routing data, the performance evaluation results demonstrate that the proposed algorithms have better performance in terms of lookup speed, memory requirement and scalability for the growth of entries and IPv6, as compared with other algorithms based on a binary search.     

On the balanced truncation and coprime factors reduction of Markovian jump linear systems

The paper deals with the balanced truncation and coprime factors reduction of Markovian jump linear (MJL) systems, which can have mode-varying state, input, and output dimensions. We develop machinery for balancing mean square stable MJL system realizations using generalized Gramians and strict Lyapunov inequalities, and provide an improved a priori upper bound on the error induced in the balanced truncation process. We also generalize the coprime factors reduction method and, in doing so, extend the applicability of the balanced truncation technique to the class of mean square stabilizable and detectable MJL systems. We provide tools to establish mean square stabilizability and detectability of the considered MJL systems. In addition, a notion of right-coprime factorization of MJL systems and methods to construct such factorizations are given. The error measure in the coprime factors reduction approach, while still norm-based, does not directly capture the mismatch between the nominal system and the reduced-order model, as is the case in the balanced truncation approach where mean square stable models are considered. Instead, the error measure is given in terms of the distance between the coprime factors realizations, and thus has an interpretation in terms of robust feedback stability. The paper concludes with an illustrative example which demonstrates how to apply the coprime factors model reduction approach.