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.

[pt] Companhias de petróleo investindo no desenvolvimento de campos de hidrocarboneto dependem de estudos de reservatórios para realizarem previsões de produção e quantificarem os riscos associados à economicidade dos projetos. Neste sentido, a área de modelagem de reservatórios é de suma importância, sendo responsável por prever o desempenho futuro do reservatório sob diversas condições operacionais. Considerando que a solução dos sistemas de equações construídos a cada passo de tempo de uma simulação, durante o ciclo de linearização, é a parte que apresenta a maior demanda computacional, esta dissertação foca na análise de diferentes técnicas de solvers numéricos que podem ser aplicadas a simuladores, para mensurar seus desempenhos. Os solvers numéricos mais adequados para a solução de grandes sistemas de equações, tais como os encontrados em simulações de reservatórios, são os denominados solvers iterativos, que gradativamente aproximam a solução de um dado problema por meio da combinação de um método iterativo e um precondicionador. Os métodos iterativos avaliados nesta pesquisa foram o Gradiente Biconjugado Estabilizado (BiCGSTAB), Mínimos Resíduos Generalizado (GMRES) e Minimização Ortogonal (ORTHOMIN). Além disso, três técnicas de precondicionamento foram implementadas para auxiliar os métodos iterativos, sendo estas a Decomposição LU Incompleta (ILU), Fatoração Aninhada (NF) e Pressão Residual Restrita (CPR). A combinação destes diferentes métodos iterativos e precondicionadores permite a avaliação de diversas configurações distintas de solvers, em termos de seus desempenhos em um simulador. Os testes numéricos conduzidos neste trabalho utilizaram um novo simulador de reservatórios que está sendo desenvolvido pela Pontifícia Universidade Católica (PUC-Rio) em conjunto com a Petrobras. O objetivo dos testes foi analisar a robustez e eficiência de cada um dos solvers quanto à sua capacidade de resolver as equações de escoamento multifásico no meio poroso, visando assim auxiliar na seleção do solver mais adequado para o simulador. / [en] Petroleum companies investing in the development of hydrocarbon fields rely upon a variety of reservoir studies to perform production forecasts and quantify the risks associated with the economics of their projects. Integral to these studies is the discipline of reservoir modeling, responsible for predicting future reservoir performance under various operational conditions. Considering that the most time-demanding aspect of reservoir simulations is the solution of the systems of equations that arise within the linearization cycles at each time-step, this research focuses on analyzing different numerical solver techniques to be applied to a simulator, in order to assess their performance. The numerical solvers most suited for the solution of very large systems of equations, such as those encountered in reservoir simulations, are the so-called iterative solvers, which gradually approach the solution to a problem by combining an iterative strategy with a preconditioning method. The iterative methods examined in this research were the Stabilized Biconjugate Gradient (BiCGSTAB), the Generalized Minimum Residual (GMRES), and the Orthogonal Minimization (ORTHOMIN) methods. Furthermore, three preconditioning techniques were implemented to aid the iterative methods, namely the Incomplete LU Factorization (ILU), the Nested Factorization (NF), and the Constrained Pressure Residual (CPR) methods. The combination of these different iterative methods and preconditioners enables the appraisal of several distinct solver configurations, in terms of their performance in a simulator. The numerical tests conducted in this work made use of a new reservoir simulator currently under development at Pontifical Catholic University of Rio de Janeiro (PUC-Rio), as part of a joint project with Petrobras. The objective of these tests was to assess the robustness and efficiency of each solver in the solution of the multiphase flow equations in porous media, and support the selection of the solver most suited for the simulator.

