Les méthodes de décomposition de domaine en espace ont prouvé leur utilité dans le cadre des architectures parallèles. Pour les problèmes d’évolution en temps, il est nécessaire d’introduire une dimension supplémentaire de parallélisme dans la direction du temps. Ceci peut alors être couplé avec des méthodes de type optimisé Schwarz waveform relaxation. Nous nous intéressons dans cette thèse aux méthodes directes de décomposition en temps. Nous en étudions particulièrement deux. Dans une première partie nous étudions la méthode de produit tensoriel, introduite par R. E. Lynch, J. R. Rice, et D. H. Thomas in 1963. Nous proposons une méthode d’optimisation des pas de temps, basée sur une étude d’erreur en variable de Fourier en temps. Nous menons cette étude sur les schémas d’Euler et de Newmark pour la discrétisation en temps de l’équation de la chaleur. Nous présentons ensuite des tests numériques établissant la validité de cette approche. Dans la seconde partie, nous étudions les méthodes dites de Bloc, introduites par Amodio et Brugnano en 1997. Nous comparons diverses implémentations de la méthode, basées sur différentes approximations de l’exponentielle de matrice. Nous traitons l’équation de la chaleur et l’équation des ondes, et montrons par une étude numérique bidimensionnelle la puissance de la méthode. / Domain decomposition methods in space applied to Partial Differential Equations (PDEs) expanded considerably thanks to their effectiveness (memory costs, calculation costs, better local conditioned problems) and this related to the development of massively parallel machines. Domain decomposition in space-time brings an extra dimension to this optimization. In this work, we study two different direct time-parallel methods for the resolution of Partial Differential Equations. The first part of this work is devoted to the Tensor-product space-time method introduced by R.E. Lynch, J. R. Rice, and D. H. Thomas in 1963. We analyze it in depth for Euler and Crank-Nicolson schemes in time applied to the heat equation. The method needs all time steps to be different, while accuracy is optimal when they are all equal (in the Euler case). Furthermore, when they are close to each other, the condition number of the linear problems involved becomes very big. We thus give for each scheme an algorithm to compute optimal time steps, and present numerical evidences of the quality of the method. The second part of this work deals with the numerical implementation of the Block method of Amodio and Brugnano presented in 1997 to solve the heat equation with Euler and Crank- Nicolson time schemes and the elasticity equation with Euler and Gear time schemes. Our implementation shows how the method is accurate and scalable.

