Model Order Reduction: Theory, Research Aspects and Applications

In this first section we present a high level discussion on computational science, and the need for compact models of phenomena observed in nature and industry. We argue that much more complex problems can be addressed by making use of current computing technology and advanced algorithms, but that there is a need for model order reduction in order to cope with even more complex problems. We also go into somewhat more detail about the question as to what model order reduction is.

The development of Model Order Reduction techniques for various problems was triggered by the success of subspace projection methods for the solution of large linear systems and for the solution of matrix eigenvalue problems.

The most well-known approaches in the subspace projection arena are based on the construction of Krylov subspaces. These subspaces were proposed in 1931 by Krylov for the explicit construction of the characteristic polynomial of a matrix, so that the eigenvalues could be computed as the roots of that polynomial. This initial technique proved to be unpractical for matrices of order larger than, say, 6 or 7. It failed because of the poor quality of the standard basis vectors for the Krylov subspace. An orthogonal basis for this subspace appeared to be an essential factor, as well as the way in which this orthogonal basis is generated. These were breakthroughs initiated by Lanczos [4] and Arnoldi [1], both in the early 1950’s. In this chapter we will first discuss briefly some standard techniques for solving linear systems and for matrix eigenvalue problems.We will mention some relevant properties, but we refer the reader for background and more references to the standard text by Golub and van Loan [3].

We will then focus our attention on subspace techniques and highlight ideas that are relevant and can be carried over to Model Order Reduction approaches for other sorts of problems.

In recent years, order-reduction techniques based on Krylov subspaces have become the methods of choice for generating macromodels of large multi-port RCL circuits. Despite the success of these techniques and the extensive research efforts in this area, for general RCL circuits, the existing Krylov subspace-based reduction algorithms do not fully preserve all essential structures of the given large RCL circuit. In this paper, we describe the problem of structure-preserving model order reduction of general RCL circuits, and we discuss two state-of-the-art algorithms, PRIMA and SPRIM, for the solution of this problem. Numerical results are reported that illustrate the higher accuracy of SPRIM vs. PRIMA. We also mention some open problems.

Physical systems often have certain characteristics that are critical in determining the system behavior. Often these characteristics appear in the form of system matrices that are naturally blocked with each sub-block having its own physical relevance. for example, the system matrices from linearizing a second order dynamical system admit a natural 2-by-2 block partitioning. General purpose subspace projection techniques for model order reduction usually destroy any block structure and thus the reduced systems may not be of the same type as the original system. For similar reasons we would like to preserve the block structure and hence some of the important characteristics so that the reduced systems are much like the original system but only at a much smaller scale.

The remainder of this chapter is organized as follows. In Section 2, we discuss a unified Krylov subspace projection formulation for model order reduction with properties of structure-preserving and moment-matching, and present a generic algorithm for constructing structure-preserving projection matrices. The inherent structural properties of Krylov subspaces for certain block matrices are presented in Section 3. Section 4 examines structure-preserving model order reduction of RCL and RCS equations including the objective to develop synthesized RCL and RCS equations.

In this chapter we present a family of algorithms that can be considered intermediate between frequency domain projection methods and approximation of truncated balanced realizations. The methods discussed are computationally simple to implement, have good error properties, and possess simple error estimation and order control procedures. By tailoring the method to take into account a statistical representation of individual problem characteristics, more efficient, improved results have been obtained in several situations, meaning models of small order that retain acceptable accuracy, on problems for which many other methods struggle. Examples are shown to illustrate the algorithms in the contexts of frequency weighting, circuit simulation with parasitics networks having large numbers of input/output ports, and interconnect modeling in the presence of parameter change due to process variation.

In this paper we give an overview of model order reduction techniques for coupled systems. We consider linear time-invariant control systems that are coupled through input-output relations and discuss model reduction of such systems using moment matching approximation and balanced truncation. Structure-preserving approaches to model order reduction of coupled systems are also presented. Numerical examples are given.

In this chapter we present the principles of the space-mapping iteration techniques for the efficient solution of optimization problems. We also show how space-mapping optimization can be understood in the framework of defect correction.

We observe the difference between the solution of the optimization problem and the computed space-mapping solutions. We repair this discrepancy by exploiting the correspondence with defect correction iteration and we construct the manifold-mapping algorithm, which is as efficient as the space-mapping algorithm but converges to the true solution.

In the last section we show a simple example from practice, comparing space-mapping and manifold mapping and illustrating the efficiency of the technique.