In this thesis we present research on mathematical properties of methods for solv- ing symmetric systems of linear equations that arise in various optimization problem formulations and in methods for solving such problems. In the first and third paper (Paper A and Paper C), we consider the connection be- tween the method of conjugate gradients and quasi-Newton methods on strictly convex quadratic optimization problems or equivalently on a symmetric system of linear equa- tions with a positive definite matrix. We state conditions on the quasi-Newton matrix and the update matrix such that the search directions generated by the corresponding quasi-Newton method and the method of conjugate gradients respectively are parallel. In paper A, we derive such conditions on the update matrix based on a sufficient condition to obtain mutually conjugate search directions. These conditions are shown to be equivalent to the one-parameter Broyden family. Further, we derive a one-to-one correspondence between the Broyden parameter and the scaling between the search directions from the method of conjugate gradients and a quasi-Newton method em- ploying some well-defined update scheme in the one-parameter Broyden family. In paper C, we give necessary and sufficient conditions on the quasi-Newton ma- trix and on the update matrix such that equivalence with the method of conjugate gra- dients hold for the corresponding quasi-Newton method. We show that the set of quasi- Newton schemes admitted by these necessary and sufficient conditions is strictly larger than the one-parameter Broyden family. In addition, we show that this set of quasi- Newton schemes includes an infinite number of symmetric rank-one update schemes. In the second paper (Paper B), we utilize an unnormalized Krylov subspace frame- work for solving symmetric systems of linear equations. These systems may be incom- patible and the matrix may be indefinite/singular. Such systems of symmetric linear equations arise in constrained optimization. In the case of an incompatible symmetric system of linear equations we give a certificate of incompatibility based on a projection on the null space of the symmetric matrix and characterize a minimum-residual solu- tion. Further we derive a minimum-residual method, give explicit recursions for the minimum-residual iterates and characterize a minimum-residual solution of minimum Euclidean norm. / I denna avhandling betraktar vi matematiska egenskaper hos metoder för att lösa symmetriska linjära ekvationssystem som uppkommer i formuleringar och metoder för en mängd olika optimeringsproblem. I första och tredje artikeln (Paper A och Paper C), undersöks kopplingen mellan konjugerade gradientmetoden och kvasi-Newtonmetoder när dessa appliceras på strikt konvexa kvadratiska optimeringsproblem utan bivillkor eller ekvivalent på ett symmet- risk linjärt ekvationssystem med en positivt definit symmetrisk matris. Vi ställer upp villkor på kvasi-Newtonmatrisen och uppdateringsmatrisen så att sökriktningen som fås från motsvarande kvasi-Newtonmetod blir parallell med den sökriktning som fås från konjugerade gradientmetoden. I den första artikeln (Paper A), härleds villkor på uppdateringsmatrisen baserade på ett tillräckligt villkor för att få ömsesidigt konjugerade sökriktningar. Dessa villkor på kvasi-Newtonmetoden visas vara ekvivalenta med att uppdateringsstrategin tillhör Broydens enparameterfamilj. Vi tar också fram en ett-till-ett överensstämmelse mellan Broydenparametern och skalningen mellan sökriktningarna från konjugerade gradient- metoden och en kvasi-Newtonmetod som använder någon väldefinierad uppdaterings- strategi från Broydens enparameterfamilj. I den tredje artikeln (Paper C), ger vi tillräckliga och nödvändiga villkor på en kvasi-Newtonmetod så att nämnda ekvivalens med konjugerade gradientmetoden er- hålls. Mängden kvasi-Newtonstrategier som uppfyller dessa villkor är strikt större än Broydens enparameterfamilj. Vi visar också att denna mängd kvasi-Newtonstrategier innehåller ett oändligt antal uppdateringsstrategier där uppdateringsmatrisen är en sym- metrisk matris av rang ett. I den andra artikeln (Paper B), används ett ramverk för icke-normaliserade Krylov- underrumsmetoder för att lösa symmetriska linjära ekvationssystem. Dessa ekvations- system kan sakna lösning och matrisen kan vara indefinit/singulär. Denna typ av sym- metriska linjära ekvationssystem uppkommer i en mängd formuleringar och metoder för optimeringsproblem med bivillkor. I fallet då det symmetriska linjära ekvations- systemet saknar lösning ger vi ett certifikat för detta baserat på en projektion på noll- rummet för den symmetriska matrisen och karaktäriserar en minimum-residuallösning. Vi härleder även en minimum-residualmetod i detta ramverk samt ger explicita rekur- sionsformler för denna metod. I fallet då det symmetriska linjära ekvationssystemet saknar lösning så karaktäriserar vi en minimum-residuallösning av minsta euklidiska norm. / <p>QC 20150519</p>