Dans cette thèse, nous proposons de nouvelles méthodes permettant de résoudre numériquement des problèmes de diffraction harmoniques et tridimensionnels, aussi bien acoustiques qu'électromagnétiques, pour lesquels l'objet diffractant est pénétrable et inhomogène. La résolution de tels problèmes est centrale pour des calculs de surfaces équivalentes sonar et radar (SES et SER). Elle est toutefois connue pour être difficile car elle requiert de discrétiser des équations aux dérivées partielles posées dans un domaine extérieur. Étant infini, ce domaine ne peut pas être maillé en vue d'une résolution par la méthode des éléments finis volumiques. Deux approches classiques permettent de contourner cette difficulté. La première consiste à tronquer le domaine extérieur et rend alors possible une résolution par la méthode des éléments finis volumiques. Étant donné qu'elles approximent les problèmes de diffraction au niveau continu, les méthodes de troncature de domaine peuvent toutefois manquer de précision pour des calculs de SES et de SER. Les problèmes de diffraction harmoniques, pénétrables et inhomogènes peuvent également être résolus en couplant une formulation variationnelle volumique associée à l'objet diffractant et des équations intégrales surfaciques rattachées au domaine extérieur. Nous parlons de couplages FEM-BEM (Finite Element Method-Boundary Element Method). L'intérêt de cette approche réside dans le fait qu'elle est exacte au niveau continu. Les couplages FEM-BEM classiques sont dits forts car ils couplent la formulation variationnelle volumique et les équations intégrales surfaciques au sein d'une même formulation. Ils ne sont toutefois pas adaptés à la résolution de problèmes à haute fréquence. Pour pallier cette limitation, d'autres couplages FEM-BEM, dits faibles, ont été proposés. Ils correspondent concrètement à des algorithmes de décomposition de domaine itérant entre l'objet diffractant et le domaine extérieur. Dans cette thèse, nous introduisons de nouveaux couplages faibles FEM-BEM acoustiques et électromagnétiques basés sur des approximations de Padé récemment développées pour les opérateurs Dirichlet-to-Neumann et Magnetic-to-Electric. Le nombre d'itérations nécessaires à la résolution de ces couplages ne dépend que faiblement de la fréquence et du raffinement du maillage. Les couplages faibles FEM-BEM que nous proposons sont donc adaptés pour des calculs précis de SES et de SER à haute fréquence / In this doctoral dissertation, we propose new methods for solving acoustic and electromagnetic three-dimensional harmonic scattering problems for which the scatterer is penetrable and inhomogeneous. The resolution of such problems is key in the computation of sonar and radar cross sections (SCS and RCS). However, this task is known to be difficult because it requires discretizing partial differential equations set in an exterior domain. Being unbounded, this domain cannot be meshed thus hindering a volume finite element resolution. There are two standard approaches to overcome this difficulty. The first one consists in truncating the exterior domain and renders possible a volume finite element resolution. Given that they approximate the scattering problems at the continuous level, truncation methods may however not be accurate enough for SCS and RCS computations. Inhomogeneous penetrable harmonic scattering problems can also be solved by coupling a volume variational formulation associated with the scatterer and surface integral equations related to the exterior domain. This approach is known as FEM-BEM coupling (Finite Element Method-Boundary Element Method). It is of great interest because it is exact at the continuous level. Classical FEM-BEM couplings are qualified as strong because they couple the volume variational formulation and the surface integral equations within one unique formulation. They are however not suited for solving high-frequency problems. To remedy this drawback, other FEM-BEM couplings, said to be weak, have been proposed. These couplings are actually domain decomposition algorithms iterating between the scatterer and the exterior domain. In this thesis, we introduce new acoustic and electromagnetic weak FEM-BEM couplings based on recently developed Padé approximations of Dirichlet-to-Neumann and Magnetic-to-Electric operators. The number of iterations required to solve these couplings is only slightly dependent on the frequency and the mesh refinement. The weak FEM-BEM couplings that we propose are therefore suited to accurate SCS and RCS computations at high frequencies

Este trabalho apresenta a aplicação de técnicas de Decomposição de Domínio e Processamento Paralelo na solução de grandes sistemas de equações algébricas lineares provenientes da modelagem de fenômenos eletromagnéticos pelo Método de Elementos Finitos. Foram implementadas as técnicas dos tipos Complemento de Schur e o Método Aditivo de Schwarz, adaptadas para a resolução desses sistemas em cluster de computadores do tipo Beowulf e com troca de mensagens através da Biblioteca MPI. A divisão e balanceamento de carga entre os processadores são feitos pelo pacote METIS. Essa metodologia foi testada acoplada a métodos, seja iterativo (ICCG), seja direto (LU) na etapa de resolução dos sistemas referentes aos nós internos de cada partição. Para a resolução do sistema envolvendo os nós de fronteira, no caso do Complemento de Schur, utilizou-se uma implementação paralisada do Método de Gradientes Conjugados (PCG). S~ao discutidos aspectos relacionados ao desempenho dessas técnicas quando aplicadas em sistemas de grande porte. As técnicas foram testadas na solução de problemas de aplicação do Método de Elementos Finitos na Engenharia Elétrica (Magnetostática, Eletrocinética e Magnetodinâmica), sejam eles de natureza bidimensional com malhas não estruturadas, seja tridimensional, com malhas estruturadas. / This work presents the study of Domain Decomposition and Parallel Processing Techniques applied to the solution of systems of algebraic equations issued from the Finite Element Analysis of Electromagnetic Phenomena. Both Schur Complement and Schwarz Additive techniques were implemented. They were adapted to solve the linear systems in Beowulf clusters with the use of MPI library for message exchange. The load balance among processors is made with the aid of METIS package. The methodology was tested in association to either iterative (ICCG) or direct (LU) methods in order to solve the system related to the inner nodes of each partition. In the case of Schur Complement, the solution of the system related to the boundary nodes was performed with a parallelized Conjugated Gradient Method (PCG). Some aspects of the peformance of these techniques when applied to large scale problems have also been discussed. The techniques has been tested in the simulation of a collection of problems of Electrical Engineering, modelled by the Finite Element Method, both in two dimensions with unstructured meshes (Magnetostatics) and three dimensions with structured meshes (Electrokinetics).