A large scale dynamical system can have a large number of modes. Like a general square matrix can be approximated by its largest eigenvalues, i.e. by projecting it onto the space spanned by the eigenvalues corresponding to the largest eigenvalues, a dynamical system can be approximated by its dominant modes: a reduced order model, called the modal equivalent, can be obtained by projecting the state space on the subspace spanned by the dominant modes. This technique, modal approximation or modal model reduction, has been successfully applied to transfer functions of large-scale power systems, with applications such as stability analysis and controller design, see [16] and references therein.

The dominant modes, and the corresponding dominant poles of the system transfer function, are specific eigenvectors and eigenvalues of the state matrix. Because the systems are very large in practice, it is not feasible to compute all modes and to select the dominant ones. This chapter is concerned with the efficient computation of these dominant poles and modes specifically, and their use in reduced order modeling. In Sect. 2 the concept of dominant poles and modal approximation is explained in more detail. Dominant poles can be computed with specialized eigensolution methods, as is described in Sect. 3. Some generalizations of the presented algorithms are shown in Sect. 4. The theory is illustrated with numerical examples in Sect. 5 and 6 concludes.

Part of the contents of this chapter is based on [15, 16]. The pseudocode algorithms presented in this chapter are written using Matlab-like [21] notation.

Saddle point problems arise frequently in many applications in science and engineering, including constrained optimization, mixed finite element formulations of partial differential equations, circuit analysis, and so forth. Indeed the formulation of most problems with constraints gives rise to saddle point systems. This paper provides a concise overview of iterative approaches for the solution of such systems which are of particular importance in the context of large scale computation. In particular we describe some of the most useful preconditioning techniques for Krylov subspace solvers applied to saddle point problems, including block and constraint preconditioners.

Balancing for linear time varying systems and its application to model reduction via projection of dynamics (POD) are briefly reviewed. We argue that a generalization for balancing nonlinear systems may be expected to be based upon three sound principles: 1) Balancing should be defined with respect to a nominal flow; 2) Only Gramians defined over small time intervals should be used in order to preserve the accuracy of the linear perturbation model and; 3) Linearization should commute with balancing, in the sense that the linearization of a globally balanced model should correspond to the balanced linearized model in the original coordinates.

The first two principles lead to local balancing, which provides useful information about the dynamics of the system and the topology of the state space. It is shown that an integrability condition generically provides an obstruction towards a notion of a globally balanced realization in the strict sense. By relaxing the conditions of “strict balancing” in various ways useful system approximations may be obtained.

For linear control systems minimal realization theory and the related model reduction methods play a crucial role in understanding and handling the system. These methods are well established and have proved to be very successful, e.g., [Antoulas05, OA01, ZDG96]. In particular the method called balanced truncation gives a good reduced order model with respect to the input-output behavior, [Moore81, Glover84]. This method relies on the relation with the system Hankel operator, which plays a central role in minimal realization theory. Specifically, the Hankel operator supplies a set of similarity invariants, the so called Hankel singular values, which can be used to quantify the importance of each state in the corresponding input-output system [JS82]. The Hankel operator can also be factored into a composition of observability and controllability operators, from which Gramian matrices can be defined and the notion of balanced realization follows, first introduced in [Moore81] and further studied by many authors, e.g. [JS82, ZDG96]. This linear theory is rather complete and the relations between and interpretations in the state-space and input-output settings are fully understood.

This paper gives an overview of the series of research on balanced realization and the related model order reduction method based on nonlinear singular value analysis. Section 2 explains the taken point of view on singular value analysis for nonlinear operators. Section 3 briefly reviews the linear balancing method and balanced truncation in order to show the way of thinking for the nonlinear case. Section 4 treats the state-space balancing method stemming from [Scherpen93]. Then, in Section 5 we continue with balanced realizations based on the singular value analysis of the nonlinear Hankel operator. Furthermore, in Section 6 balanced truncation based on the method of Section 5 is presented. Finally, in Section 7 a numerical simulation illustrates how the proposed model order reduction method works for real-world systems.

In this chapter, we give an overview on methods to compute functions of a (usually square) matrix A with particular emphasis on the matrix exponential and the matrix sign function. We will distinguish between methods which indeed compute the entire matrix function, i.e. they compute a matrix, and those which compute the action of the matrix function on a vector. The latter task is particularly important in the case where we have to deal with a very large (and possibly sparse) matrix A or in situations, where A is not available as a matrix but just as a function which returns Ax for any input vector x. Computing the action of a matrix function on a vector is a typical model reduction problem, since the resulting techniques usually rely on approximations from small-dimensional subspaces.