Mit dem Begriff Wellenleiterquantenelektrodynamik (WQED) wird gemeinhin die Physik des quantisierten und in eindimensionalen Wellenleitern geführten Lichtes in Wechselwirkung mit einzelnen Emittern bezeichnet. In dieser Arbeit untersuche ich Effekte der WQED für einzelne Dreiniveausysteme (3NS) bzw. Paare von Zweiniveausystemen (2NS), die in den Wellenleiter eingebettet sind. Hierzu bediene ich mich hauptsächlich numerischer Methoden und betrachte die Modellsysteme im Rahmen der Drehwellennäherung. Ich untersuche die Dynamik der Streuung einzelner Photonen an einzelnen, in den Wellenleiter eingebetteten 3NS. Dabei analysiere ich den Einfluss dunkler bzw. nahezu dunkler Zustände der 3NS auf die Streuung und zeige, wie sich mit Hilfe stationärer elektrischer Treibfelder gezielt auf die Streuung einwirken lässt. Ich quantifiziere Verschränkung zwischen dem Lichtfeld im Wellenleiter und den Emittern mit Hilfe der Schmidt-Zerlegung und untersuche den Einfluss der Form der Einhüllenden eines Einzelphotonpulses auf die Ausbeute der Verschränkungserzeugung bei der Streuung des Photons an einem einzelnen Lambda-System im Wellenleiter. Hier zeigt sich, dass die Breite der Einhüllenden im k-Raum und die Emissionszeiten der beiden Übergänge des 3NS die maßgeblichen Parameter darstellen. Abschließend ergründe ich die Emissionsdynamik zweier im Abstand L in den Wellenleiter eingebetteter 2NS. Diese Dynamik wird insbesondere durch kavitätsartige und polaritonische Zustände des Systems aus Wellenleiter und Emitter ausschlaggebend beeinflusst. Bei der kollektiven Emission der 2NS treten - abhängig vom Abstand L - Sub- bzw. Superradianz auf. Dabei nimmt die Intensität dieser Effekte mit längerem Abstand L zu. Diese Eigenart lässt sich auf die Eindimensionalität des Wellenleiters zurückführen. / The field of waveguide quantum electrodynamics (WQED) deals with the physics of quantised light in one-dimensional (1D) waveguides coupled to single emitters. In this thesis, I investigate WQED effects for single three-level systems (3LS) and pairs of two-level systems (2LS), respectively, which are embedded in the waveguide. To this end, I utilise numerical techniques and consider all model systems within the rotating wave approximation. I investigate the dynamics of single-photon scattering by single, embedded 3LS. In doing so, I analyse the influence of dark and almost-dark states of the 3LS on the scattering dynamics. I also show, how stationary electrical driving fields can control the outcome of the scattering. I quantify entanglement between the waveguide''s light field and single emitters by utilising the Schmidt decomposition. I apply this formalism to a lambda-system embedded in a 1D waveguide and study the generation of entanglement by scattering single-photon pulses with different envelopes on the emitter. I show that this entanglement generation is mainly determined by the photon''s width in k-space and the 3LS''s emission times. Finally, I explore the emission dynamics of a pair of 2LS embedded by a distance L into the waveguide. These dynamics are primarily governed by bound states in the continuum and by polaritonic atom-photon bound-states. For collective emission processes of the two 2LS, sub- and superradiance appear and depend strongly on the 2LS''s distance: the effects increase for larger L. This is an exclusive property of the 1D nature of the waveguide.

Στη παρούσα διπλωματική εργασία ασχολούμαστε με την αποδοτική επίλυση ταινιακών και γενικών, αραιών γραμμικών συστημάτων σε παράλληλες αρχιτεκτονικές μέσω της οικογένειας αλγορίθμων Spike. Ζητούμενο είναι η βελτίωση (μείωση) του χρόνου επίλυσης μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη. Πιο συγκεκριμένα, επικεντρωνόμαστε στην επίλυση της εξίσωσης μητρώου $AX=F$ (1) όπου $A\in \mathbb{R}^{n\times n}$ είναι το μητρώο συντελεστών και το οποίο είναι αραιό ή/και ταινιακό, $F\in \mathbb{R}^{n\times s}$ είναι ένα μητρώο με $s$ στήλες το οποίο ονομάζεται μητρώο δεξιών μελών και $X\in \mathbb{R}^{n\times s}$ είναι η λύση του συστήματος. Μια σημαντική μέθοδος για την παράλληλη επίλυση της παραπάνω εξίσωσης, είναι η μέθοδος Spike και οι παραλλαγές της. Η μέθοδος Spike βασίζεται στη τεχνική διαίρει και βασίλευε και αποτελείται από δυο φάσεις: α) επίλυση ανεξάρτητων υπο-προβλημάτων τοπικά σε κάθε επεξεργαστή, και β) επίλυση ενός πολύ μικρότερου προβλήματος το οποίο απαιτεί επικοινωνία μεταξύ των επεξεργαστών. Οι δύο φάσεις συνδυάζονται ώστε να παραχθεί η τελική λύση $X$. Η συνεισφορά της διπλωματικής εργασίας έγκειται στην επιτάχυνση της οικογένειας αλγορίθμων Spike για την επίλυση της εξίσωσης (1) μέσω της μελέτης, το σχεδιασμό και την υλοποίηση νέων, περισσότερο αποδοτικών αλγοριθμικών σχημάτων τα οποία βασίζονται σε τεχνικές επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη. Αυτά τα νέα αλγοριθμικά σχήματα έχουν ως στόχο τη βελτίωση του χρόνου επίλυσης των γραμμικών συστημάτων καθώς και άλλα οφέλη όπως η αποδοτικότερη χρήση μνήμης. / In this thesis we focus on the efficient solution of general banded and general sparse linear systems on parallel architectures by exploiting the Spike family of algorithms. The equation of interest can be written in matrix form as $ AX = F $ (1) where $ A \ in \ mathbb {R} ^ {n \ times n} $ is the coefficient matrix, which is also sparse and / or banded, $ F \ in \ mathbb {R} ^ {n \ times s} $ is a matrix with $ s $ columns called matrix of the right hand sides and $ X \ in \ mathbb {R} ^ {n \ times s} $ is the solution of the system. An important method for the parallel solution of the above equation, is the Spike method and its variants. The Spike method is based on the divide and conquer technique and consists of two phases: a) solution of local, independent sub-problems in each processor, and b) solution of a much smaller problem which requires communication among the processors. The two phases are combined to produce the final solution $ X $. The contribution of this thesis is the acceleration of the Spike method for the solution of the matrix equation in (1) by studying, designing and implementing new, more efficient algorithmic schemes which are based on techniques used for the effective solution of linear systems with multiple right hand sides. These new algorithmic schemes were designed to improve the solving time of the linear systems as well as to provide other benefits such as more efficient use of memory.

