Rozprawy doktorskie na temat „Augmented Krylov Model Order Reduction”

The use of Krylov subspace model order reduction for nonlinear/bilinear systems, over the past few years, has become an increasingly researched area of study. The need for model order reduction has never been higher, as faster computations for control, diagnosis and prognosis have never been higher to achieve better system performance. Krylov subspace model order reduction techniques enable this to be done more quickly and efficiently than what can be achieved at present. The most recent advances in the use of Krylov subspaces for reducing bilinear models match moments and multimoments at some expansion points which have to be obtained through an optimisation scheme. This therefore removes the computational advantage of the Krylov subspace techniques implemented at an expansion point zero. This thesis demonstrates two improved approaches for the use of one-sided Krylov subspace projection for reducing bilinear models at the expansion point zero. This work proposes that an alternate linear approximation can be used for model order reduction. The advantages of using this approach are improved input-output preservation at a simulation cost similar to some earlier works and reduction of bilinear systems models which have singular state transition matrices. The comparison of the proposed methods and other original works done in this area of research is illustrated using various examples of single input single output (SISO) and multi input multi output (MIMO) models.

Thesis (Ph. D.)--University of California, Riverside, 2009.
Includes abstract. Available via ProQuest Digital Dissertations. Title from first page of PDF file (viewed March 12, 2010). Includes bibliographical references (p. 122-126). Also issued in print.

La solution numérique des systèmes dynamiques est un moyen efficace pour étudier des phénomènes physiques complexes. Cependant, dans un cadre à grande échelle, la dimension du système rend les calculs infaisables en raison des limites de mémoire et de temps, ainsi que le mauvais conditionnement. La solution de ce problème est la réduction de modèles. Cette thèse porte sur les méthodes de projection pour construire efficacement des modèles d'ordre inférieur à partir des systèmes linéaires dynamiques de grande taille. En particulier, nous nous intéressons à la projection sur la réunion de plusieurs sous-espaces de Krylov standard qui conduit à une classe de modèles d'ordre réduit. Cette méthode est connue par l'interpolation rationnelle. En se basant sur ce cadre théorique qui relie la projection de Krylov à l'interpolation rationnelle, quatre algorithmes de type Lanczos rationnel pour la réduction de modèles sont proposés. Dans un premier temps, nous avons introduit une méthode adaptative de type Lanczos rationnel par block pour réduire l'ordre des systèmes linéaires dynamiques de grande taille, cette méthode est basée sur l'algorithme de Lanczos rationnel par block et une méthode adaptative pour choisir les points d'interpolation. Une généralisation de ce premier algorithme est également donnée, où différentes multiplicités sont considérées pour chaque point d'interpolation. Ensuite, nous avons proposé une autre extension de la méthode du sous-espace de Krylov standard pour les systèmes à plusieurs-entrées plusieurs-sorties, qui est le sous-espace de Krylov global. Nous avons obtenu des équations qui décrivent cette procédure. Finalement, nous avons proposé une méthode de Lanczos étendu par block et nous avons établi de nouvelles propriétés algébriques pour cet algorithme. L'efficacité et la précision de tous les algorithmes proposés, appliqués sur des problèmes de réduction de modèles, sont testées dans plusieurs exemples numériques
Numerical solution of dynamical systems have been a successful means for studying complex physical phenomena. However, in large-scale setting, the system dimension makes the computations infeasible due to memory and time limitations, and ill-conditioning. The remedy of this problem is model reductions. This dissertations focuses on projection methods to efficiently construct reduced order models for large linear dynamical systems. Especially, we are interesting by projection onto unions of Krylov subspaces which lead to a class of reduced order models known as rational interpolation. Based on this theoretical framework that relate Krylov projection to rational interpolation, four rational Lanczos-type algorithms for model reduction are proposed. At first, an adaptative rational block Lanczos-type method for reducing the order of large scale dynamical systems is introduced, based on a rational block Lanczos algorithm and an adaptive approach for choosing the interpolation points. A generalization of the first algorithm is also given where different multiplicities are consider for each interpolation point. Next, we proposed another extension of the standard Krylov subspace method for Multiple-Input Multiple-Output (MIMO) systems, which is the global Krylov subspace, and we obtained also some equations that describe this process. Finally, an extended block Lanczos method is introduced and new algebraic properties for this algorithm are also given. The accuracy and the efficiency of all proposed algorithms when applied to model order reduction problem are tested by means of different numerical experiments that use a collection of well known benchmark examples