We consider a particular class of structured systems that can be modelled as a set of input/output subsystems that interconnect to each other, in the sense that outputs of some subsystems are inputs of other subsystems. Sometimes, it is important to preserve this structure in the reduced order system. Instead of reducing the entire system, it makes sense to reduce each subsystem (or a few of them) by taking into account its interconnection with the other subsystems in order to approximate the entire system in a so-called structured manner. The purpose of this paper is to present both Krylov-based and Gramian-based model reduction techniques that preserve the structure of the interconnections. Several structured model reduction techniques existing in the literature appear as special cases of our approach, permitting to unify and generalize the theory to some extent.

Accurate frequency-domain macromodels are becoming increasingly important for the design, study and optimization of complex physical systems. These macromodels approximate the complex frequency-dependent input-output behaviour of broadband multi-port systems in the frequency domain by rational functions [28]. Unfortunately, due to the complexity of the physical systems under study and the dense discretization required for accurately modelling their behaviour, the rational or state-space macromodels may lead to unmanageable levels of storage and computational requirements. Therefore, Model Order Reduction (MOR) methods can be applied to build a model of reduced size, which captures the dynamics of the larger model as closely as possible.

With the rapid developments in Very Large Scale Integration (VLSI) technology at both the chip and package level, the operating frequencies are quickly reaching the vicinity of GHz and switching times are getting to the sub-nano second levels. The ever increasing quest for high-speed applications has placed higher demands on interconnect performance and highlighted the previously negligible effects of interconnects such as ringing, signal delay, distortion, reflections and crosstalk. As depicted by Figure 1, interconnects can exist at various levels of design hierarchy such as on-chip, packaging structures, multichip modules, printed circuit boards and backplanes. In addition, the trend in the VLSI industry towards miniature designs, low power consumption and increased integration of analog circuits with digital blocks has further complicated the issue of signal integrity analysis. It is predicted that interconnects will be responsible for majority of signal degradation in high-speed systems [1]. High-speed interconnect problems are not always handled appropriately by the conventional circuit simulators, such as SPICE [2]. If not considered during the design stage, these interconnect effects can cause logic glitches which render a fabricated digital circuit inoperable, or they can distort an analog signal such that it fails to meet specifications. Since extra iterations in the design cycle are costly, accurate prediction of these effects is a necessity in high-speed designs. Hence it becomes extremely important for designers to simulate the entire design along with interconnect subcircuits as efficiently as possible while retaining the accuracy of simulation.

We present a methodology and computational environment for applying mathematical model order reduction (MOR) to electro-thermal MEMS^I. MOR can successfully create dynamic compact thermal models of MEMS devices. It is currently possible to use software tool “MOR for ANSYS” (pronounced “more for ANSYS”) to automatically create reduced order thermal models directly from ANSYS models with more than 500 000 degrees of freedom. Model order reduction is automatic and based on the implicit Pad approximation of the transfer function via the Arnoldi algorithm. After model reduction, one can visualize simulation results of the reduced model in Mathematica and can call the SLICOT library via the Mathlink interface in order to obtain mathematically optimal reduced models. Reduced models are easily convertible into hardware description language (HDL) form, and can be directly used for system-level simulation.

In this chapter, we will focus on direct techniques for reduction of RC circuits. Compared to iterative techniques, which are frequently (usually) based on subspace projection techniques, direct techniques are based on Gaussian Elimination or equivalent techniques.

In this chapter, we will focus on the reduction of RC circuits. Formally, given a linear RC (sub-)circuit, let us define port nodes as a input or output nodes of the circuit. Typically, these are connected to the real inputs and outputs of the circuit or to the terminals of the active devices. Also, internal nodes are all the remaining nodes. Then, reduction aims at removing internal nodes and (resistive or capacitive) branches connecting them such that the result is simpler but still accurate enough. Port nodes typically should be preserved, although sometimes they can be merged without a large accuracy penalty.

The models of passive components have to describe all relevant electromagnetic field effects at high frequency encountered inside these devices. These effects are quantified by the Maxwell equations of the electromagnetic field in full wave (FW) regime. Therefore, at the first level of approximation, the model of a passive device is defined by an electromagnetic (EM) field problem, formulated by Maxwell partial differential equations with appropriate boundary and initial conditions. This problem defines a consistent I/O system which has a unique response, described by the output signals, for any input signal applied as terminal excitations. This system with distributed parameters has an infinite dimension state space, but a finite number of inputs and outputs related to the device terminals.