La résolution des équations différentielles (EDP/EDO/EDA) est au cœur de la simulation de phénomènes physiques. L'accroissement de la taille et de la complexité des modèles nécessite la mise en œuvre de méthodes de résolution robustes et performantes en termes de temps de calcul. L'objectif de cette thèse est de proposer des méthodes pour accélérer la résolution des équations différentielles par des méthodes de décomposition de domaine. On considère d'abord les méthodes de décomposition de domaine de Schwarz pour la résolution de grands systèmes linéaires issus de la discrétisation d'EDP. Afin d'accélérer la convergence de la méthode de Schwarz, on propose une approximation de l'opérateur de propagation d'erreur. Cette approximation respectera la structure de l'opérateur exact, ce qui conduira à une réduction très significative des temps de calcul sur le problème des écoulements dans les milieux poreux hétérogènes. La deuxième contribution concerne la résolution de la suite de systèmes linéaires provenant de l'intégration en temps de problèmes non linéaires. On propose deux approches en utilisant le fait que la matrice jacobienne ne varie que peu d'un système à l'autre. Premièrement, on applique la mise à jour de Broyden au préconditionneur RAS (Restricted Additive Schwarz) au lieu de recalculer les factorisations LU. La deuxième approche consiste à dédier des processeurs a la mise à jour partielle et asynchrone du préconditionneur RAS. Des résultats numériques sur le problème de la cavité entrainée et sur un problème de réactiondiffusion montrent qu'une accélération super linéaire peut être obtenue. La dernière contribution a pour objet la résolution simultanée des problèmes non linéaires de pas de temps consécutifs. On étudie le cas où la méthode de Broyden est utilisée pour résoudre ces problèmes non linéaires. Dans ce cas, la mise à jour de Broyden peut être propagée d'un pas de temps à l'autre. La parallélisation à travers les pas de temps est également appliquée a la recherche d'une solution initiale consistante pour les équations différentielles algébriques / Solving differential equations (PDEs/ODEs/DAEs) is central to the simulation of physical phenomena. The increase in size and complexity of the models requires the design of methods that are robust and efficient in terms of computational time. The aim of this thesis is to design methods that accelerate the solution of differential equations by domain decomposition methods. We first consider Schwarz domain decomposition methods to solve large-scale linear systems arising from the discretization of PDEs. In order to accelerate the convergence of the Schwarz method, we propose an approximation of the error propagation operator. This approximation preserves the structure of the exact operator. A significant reduction of computational time is obtained for the groundwater flow problem in highly heterogeneous media. The second contribution concerns solving the sequence of linear systems arising from the time-integration of nonlinear problems. We propose two approaches, taking advantage of the fact that the Jacobian matrix does not change dramatically from one system to another. First, we apply Broyden’s update to the Restricted Additive Schwarz (RAS) preconditioner instead of recomputing the local LU factorizations. The second approach consists of dedicating processors to the asynchronous and partial update of the RAS preconditioner. Numerical results for the lid-driven cavity problem, and for a reaction-diffusion problem show that a super-linear speedup may be achieved. The last contribution concerns the simultaneous solution of nonlinear problems associated to consecutive time steps. We study the case where the Broyden method is used to solve these nonlinear problems. In that case, Broyden’s update of the Jacobian matrix may also be propagated from one time step to another. The parallelization through the time steps is also applied to the problem of finding a consistent initial guess for differential-algebraic equations