Dynamical systems are mathematical models characterized by a set of differential or difference equations. Model reduction aims to replace the original system with a reduced system of significantly smaller dimension that still describes the important dynamics of the large-scale model. Interpolatory model reduction methods define a reduced model that interpolates the full model at selected interpolation points. The reduced model may be obtained through a Krylov reduction process or by using the Iterative Rational Krylov Algorithm (IRKA), which iterates this Krylov reduction process to obtain an optimal $\mathcal{H}_2$ reduced model. This dissertation studies interpolatory model reduction for first-order descriptor systems, second-order systems, and DAEs. The main computational cost of interpolatory model reduction is the associated linear systems. Especially in the large-scale setting, inexact solves become desirable if not necessary. With the introduction of inexact solutions, however, exact interpolation no longer holds. While the effect of this loss of interpolation has previously been studied, we extend the discussion to the preconditioned case. Then we utilize IRKA's convergence behavior to develop preconditioner updates. We also consider the interpolatory framework for DAEs and second-order systems. While interpolation results still hold, the singularity associated with the DAE often results in unbounded model reduction errors. Therefore, we present a theorem that guarantees interpolation and a bounded model reduction error. Since this theorem relies on expensive projectors, we demonstrate how interpolation can be achieved without explicitly computing the projectors for index-1 and Hessenberg index-2 DAEs. Finally, we study reduction techniques for second-order systems. Many of the existing methods for second-order systems rely on the model's associated first-order system, which results in computations of a $2n$ system. As a result, we present an IRKA framework for the reduction of second-order systems that does not involve the associated $2n$ system. The resulting algorithm is shown to be effective for several dynamical systems.
Ph. D.

MOR (Model Order Reduction) est devenu un domaine très répondu dans la recherche grâce à l'intérêt qu'il peut apporter dans la réduction des systèmes, ce qui permet d'économiser du temps, de la mémoire et le coût de CPU pour les outils de CAO. Ce domaine contient principalement deux branches: linéaires et non linéaires. MOR linéaire est un domaine mature avec des techniques numériques bien établie et bien connus dans la domaine de la recherche, par contre le domaine non linéaire reste vague, et jusqu'à présent il n'a pas montré des bons résultats dans la simulation des circuits électriques. La recherche est toujours en cours dans ce domaine, en raison de l’intérêt qu'il peut fournir aux simulateurs contemporains, surtout avec la croissance des puces électroniques en termes de taille et de complexité, et les exigences industrielles vers l'intégration des systèmes sur la même puce.Une contribution significative, pour résoudre le problème de Harmonic Balance (Equilibrage Harmonique) en utilisant la technique MOR, a été proposé en 2002 par E. Gad et M. Nakhla. La technique a montré une réduction substantielle de la dimension du système, tout en préservant, en sortie, la précision de l'analyse en régime permanent. Cette méthode de MOR utilise la technique de projection par l'intermédiaire de Krylov, et il préserve la passivité du système. Cependant, il souffre de quelques limitations importantes dans la construction de la matrice “pre-conditioner“ qui permettrait de réduire le système. La limitation principale est la nécessité d'une factorisation explicite comme une suite numérique de l'équation des dispositifs non linéaires . cette limitation rend la technique difficile à appliquer dans les conditions générales d'un simulateur. Cette thèse examinera les aspects non linéaires du modèle de réduction pour les équations de bilan harmoniques, et il étudiera les solutions pour surmonter les limitations mentionnées ci-dessus, en particulier en utilisant des approches de dérivateur numériques
MOR recently became a well-known research field, due to the interest that it shows in reducing the system, which saves time, memory, and CPU cost for CAD tools. This field contains two branches, linear and nonlinear MOR, the linear MOR is a mature domain with well-established theory and numerical techniques. Meanwhile, nonlinear MOR domain is still stammering, and so far it didn’t show good and successful results in electrical circuit simulation. Some improvements however started to pop-up recently, and research is still going on this field because of the help that it can give to the contemporary simulators, especially with the growth of the electronic chips in terms of size and complexity due to industrial demands towards integrating systems on the same chip. A significant contribution in the MOR technique of HB solution has been proposed a decade ago by E. Gad and M. Nakhla. The technique has shown to provide a substantial system dimension reduction while preserving the precision of the output in steady state analysis. This MOR method uses the technique of projection via Krylov, and it preserves the passivity of the system. However, it suffers a number of important limitations in the construction of the pre-conditioner matrix which is ought to reduce the system. The main limitation is the necessity for explicit factorization as a power series of the equation of the nonlinear devices. This makes the technique difficult to apply in general purpose simulator conditions. This thesis will review the aspects of the nonlinear model order reduction technique for harmonic balance equations, and it will study solutions to overcome the above mentioned limitations, in particular using numerical differentiation approaches