Nous nous intéressons dans cette thèse, à l'étude de certaines méthodes numériques de type krylov dans le cas symplectique, en utilisant la technique de blocs. Ces méthodes, contrairement aux méthodes classiques, permettent à la matrice réduite de conserver la structure Hamiltonienne ou anti-Hamiltonienne ou encore symplectique d'une matrice donnée. Parmi ces méthodes, nous nous sommes intéressés à la méthodes d'Arnoldi symplectique par bloc que nous appelons aussi bloc J-Arnoldi. Notre but essentiel est d’étudier cette méthode de façon théorique et numérique, sur la nouvelle structure du K-module libre ℝ²nx²s avec K = ℝ²sx²s où s ≪ n désigne la taille des blocs utilisés. Un deuxième objectif est de chercher une approximation de l'epérateur exp(A)V, nous étudions en particulier le cas où A est une matrice réelle Hamiltonnienne et anti-symétrique de taille 2n x 2n et V est une matrice rectangulaire ortho-symplectique de taille 2n x 2s sur le sous-espace de Krylov par blocs Km(A,V) = blockspan {V,AV,...,Am-1V}, en conservant la structure de la matrice V. Cette approximation permet de résoudre plusieurs problèmes issus des équations différentielles dépendants d'un paramètre (EDP) et des systèmes d'équations différentielles ordinaires (EDO). Nous présentons également une méthode de Lanczos symplectique par bloc, que nous nommons bloc J-Lanczos. Cette méthode permet de réduire une matrice structurée sous la forme J-tridiagonale par bloc. Nous proposons des algorithmes basés sur deux types de normalisation : la factorisation S R et la factorisation Rj R. Dans une dernière partie, nous proposons un algorithme qui généralise la méthode de Greville afin de déterminer la pseudo inverse de Moore-Penros bloc de lignes par bloc de lignes d'une matrice rectangulaire de manière itérative. Nous proposons un algorithme qui utilise la technique de bloc. Pour toutes ces méthodes, nous proposons des exemples numériques qui montrent l'efficacité de nos approches. / We study, in this thesis, some numerical block Krylov subspace methods. These methods preserve geometric properties of the reduced matrix (Hamiltonian or skew-Hamiltonian or symplectic). Among these methods, we interest on block symplectic Arnoldi, namely block J-Arnoldi algorithm. Our main goal is to study this method, theoretically and numerically, on using ℝ²nx²s as free module on (ℝ²sx²s, +, x) with s ≪ n the size of block. A second aim is to study the approximation of exp (A)V, where A is a real Hamiltonian and skew-symmetric matrix of size 2n x 2n and V a rectangular matrix of size 2n x 2s on block Krylov subspace Km (A, V) = blockspan {V, AV,...Am-1V}, that preserve the structure of the initial matrix. this approximation is required in many applications. For example, this approximation is important for solving systems of ordinary differential equations (ODEs) or time-dependant partial differential equations (PDEs). We also present a block symplectic structure preserving Lanczos method, namely block J-Lanczos algorithm. Our approach is based on a block J-tridiagonalization procedure of a structured matrix. We propose algorithms based on two normalization methods : the SR factorization and the Rj R factorization. In the last part, we proposea generalized algorithm of Greville method for iteratively computing the Moore-Penrose inverse of a rectangular real matrix. our purpose is to give a block version of Greville's method. All methods are completed by many numerical examples.