Spelling suggestions: "subject:"krylovsubspace"" "subject:"krylovsubspaces""
31 |
Rational Lanczos-type methods for model order reduction / Méthodes de type Lanczos rationnel pour la réduction de modèlesBarkouki, Houda 22 December 2016 (has links)
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.
|
32 |
Clustering for Model Reduction of Circuits : Multi-level TechniquesMilind, R January 2014 (has links) (PDF)
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.
|
33 |
Enlarged Krylov Subspace Methods and Preconditioners for Avoiding Communication / Méthodes de sous-espace de krylov élargis et préconditionneurs pour réduire les communicationsMoufawad, Sophie 19 December 2014 (has links)
La performance d'un algorithme sur une architecture donnée dépend à la fois de la vitesse à laquelle le processeur effectue des opérations à virgule flottante (flops) et de la vitesse d'accès à la mémoire et au disque. Etant donné que le coût de la communication est beaucoup plus élevé que celui des opérations arithmétiques, celle-là forme un goulot d'étranglement dans les algorithmes numériques. Récemment, des méthodes de sous-espace de Krylov basées sur les méthodes 's-step' ont été développées pour réduire les communications. En effet, très peu de préconditionneurs existent pour ces méthodes, ce qui constitue une importante limitation. Dans cette thèse, nous présentons le préconditionneur nommé ''Communication-Avoiding ILU0'', pour la résolution des systèmes d’équations linéaires (Ax=b) de très grandes tailles. Nous proposons une nouvelle renumérotation de la matrice A ('alternating min-max layers'), avec laquelle nous montrons que le préconditionneur en question réduit la communication. Il est ainsi possible d’effectuer « s » itérations d’une méthode itérative préconditionnée sans communication. Nous présentons aussi deux nouvelles méthodes itératives, que nous nommons 'multiple search direction with orthogonalization CG' (MSDO-CG) et 'long recurrence enlarged CG' (LRE-CG). Ces dernières servent à la résolution des systèmes linéaires d’équations de très grandes tailles, et sont basées sur l’enrichissement de l’espace de Krylov par la décomposition du domaine de la matrice A. / The performance of an algorithm on any architecture is dependent on the processing unit’s speed for performing floating point operations (flops) and the speed of accessing memory and disk. As the cost of communication is much higher than arithmetic operations, and since this gap is expected to continue to increase exponentially, communication is often the bottleneck in numerical algorithms. In a quest to address the communication problem, recent research has focused on communication avoiding Krylov subspace methods based on the so called s-step methods. However there are very few communication avoiding preconditioners, and this represents a serious limitation of these methods. In this thesis, we present a communication avoiding ILU0 preconditioner for solving large systems of linear equations (Ax=b) by using iterative Krylov subspace methods. Our preconditioner allows to perform s iterations of the iterative method with no communication, by applying a heuristic alternating min-max layers reordering to the input matrix A, and through ghosting some of the input data and performing redundant computation. We also introduce a new approach for reducing communication in the Krylov subspace methods, that consists of enlarging the Krylov subspace by a maximum of t vectors per iteration, based on the domain decomposition of the graph of A. The enlarged Krylov projection subspace methods lead to faster convergence in terms of iterations and to parallelizable algorithms with less communication, with respect to Krylov methods. We discuss two new versions of Conjugate Gradient, multiple search direction with orthogonalization CG (MSDO-CG) and long recurrence enlarged CG (LRE-CG).
|
34 |
A rational SHIRA method for the Hamiltonian eigenvalue problemBenner, Peter, Effenberger, Cedric 07 January 2009 (has links)
The SHIRA method of Mehrmann and Watkins belongs among the structure preserving Krylov subspace methods for solving skew-Hamiltonian eigenvalue problems. It can also be applied to Hamiltonian eigenproblems by considering a suitable transformation. Structure induced shift-and-invert techniques are employed to steer the algorithm towards the interesting region of the spectrum. However, the shift cannot be altered in the middle of the computation without discarding the information that has been accumulated so far. This paper shows how SHIRA can be combined with ideas from Ruhe's Rational Krylov algorithm to yield a method that permits an adjustment of shift after every step of the computation, adding greatly to the flexibility of the algorithm. We call this new method rational SHIRA. A numerical example is presented to demonstrate its efficiency.
|
35 |
Novel Model Reduction Techniques for Control of Machine ToolsBenner, Peter, Bonin, Thomas, Faßbender, Heike, Saak, Jens, Soppa, Andreas, Zaeh, Michael 13 November 2009 (has links)
Computational methods for reducing the complexity of Finite Element (FE)
models in structural dynamics are usually based on modal analysis.
Classical approaches such as modal truncation, static condensation
(Craig-Bampton, Guyan), and component mode synthesis (CMS) are
available in many CAE tools such as ANSYS. In other disciplines, different
techniques for Model Order Reduction (MOR) have been developed in the
previous 2 decades. Krylov subspace methods are one possible
choice and often lead to much smaller models than modal truncation
methods given the same prescribed tolerance threshold. They have become
available to ANSYS users through the tool mor4ansys. A disadvantage
is that neither modal truncation nor CMS nor Krylov subspace methods
preserve properties important to control design. System-theoretic
methods like balanced truncation approximation (BTA), on the other
hand, are directed towards reduced-order models for use in closed-loop
control. So far, these methods are considered to be too expensive for
large-scale structural models. We show that recent algorithmic
advantages lead to MOR methods that are applicable to FE models in
structural dynamics and that can easily be integrated into CAE
software. We will demonstrate the efficiency of the proposed MOR
method based on BTA using a control system including as plant the FE
model of a machine tool.
|
36 |
Modellreduktion thermischer Felder unter Berücksichtigung der WärmestrahlungRother, Stephan 15 November 2019 (has links)
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.
|
37 |
Metody krylovovských podprostorů - Analýza a aplikace / Krylov Subspace Methods - Analysis and ApplicationGergelits, Tomáš January 2020 (has links)
Title: Krylov Subspace Methods - Analysis and Application Author: Tomáš Gergelits Department: Department of Numerical Mathematics Supervisor: prof. Ing. Zdeněk Strakoš, DrSc., Department of Numerical Mathematics Abstract: Convergence behavior of Krylov subspace methods is often studied for linear algebraic systems with symmetric positive definite matrices in terms of the condition number of the system matrix. As recalled in the first part of this thesis, their actual convergence behavior (that can be in practice also substantially affected by rounding errors) is however determined by the whole spectrum of the system matrix, and by the projections of the initial residual to the associated invariant subspaces. The core part of this thesis investigates the spectra of infinite dimensional operators −∇ · (k(x)∇) and −∇ · (K(x)∇), where k(x) is a scalar coefficient function and K(x) is a symmetric tensor function, preconditioned by the Laplace operator. Subsequently, the focus is on the eigenvalues of the matrices that arise from the discretization using conforming finite elements. Assuming continuity of K(x), it is proved that the spectrum of the preconditi- oned infinite dimensional operator is equal to the convex hull of the ranges of the diagonal function entries of Λ(x) from the spectral decomposition K(x) =...
|
38 |
Strategies For Recycling Krylov Subspace Methods and Bilinear Form EstimationSwirydowicz, Katarzyna 10 August 2017 (has links)
The main theme of this work is effectiveness and efficiency of Krylov subspace methods and Krylov subspace recycling. While solving long, slowly changing sequences of large linear systems, such as the ones that arise in engineering, there are many issues we need to consider if we want to make the process reliable (converging to a correct solution) and as fast as possible. This thesis is built on three main components. At first, we target bilinear and quadratic form estimation. Bilinear form $c^TA^{-1}b$ is often associated with long sequences of linear systems, especially in optimization problems. Thus, we devise algorithms that adapt cheap bilinear and quadratic form estimates for Krylov subspace recycling. In the second part, we develop a hybrid recycling method that is inspired by a complex CFD application. We aim to make the method robust and cheap at the same time. In the third part of the thesis, we optimize the implementation of Krylov subspace methods on Graphic Processing Units (GPUs). Since preconditioners based on incomplete matrix factorization (ILU, Cholesky) are very slow on the GPUs, we develop a preconditioner that is effective but well suited for GPU implementation. / Ph. D.
|
39 |
Krylov subspace methods for approximating functions of symmetric positive definite matrices with applications to applied statistics and anomalous diffusionSimpson, Daniel Peter January 2008 (has links)
Matrix function approximation is a current focus of worldwide interest and finds application in a variety of areas of applied mathematics and statistics. In this thesis we focus on the approximation of A..=2b, where A 2 Rnn is a large, sparse symmetric positive definite matrix and b 2 Rn is a vector. In particular, we will focus on matrix function techniques for sampling from Gaussian Markov random fields in applied statistics and the solution of fractional-in-space partial differential equations. Gaussian Markov random fields (GMRFs) are multivariate normal random variables characterised by a sparse precision (inverse covariance) matrix. GMRFs are popular models in computational spatial statistics as the sparse structure can be exploited, typically through the use of the sparse Cholesky decomposition, to construct fast sampling methods. It is well known, however, that for sufficiently large problems, iterative methods for solving linear systems outperform direct methods. Fractional-in-space partial differential equations arise in models of processes undergoing anomalous diffusion. Unfortunately, as the fractional Laplacian is a non-local operator, numerical methods based on the direct discretisation of these equations typically requires the solution of dense linear systems, which is impractical for fine discretisations. In this thesis, novel applications of Krylov subspace approximations to matrix functions for both of these problems are investigated. Matrix functions arise when sampling from a GMRF by noting that the Cholesky decomposition A = LLT is, essentially, a `square root' of the precision matrix A. Therefore, we can replace the usual sampling method, which forms x = L..T z, with x = A..1=2z, where z is a vector of independent and identically distributed standard normal random variables. Similarly, the matrix transfer technique can be used to build solutions to the fractional Poisson equation of the form n = A..=2b, where A is the finite difference approximation to the Laplacian. Hence both applications require the approximation of f(A)b, where f(t) = t..=2 and A is sparse. In this thesis we will compare the Lanczos approximation, the shift-and-invert Lanczos approximation, the extended Krylov subspace method, rational approximations and the restarted Lanczos approximation for approximating matrix functions of this form. A number of new and novel results are presented in this thesis. Firstly, we prove the convergence of the matrix transfer technique for the solution of the fractional Poisson equation and we give conditions by which the finite difference discretisation can be replaced by other methods for discretising the Laplacian. We then investigate a number of methods for approximating matrix functions of the form A..=2b and investigate stopping criteria for these methods. In particular, we derive a new method for restarting the Lanczos approximation to f(A)b. We then apply these techniques to the problem of sampling from a GMRF and construct a full suite of methods for sampling conditioned on linear constraints and approximating the likelihood. Finally, we consider the problem of sampling from a generalised Matern random field, which combines our techniques for solving fractional-in-space partial differential equations with our method for sampling from GMRFs.
|
40 |
Uma formulação implícita para o método Smoothed Particle Hydrodynamics / An implicit formulation for the Smoothed Particle Hydrodynamics MethodRicardo Dias dos Santos 17 February 2014 (has links)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Em uma grande gama de problemas físicos, governados por equações diferenciais, muitas
vezes é de interesse obter-se soluções para o regime transiente e, portanto, deve-se empregar
técnicas de integração temporal. Uma primeira possibilidade seria a de aplicar-se métodos
explícitos, devido à sua simplicidade e eficiência computacional. Entretanto, esses métodos frequentemente
são somente condicionalmente estáveis e estão sujeitos a severas restrições na
escolha do passo no tempo. Para problemas advectivos, governados por equações hiperbólicas,
esta restrição é conhecida como a condição de Courant-Friedrichs-Lewy (CFL). Quando temse
a necessidade de obter soluções numéricas para grandes períodos de tempo, ou quando o
custo computacional a cada passo é elevado, esta condição torna-se um empecilho. A fim de
contornar esta restrição, métodos implícitos, que são geralmente incondicionalmente estáveis,
são utilizados. Neste trabalho, foram aplicadas algumas formulações implícitas para a integração
temporal no método Smoothed Particle Hydrodynamics (SPH) de modo a possibilitar o uso
de maiores incrementos de tempo e uma forte estabilidade no processo de marcha temporal.
Devido ao alto custo computacional exigido pela busca das partículas a cada passo no tempo,
esta implementação só será viável se forem aplicados algoritmos eficientes para o tipo de estrutura
matricial considerada, tais como os métodos do subespaço de Krylov. Portanto, fez-se um
estudo para a escolha apropriada dos métodos que mais se adequavam a este problema, sendo
os escolhidos os métodos Bi-Conjugate Gradient (BiCG), o Bi-Conjugate Gradient Stabilized
(BiCGSTAB) e o Quasi-Minimal Residual (QMR). Alguns problemas testes foram utilizados a
fim de validar as soluções numéricas obtidas com a versão implícita do método SPH. / In a wide range of physical problems governed by differential equations, it is often of
interest to obtain solutions for the unsteady state and therefore it must be employed temporal
integration techniques. One possibility could be the use of an explicit methods due to its
simplicity and computational efficiency. However, these methods are often only conditionally
stable and are subject to severe restrictions for the time step choice. For advective problems
governed by hyperbolic equations, this restriction is known as the Courant-Friedrichs-Lewy
(CFL) condition. When there is the need to obtain numerical solutions for long periods of time,
or when the computational cost for each time step is high, this condition becomes a handicap.
In order to overcome this restriction implicit methods can be used, which are generally unconditionally
stable. In this study, some implicit formulations for time integration are used in the
Smoothed Particle Hydrodynamics (SPH) method to enable the use of larger time increments
and obtain a strong stability in the time evolution process. Due to the high computational cost
required by the particles tracking at each time step, the implementation will be feasible only if
efficient algorithms were applied for this type of matrix structure such as Krylov subspace methods.
Therefore, we carried out a study for the appropriate choice of methods best suited to this
problem, and the methods chosen were the Bi-Conjugate Gradient (BiCG), the Bi-Conjugate
Gradient Stabilized (BiCGSTAB) and the Quasi-Minimal Residual(QMR). Some test problems
were used to validate the numerical solutions obtained with the implicit version of the SPH
method.
|
Page generated in 0.0419 seconds