Die FEM-MKS-Kopplung erfordert Modellordnungsreduktions-Verfahren, die mit kleiner reduzierter Systemdimension das Übertragungsverhalten mechanischer Strukturen abbilden. Rationale Krylov-Unterraum-Verfahren, basierend auf dem Arnoldi-Algorithmen, ermöglichen solche Abbildungen in frei wählbaren, breiten Frequenzbereichen. Ziel ist der Entwurf einer fehlerüberwachten Modelreduktion auf Basis von Krylov-Unterraumverfahren und Anwendung auf ein strukturmechanisches Model. Auf Grundlage der Software MORPACK wird eine Arnoldi-Funktion erster Ordnung um interpolativen Startvektor, Eliminierung der Starrkörperbewegung und Reorthogonalisierung erweitert. Diese Operationen beinhaltend, wird ein rationales, interpolatives SOAR-Verfahren entwickelt. Ein rationales Block-SOAR-Verfahren erweist sich im Vergleich als unterlegen. Es wird interpolative Gleichwichtung verwendet. Das Arnoldi-Verfahren zeichnet kleiner Berechnungsaufwand aus. Das rationale, interpolative SOAR liefert kleinere reduzierte Systemdimensionen für gleichen abgebildeten Frequenzbereich. Die Funktionen werden auf Rahmen-, Getriebegehäuse- und Treibsatzwellen-Modelle angewendet. Zur Fehlerbewertung wird eigenfrequenzbasiert ein H2-Integrationsbereich festgelegt und der übertragungsfunktionsbasierte, relative H2-Fehler berechnet. Es werden zur Lösung linearer Gleichungssysteme mit Matlab entsprechende Löser-Funktionen, auf Permutation und Faktorisierung basierend, implementiert
FEM-MKS-coupling requires model order reduction methods to simulate the frequency response of mechanical structures using a smaller reduced representation of the original system. Most of the rational Krylov-subspace methods are based on Arnoldi-algorithms. They allow to represent the frequency response in freely selectable, wide frequency ranges. Subject of this thesis is the implementation of an error-controlled model order reduction based on Krylov-subspace methods and the application to a mechanical model. Based on the MORPACK software, a first-order-Arnoldi function is extended by an interpolative start vector, the elimination of rigid body motion and a reorthogonalization. Containing these functions, a rational, interpolative Second Order Arnoldi (SOAR) method is designed that works well compared to a rational Block-SOAR-method. Interpolative equal weighting is used. The first-order-Arnoldi method requires less computational effort compared to the rational, interpolative SOAR that is able to compute a smaller reduction size for same frequency range of interest. The methods are applied to the models of a frame, a gear case and a drive shaft. Error-control is realized by eigenfrequency-based H2-integration-limit and relative H2-error based on the frequency response function. For solving linear systems of equations in Matlab, solver functions based on permutation and factorization are implemented

Model order reduction (MOR) refers to the process of reducing the size of large scale discrete systems with the goal of capturing their behavior in a small and tractable model known as the reduced order model (ROM). ROMs are invariably constructed by projecting the original system onto a low rank subspace that captures the physics for specified range/s of parameter/s. The parameters, say for electromagnetic scattering, can be the frequency of excitation, angle of incidence, and/or material parameters. Thus, ROMs enable fast parameter sweep analysis and quick prototyping. Historically, a majority of the MOR techniques dealt with systems that are either linear or linearizable. Such techniques were developed around the numerically robust and computationally efficient Krylov subspace methods such as the Arnoldi or the Lanczos algorithm for single input, single output (SISO) systems. For multiple input, multiple output (MIMO) case, the block versions of these algorithms were used. In particular, the Lanczos algorithm could be used to construct a Padé approximation of the original system. Furthermore, since Krylov subspace based ROMs could preserve important attributes of the original system, like passivity, they were specifically popular in large-scale interconnect modeling. However, the frequency domain finite element method (FEM) (used in this work), in the presence of absorbing boundaries (or perfectly matched layers) and/or losses in the media leads to matrix systems that exhibit nonlinear dependence on the frequency of excitation. One can approximate this nonlinear dependence with a matrix polynomial system through Taylor expansion and linearize the system followed by a projection via Arnoldi (PVA) or Padé via Lanczos (PVL) to construct the ROM. However, linearizations usually increase the system size depending upon the polynomial degree besides having a different sparsity pattern than the matrix polynomial. Alternatively, one can tackle the nonlinearity directly by matching the moments using what is known as asymptotic waveform evaluation (AWE). AWE is inherently an ill-conditioned process. A recent work known as the well-conditioned AWE (WCAWE) improves its conditioning by enforcing implicit orthonormalization while still matching moments, by introducing some correction terms. However, WCAWE can be cumbersome to implement and appears to be inherently sequential. This work reports a novel perspective on the AWE space and proposes a parallelizable multilevel Krylov subspace generation technique that improves the accuracy/bandwidth of the ROM even further. We also introduce a novel adaptation of the Jacobi-Davidson algorithm, which is used to solve nonlinear eigenvalue problems (NLEVP), to target solutions and their derivatives (AWE space) for the matrix system rather than the underlying NLEVP, and formulate its well-conditioned form. By doing so, we enable the use of a new preconditioned iterative solver for AWE. Finally, noting the bottleneck posed by the reassembly of excitation vector derivatives at the expansion points in certain types of multipoint AWE ROMs, we propose an algorithm to reuse the derivatives, thus saving on the ROM setup time considerably, without sacrificing accuracy. The efficacy of the proposed algorithms is verified through several practical examples. The work is concluded with pointers to many possibilities for future research, like preconditioners, parallelization and domain-decomposition.