Orientador: João Antonio Pereira / Banca: Luiz de Paula do Nascimento / Banca: Mário Francisco Mucheroni / Resumo: Este trabalho apresenta o estudo, a implementação e a aplicação de duas técnicas de identificação de parâmetros modais utilizando apenas as respostas da estrutura, denominadas: Identificação Estocástica de Subespaço (IES) e Decomposição no Domínio da Freqüência (DDF). A IES é baseada na Decomposição em Valores Singulares (DVS) da projeção ortogonal do espaço das linhas das saídas futuras no espaço das linhas das saídas passadas. Uma vez realizada a DVS da projeção ortogonal é possível obter o modelo de espaço de estado da estrutura e os parâmetros modais são estimados diretamente através da decomposição em autovalores e autovetores da matriz dinâmica. A DDF é baseada na DVS da matriz de densidade espectral de potência de saída nas linhas de freqüências correspondentes a região em torno de um modo. O primeiro vetor singular obtido para cada linha de freqüência contém as respectivas informações daquele modo e os correspondentes valores singulares levam a função densidade espectral de um sistema equivalente de um grau de liberdade (1GL), permitindo a obtenção dos parâmetros do respectivo modo. Os métodos são avaliados utilizando dados simulados e experimentais. Os resultados mostram que as técnicas implementadas são capazes de estimar os parâmetros modais de estruturas utilizando apenas as respostas. / Abstract: This work presents the study, implementation and application of the two techniques for the modal parameters identification using only response data: Stochastic Subspace Identification (SSI) and Frequency Domain Decomposition (FDD). The SSI is based on Singular Value Decomposition (SVD) of the orthogonal projection of the future output row space in the past output row space. After the completion of the SVD of the orthogonal projection, is possible to get the state space model of the structure and the modal parameters are estimated directly through the eigenvalues and eigenvectors decomposition of the dynamic matrix. The FDD is based on the SVD of the output power spectral density matrix in the frequencies lines around a mode. The first singular vector obtained for each frequency line contains the respective information about this mode and the corresponding spectral density function leads to an equivalent system of one degree of freedom (1 DOF), allowing the calculation of the parameters of the mode. The methods are evaluated using simulated and experimental data. The results show that the techniques implemented are capable to estimate the modal parameters of structures using only response data. / Mestre

Les équations fondamentales décrivant la dynamique de l'océan sont en théorie les équations de Navier-Stokes sur une sphère en rotation, auxquelles il faut a jouter une équation d'état pour la densité, et des équations de transport-diffusion pour les traceurs. Toutefois, un certain nombre de considérations physiques et de limitations pratiques ont nécessité le développement de modèles plus simples. En effet, un certain nombre d'hypothèses simplificatrices sont pleinement justifiées du point de vue de la physique des mouvements océaniques, dont les principales sont les approximations de couche mince et de Boussinesq. D'autre part, étant donné les dimensions des bassins océaniques (plusieurs centaines à plusieurs milliers de kilomètres), les coûts de calculs sont un facteur pratique extrêmement limitant. On est, à l'heure actuelle, capable de simuler l'océan mondial avec une résolution de l'ordre de dix kilomètres, en utilisant des modèles dits aux équations primitives, dont le coût de calcul est bien inférieur à celui des équations de Navier-Stokes. On est donc bien loin d'une modélisation complète des phénomènes décrits par ces équations, qui nécessiterait en théorie de considérer des échelles de l'ordre du millimètre. Les équations primitives sont issues des équations complètes de la mécanique des fluides en effectuant l'approximation hydrostatique, justifiée par la faible profondeur des domaines considérés au regard de leur dimension horizontale. Dans cette thèse, nous considérerons les équations de Navier-Stokes (NS) qui sont le coeur du modèle complet évoqué ci-dessus, sans prendre en compte les équations de la densité et des traceurs (salinité, température, etc.). Nous utiliserons l'approximation hydrostatique dans le chapitre 10, et le modèle sera naturellement appelé Navier-Stokes hydrostatique (NSH). Il correspond aux équations primitives dans lesquelles on ne prendrait pas en compte la densité et les traceurs. C'est dans ce cadre que se situe le travail présenté dans cette thèse, avec l'objectif à moyen terme de pouvoir coupler de façon rigoureuse et efficace les équations de Navier-Stokes avec les équations primitives. Dans une première partie, on présentera quelques rappels sur les équations de Navier-Stokes, leur discrétisation, ainsi que le cas-test de la cavité entraînée qui sera utilisé dans tout ce document. Dans une deuxième partie, on met en œuvre les méthodes de Schwarz sur les équations de Stokes et Navier-Stokes, en dérivant notamment des conditions absorbantes exactes et approchées pour ces systèmes. Enfin, dans une troisième partie, on proposera des pistes vers le couplage Navier-Stokes/Navier-Stokes hydrostatique décrit ci-dessus. / Fundamental equations describing the ocean dynamic are theoretically Navier-Stokes equations over a rotating sphere, whom need to add a state equation for the fluid density, and advection-diffusion equations for tracers. However, some physical considerations and practical limitations required to developped more simple models. Indeed, some simplifying hypotheses are well justified from a ocean dynamic point of view, whose principal ones are thin layer and Boussinesq approximations. On the other hand, considering the dimensions of oceans (from serveral hundreds to serveral thousands kilometers), computations costs are a very practical limitating factor. We are, by now, able to simulate the global ocean with about ten kilometers large grid mesh. This is very far from a complete modelisation of all phenomenes decribed by the Navier-Stokes equations, which require to consider scales of milimeters order. Primitives equations derive from complete equations describing fluid mecanics, by doing the hydrostatic approximations, which is justified by the low deepness of considered domains with regard to their horizontal dimension. In this thesis, we are considering Navier-Stokes equations (NS) which are the heart of the complete modele mentionned previously, without holding in account density and tracers equations. We will use the hydrostatic approximations, and the resulting equations will be named as hydrostatic Navier-Stokes equations (NSH).The mid term objective is to couple carefully Navier-Stokes equations with primitive equation. In a first part, we will remind few results for Navier-Stokes equations, their discretization, and the lid-driven cavity which wil be used as a test-case. In a second part, we will use Schwarz method with Stokes and Navier-Stokes equations, deriving in particular exact and approched absorbing interface conditions for these systems. Finally, in a third part, we shall propose first results towards coupling Navier-Stokes and hydrostatic Navier-Stokes equations.

CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / Este trabalho descreve uma tÃcnica de decomposiÃÃo de domÃnios bidimensionais para geraÃÃo em paralelo de malhas. Esta tÃcnica funciona tanto para memÃria distribuÃda quanto compartilhada, alÃm de permitir que se utilize qualquer estrutura de dados que gere regiÃes quadrangulares paralelas aos eixos para decompor o domÃnio dado como entrada. Pode se utilizar por exemplo, uma Ãrvore quaternÃria (quadtree) ou uma partiÃÃo binÃria do espaÃo (bsp). AlÃm disso, qualquer processo de geraÃÃo de malha que respeite os prÃ-requisitos estabelecidos pode ser empregado nos subdomÃnios criados, como as tÃcnicas de Delaunay ou AvanÃo de Fronteira, dentre outras. A tÃcnica proposta à dita a priori porque a malha de interface entre os subdomÃnios à gerada antes das suas malhas internas. A estimativa de carga de processamento associada a cada subdomÃnio à feita nesse trabalho com a ajuda de uma quadtree refinada, cujo nÃvel de refinamento orienta a criaÃÃo das arestas que sÃo definidas a partir da discretizaÃÃo das fronteiras das cÃlulas internas. Essa maneira de estimar carga produz resultados que representam, com boa precisÃo, o nÃmero de elementos a serem gerados em cada subdomÃnio. Isso contribui para um bom particionamento do domÃnio, fazendo com que a geraÃÃo de malha em paralelo seja significativamente mais rÃpida do que a geraÃÃo serial. AlÃm disso, a qualidade da malha gerada em paralelo à qualitativamente equivalente Ãquela gerada serialmente, dentro de limites aceitÃveis. / This work describes a technique of two-dimensional domain decomposition for parallel mesh generation. This technique works for both distributed and shared memory and has the freedom to use any data structure that manages rectangular regions parallel to the axes to decompose the domain given as input, such as a quaternary tree (quadtree) or a binary space decomposition (bsp), for example. Any process of mesh generation that respects the prerequisites established can be used in the subdomains created, for instance, Delaunay or Advancing Front, among others. This technique is called a priori because the mesh on the interface of the subdomains is generated prior to the their internal meshes. The load estimation for each sub-domain in this work is performed with the aid of a refined quadtree, whose level of refinement guides the creation of edges that are defined from the bounderies of only inner cells. This way of estimate load produces results that accurately represent the number of elements to be generated in each subdomain. That contributes to a good partitioning of the domain, making the mesh generation in parallel be significantly faster than the serial generation. Furthermore, the quality of the generated mesh in parallel is qualitatively equivalent to that generated serially within acceptable limits.

