Rozprawy doktorskie na temat „Multilevel 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

Ce travail de recherche présente une extension de la construction classique des modèles réduits (ROMs) obtenus par analyse modale, en dynamique numérique des structures linéaires. Cette extension est basée sur une stratégie de projection multi-niveau, pour l'analyse dynamique des structures complexes en présence d'incertitudes. De nos jours, il est admis qu'en dynamique des structures, la prévision sur une large bande de fréquence obtenue à l'aide d'un modèle éléments finis doit être améliorée en tenant compte des incertitudes de modèle induites par les erreurs de modélisation, dont le rôle croît avec la fréquence. Dans un tel contexte, l'approche probabiliste non-paramétrique des incertitudes est utilisée, laquelle requiert l'introduction d'un ROM. Par conséquent, ces deux aspects, évolution fréquentielle des niveaux d'incertitudes et réduction de modèle, nous conduisent à considérer le développement d'un ROM multi-niveau, pour lequel les niveaux d'incertitudes dans chaque partie de la bande de fréquence peuvent être adaptés. Dans cette thèse, on s'intéresse à l'analyse dynamique de structures complexes caractérisées par la présence de plusieurs niveaux structuraux, par exemple avec un squelette rigide qui supporte diverses sous-parties flexibles. Pour de telles structures, il est possible d'avoir, en plus des modes élastiques habituels dont les déplacements associés au squelette sont globaux, l'apparition de nombreux modes élastiques locaux, qui correspondent à des vibrations prédominantes des sous-parties flexibles. Pour ces structures complexes, la densité modale est susceptible d'augmenter fortement dès les basses fréquences (BF), conduisant, via la méthode d'analyse modale, à des ROMs de grande dimension (avec potentiellement des milliers de modes élastiques en BF). De plus, de tels ROMs peuvent manquer de robustesse vis-à-vis des incertitudes, en raison des nombreux déplacements locaux qui sont très sensibles aux incertitudes. Il convient de noter qu'au contraire des déplacements globaux de grande longueur d'onde caractérisant la bande BF, les déplacements locaux associés aux sous-parties flexibles de la structure, qui peuvent alors apparaître dès la bande BF, sont caractérisés par de courtes longueurs d'onde, similairement au comportement dans la bande hautes fréquences (HF). Par conséquent, pour les structures complexes considérées, les trois régimes vibratoires BF, MF et HF se recouvrent, et de nombreux modes élastiques locaux sont entremêlés avec les modes élastiques globaux habituels. Cela implique deux difficultés majeures, concernant la quantification des incertitudes d'une part et le coût numérique d'autre part. L'objectif de cette thèse est alors double. Premièrement, fournir un ROM stochastique multi-niveau qui est capable de rendre compte de la variabilité hétérogène introduite par le recouvrement des trois régimes vibratoires. Deuxièmement, fournir un ROM prédictif de dimension réduite par rapport à celui de l'analyse modale. Une méthode générale est présentée pour la construction d'un ROM multi-niveau, basée sur trois bases réduites (ROBs) dont les déplacements correspondent à l'un ou l'autre des régimes vibratoires BF, MF ou HF (associés à des déplacements de type BF, de type MF ou bien de type HF). Ces ROBs sont obtenues via une méthode de filtrage utilisant des fonctions de forme globales pour l'énergie cinétique (par opposition aux fonctions de forme locales des éléments finis). L'implémentation de l'approche probabiliste non-paramétrique dans le ROM multi-niveau permet d'obtenir un ROM stochastique multi-niveau avec lequel il est possible d'attribuer un niveau d'incertitude spécifique à chaque ROB. L'application présentée est relative à une automobile, pour laquelle le ROM stochastique multi-niveau est identifié par rapport à des mesures expérimentales. Le ROM proposé permet d'obtenir une dimension réduite ainsi qu'une prévision améliorée, en comparaison avec un ROM stochastique classique
This work deals with an extension of the classical construction of reduced-order models (ROMs) that are obtained through modal analysis in computational linear structural dynamics. It is based on a multilevel projection strategy and devoted to complex structures with uncertainties. Nowadays, it is well recognized that the predictions in structural dynamics over a broad frequency band by using a finite element model must be improved in taking into account the model uncertainties induced by the modeling errors, for which the role increases with the frequency. In such a framework, the nonparametric probabilistic approach of uncertainties is used, which requires the introduction of a ROM. Consequently, these two aspects, frequency-evolution of the uncertainties and reduced-order modeling, lead us to consider the development of a multilevel ROM in computational structural dynamics, which has the capability to adapt the level of uncertainties to each part of the frequency band. In this thesis, we are interested in the dynamical analysis of complex structures in a broad frequency band. By complex structure is intended a structure with complex geometry, constituted of heterogeneous materials and more specifically, characterized by the presence of several structural levels, for instance, a structure that is made up of a stiff main part embedding various flexible sub-parts. For such structures, it is possible having, in addition to the usual global-displacements elastic modes associated with the stiff skeleton, the apparition of numerous local elastic modes, which correspond to predominant vibrations of the flexible sub-parts. For such complex structures, the modal density may substantially increase as soon as low frequencies, leading to high-dimension ROMs with the modal analysis method (with potentially thousands of elastic modes in low frequencies). In addition, such ROMs may suffer from a lack of robustness with respect to uncertainty, because of the presence of the numerous local displacements, which are known to be very sensitive to uncertainties. It should be noted that in contrast to the usual long-wavelength global displacements of the low-frequency (LF) band, the local displacements associated with the structural sub-levels, which can then also appear in the LF band, are characterized by short wavelengths, similarly to high-frequency (HF) displacements. As a result, for the complex structures considered, there is an overlap of the three vibration regimes, LF, MF, and HF, and numerous local elastic modes are intertwined with the usual global elastic modes. This implies two major difficulties, pertaining to uncertainty quantification and to computational efficiency. The objective of this thesis is thus double. First, to provide a multilevel stochastic ROM that is able to take into account the heterogeneous variability introduced by the overlap of the three vibration regimes. Second, to provide a predictive ROM whose dimension is decreased with respect to the classical ROM of the modal analysis method. A general method is presented for the construction of a multilevel ROM, based on three orthogonal reduced-order bases (ROBs) whose displacements are either LF-, MF-, or HF-type displacements (associated with the overlapping LF, MF, and HF vibration regimes). The construction of these ROBs relies on a filtering strategy that is based on the introduction of global shape functions for the kinetic energy (in contrast to the local shape functions of the finite elements). Implementing the nonparametric probabilistic approach in the multilevel ROM allows each type of displacements to be affected by a particular level of uncertainties. The method is applied to a car, for which the multilevel stochastic ROM is identified with respect to experiments, solving a statistical inverse problem. The proposed ROM allows for obtaining a decreased dimension as well as an improved prediction with respect to a classical stochastic ROM

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

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.

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.