In this paper we present an approach to the nonlinear model reduction based on representing the nonlinear system with a piecewise-linear system and then reducing each of the pieces with a Krylov projection. However, rather than approximating the individual components to make a system with exponentially many different linear regions, we instead generate a small set of linearizations about the state trajectory which is the response to a 'training input'. Computational results and performance data are presented for a nonlinear circuit and a micromachined fixed-fixed beam example. These examples demonstrate that the macromodels obtained with the proposed reduction algorithm are significantly more accurate than models obtained with linear or the recently developed quadratic reduction techniques. Finally, it is shown tat the proposed technique is computationally inexpensive, and that the models can be constructed 'on-the-fly', to accelerate simulation of the system response.
Singapore-MIT Alliance (SMA)

Miniaturisation of electronic chips poses challenges at the design stage. The progressively decreasing circuit dimensions result in complex electrical behaviour that necessitates complex models. Simulation of complex circuit models involves extraordinarily large compu- tational complexity. Such complexity is better managed through Model Order Reduction. Model order reduction has been successful in large reductions in system order for most types of circuits, at high levels of accuracy. However, multiport circuits with large number of inputs/outputs, pose an additional computational challenge. A strategy based on exible clustering of interconnects results in more e cient reduction of multiport circuits. Clustering methods traditionally use Krylov-subspace methods such as PRIMA for the actual model reduction step. These clustering methods are unable to reduce the model order to the optimum extent. SVD-based methods like Truncated Balanced Realization have shown higher reduction potential than Krylov-subspace methods. In this thesis, the di erences in reduction potential and computational cost thereof between SVD-based methods and Krylov-subspace methods are identi ed, analyzed and quanti ed. A novel algorithm has been developed, utilizing a particular combination of both these methods to achieve better results. It enhances the clustering method for model reduction using Truncated Balanced Realization as a second-level reduction technique. The algorithm is tested and signi cant gains are illustrated. The proposed novel algorithm preserves the other advantages of the current clustering algorithm.

Miniaturisation of electronic chips poses challenges at the design stage. The progressively decreasing circuit dimensions result in complex electrical behaviour that necessitates complex models. Simulation of complex circuit models involves extraordinarily large compu- tational complexity. Such complexity is better managed through Model Order Reduction. Model order reduction has been successful in large reductions in system order for most types of circuits, at high levels of accuracy. However, multiport circuits with large number of inputs/outputs, pose an additional computational challenge. A strategy based on exible clustering of interconnects results in more e cient reduction of multiport circuits. Clustering methods traditionally use Krylov-subspace methods such as PRIMA for the actual model reduction step. These clustering methods are unable to reduce the model order to the optimum extent. SVD-based methods like Truncated Balanced Realization have shown higher reduction potential than Krylov-subspace methods. In this thesis, the di erences in reduction potential and computational cost thereof between SVD-based methods and Krylov-subspace methods are identi ed, analyzed and quanti ed. A novel algorithm has been developed, utilizing a particular combination of both these methods to achieve better results. It enhances the clustering method for model reduction using Truncated Balanced Realization as a second-level reduction technique. The algorithm is tested and signi cant gains are illustrated. The proposed novel algorithm preserves the other advantages of the current clustering algorithm.