Este trabalho apresenta a aplicação de técnicas de Decomposição de Domínio e Processamento Paralelo na solução de grandes sistemas de equações algébricas lineares provenientes da modelagem de fenômenos eletromagnéticos pelo Método de Elementos Finitos. Foram implementadas as técnicas dos tipos Complemento de Schur e o Método Aditivo de Schwarz, adaptadas para a resolução desses sistemas em cluster de computadores do tipo Beowulf e com troca de mensagens através da Biblioteca MPI. A divisão e balanceamento de carga entre os processadores são feitos pelo pacote METIS. Essa metodologia foi testada acoplada a métodos, seja iterativo (ICCG), seja direto (LU) na etapa de resolução dos sistemas referentes aos nós internos de cada partição. Para a resolução do sistema envolvendo os nós de fronteira, no caso do Complemento de Schur, utilizou-se uma implementação paralisada do Método de Gradientes Conjugados (PCG). S~ao discutidos aspectos relacionados ao desempenho dessas técnicas quando aplicadas em sistemas de grande porte. As técnicas foram testadas na solução de problemas de aplicação do Método de Elementos Finitos na Engenharia Elétrica (Magnetostática, Eletrocinética e Magnetodinâmica), sejam eles de natureza bidimensional com malhas não estruturadas, seja tridimensional, com malhas estruturadas. / This work presents the study of Domain Decomposition and Parallel Processing Techniques applied to the solution of systems of algebraic equations issued from the Finite Element Analysis of Electromagnetic Phenomena. Both Schur Complement and Schwarz Additive techniques were implemented. They were adapted to solve the linear systems in Beowulf clusters with the use of MPI library for message exchange. The load balance among processors is made with the aid of METIS package. The methodology was tested in association to either iterative (ICCG) or direct (LU) methods in order to solve the system related to the inner nodes of each partition. In the case of Schur Complement, the solution of the system related to the boundary nodes was performed with a parallelized Conjugated Gradient Method (PCG). Some aspects of the peformance of these techniques when applied to large scale problems have also been discussed. The techniques has been tested in the simulation of a collection of problems of Electrical Engineering, modelled by the Finite Element Method, both in two dimensions with unstructured meshes (Magnetostatics) and three dimensions with structured meshes (Electrokinetics).

The conventional Verlet table neighbor list algorithm is improved to reduce the number of unnecessary inter-atomic distance calculations in molecular simulations involving large amount of atoms. Both of the serial and parallelized performance of molecular dynamics simulation are evaluated using the new algorithm and compared with those using the conventional Verlet table and cell-linked list algorithm. Results show that the new algorithm significantly improved the performance of molecular dynamics simulation compared with conventional neighbor list maintaining and utilizing algorithms in serial programs as well as parallelized programs. / Singapore-MIT Alliance (SMA)

In flexible fitting, the high-resolution crystal structure of a molecule is deformed to optimize its position with respect to a low-resolution density map. Solving the flexible fitting problem entails answering the following questions: (A) How can the crystal structure be deformed? (B) How can the term "optimum" be defined? and (C) How can the optimization problem be solved? In this dissertation, we answer the above questions in reverse order. (C) We develop PFCorr, a non-uniform SO(3)-Fourier-based tool to efficiently conduct rigid-body correlations over arbitrary subsets of the space of rigid-body motions. (B) We develop PF2Fit, a rigid-body fitting tool that provides several useful definitions of the optimal fit between the crystal structure and the density map while using PFCorr to search over the space of rigid-body motions (A) We develop PF3Fit, a flexible fitting tool that deforms the crystal structure with a hierarchical domain-based flexibility model while using PF2Fit to optimize the fit with the density map. Our contributions help us solve the rigid-body and flexible fitting problems in unique and advantageous ways. They also allow us to develop a generalized framework that extends, breadth-wise, to other problems in computational structural biology, including rigid-body and flexible docking, and depth-wise, to the question of interpreting the motions inherent to the crystal structure. Publicly-available implementations of each of the above tools additionally provide a window into the technically diverse fields of applied mathematics, structural biology, and 3D image processing, fields that we attempt, in this dissertation, to span. / text