Transiente Simulationen im Rahmen von Parameterstudien oder Optimierungsprozessen erfor-dern die Anwendung der Modellordnungsreduktion zur Minimierung der Berechnungs¬zeiten. Die aus der Wärmestrahlung resultierende Nichtlinearität bei der Analyse thermischer Felder wird hier als äußere Last betrachtet, wodurch die entkoppelte Ermittlung der strahlungs-beding¬ten Wärmeströme gelingt. Darüber hinaus ermöglichen die infolgedessen konstanten System¬matrizen die Reduktion des Temperaturvektors mit etablierten Verfahren für lineare Systeme, wie beispielsweise den Krylov-Unterraummethoden. Die aus der in der Regel großflächigen Verteilung der thermischen Lasten folgende hohe Anzahl von Systemeingängen limitiert allerdings die erzielbare reduzierte Dimension. Deshalb werden zustandsunabhängige, sich synchron verändernde Lasten zu einem Eingang zusammengefasst. Die aus der Strahlung resultierenden Wärmeströme sind im Gegensatz dazu durch die aktuelle Temperaturverteilung bestimmt und lassen sich nicht derart gruppieren. Vor diesem Hintergrund wird ein Ansatz basierend auf der Singulärwertzerlegung von aus Trai¬ningssimulationen gewonnenen Beispiellastvektoren vorgeschlagen. Auf diese Weise gelingt eine erhebliche Verringerung der Eingangsanzahl, sodass im reduzierten System ein sehr geringer Freiheitsgrad erreicht wird. Im Vergleich zur Proper Orthogonal Decomposition (POD) genügen dabei deutlich weniger Trainingsdaten, was den Rechenaufwand während der Offline-Phase erheblich vermindert. Darüber hinaus dehnt das entwickelte Verfahren die Gültigkeit des reduzierten Modells auf einen weiten Parameterbereich aus. Die Berechnung der strahlungsbedingten Wärmeströme in der Ausgangsdimension bestimmt dann den numerischen Aufwand. Mit der Discrete Empirical Interpolation Method (DEIM) wird die Auswertung der Nichtlinearität auf ausgewählte Modellknoten beschränkt. Schließlich erlaubt die Anwendung der POD auf die Wärmestrahlungsbilanz die schnelle Anpassung des Emissionsgrades. Somit hängt das reduzierte System nicht mehr vom ursprünglichen Freiheitsgrad ab und die Gesamt-simulationszeit verkürzt sich um mehrere Größenordnungen.
Transient simulations as part of parameter studies or optimization processes require the appli-cation of model order reduction to minimize computation times. Nonlinearity resulting from heat radiation in thermal analyses is considered here as an external load. Thereby, the determi-nation of the radiation-induced heat flows is decoupled from the temperature equation. Hence, the system matrices become invariant and established algorithms for linear systems, such as Krylov Subspace Methods, can be used for the reduction of the temperature vector. However, in general the achievable reduced dimension is limited as the thermal loads distributed over large parts of the surface lead to a high number of system inputs. Therefore, state-independent, synchronously changing loads are combined into one input. In contrast, the heat flows resulting from radiation are determined by the current temperature distribution and cannot be grouped in this way. Against this background, an approach based on the singular value decomposition of snapshots obtained from training simulations is proposed allowing a considerable decreased input number and a very low degree of freedom in the reduced system. Compared to Proper Orthogonal Decomposition (POD), significantly less training data is required reducing the computational costs during the offline phase. In addition, the developed method extends the validity of the reduced model to a wide parameter range. The computation of the radiation-induced heat flows, which is performed in the original dimension, then determines the numerical effort. The Discrete Empirical Interpolation Method (DEIM) restricts the evaluation of the nonlinearity to selected model nodes. Finally, the application of the POD to the heat radiation equation enables a rapid adjustment of the emissivity. Thus, the reduced system is no longer dependent on the original degree of freedom and the total simulation time is shortened by several orders of magnitude.

Small signal stability has always been an important concern for analog designers. Recent advances such as the Loop Finder algorithm allows designers to detect and identify local, potentially unstable return loops without the need to identify and add breakpoints. However, this method suffers from extremely high time and memory complexity and thus cannot be scaled to very large analog circuits. In this research work, we first take an in-depth look at the loop finder algorithm so as to identify certain key enhancements that can be made to overcome these shortcomings. We next propose pole discovery and impedance computation methods that address these shortcomings by exploring only a certain region of interest in the s-plane. The reduced time and memory complexity obtained via the new methodology allows us to extend automatic stability checking to much larger circuits than was previously possible.