No desenvolvimento de códigos paralelos, a biblioteca PETSc se destaca como uma ferramenta prática e útil. Com o uso desta ferramenta, este trabalho apresenta um estudo sobre resolvedores de sistemas lineares aplicados a escoamentos incompressíveis de fluidos em microescala, além de uma análise de seu comportamento em paralelo. Após um estudo dos diversos aspectos dos métodos de fronteira imersa, é apresentado um método de fronteira imersa paralelo de primeira ordem. Na sequência, é apresentada uma proposta de melhoria na precisão do método, baseada na minimização da distância entre a condição de contorno exata e aproximada, no sentido de mínimos quadrados. O desenvolvimento de uma ferramenta paralela eficiente é demonstrado na solução numérica de problemas envolvendo escoamentos incompressíveis de fluidos viscosos com fronteiras imersas / In the development of parallel codes, PETSc library has an important position as a practical and useful tool. With this tool, this work presents a study about linear system solvers applied to incompressible flow in microscale problems, furthermore an analysis of the parallel behavior of these methods is presented. After a study of several aspects of immersed boundary methods, and taking advantage of the flexibility of PETSc, a parallel first order immersed boundary method is presented. Thereafter, an improvement in the accuracy of the method is presented, based on the minimization of the distance between exact and approximated boundary conditions, in the least square sense. The development of a parallel and efficient tool is demonstrated in the numerical solution of incompressible viscous flow problems with immersed boundary

Neste trabalho, apresenta-se uma adaptação dos procedimentos utilizados nos códigos computacionais seqüenciais advindos do MEF, para utilizá-los em multicomputadores. Desenvolve-se uma rotina para a montagem do sistema linear particionado entre os diversos processadores. Resolve-se o sistema de equações lineares geradas mediante a rotina do PIM (Parallel Iterative Method). São feitas adaptações deste pacote para se aproveitar as características comuns do sistema linear gerado pelo MEF: esparsidade e simetria. A técnica de resolução do sistema em paralelo é otimizada com o uso de dois tipos de pré-condicionadores: a decomposição incompleta de Cholesky (IC) generalizado e o POLY(0) ou Jacobi. É feita uma aplicação para a solução de pavimento com o algoritmo-base totalmente paralelizado. Também é avaliada a solução do sistema de equações de uma treliça. Mostram-se resultados de speed-up, de eficiência e de tempo para estes dois modelos estruturais. Além disso, é feito um estudo em processamento seqüencial da performance dos pré-condicionadores genéricos (IC) e do advindo de uma série truncada de Neumann, também generalizada, utilizando-se modelos estruturais de placa e chapa. / This work presents an adaptation of conventional finite element method (FEM) computing procedures to multicomputers. It is presented the procedure which the linear system of equations is split among the processor and its solution. It was improved a public software called PIM (Parallel Iterative Method) is used to solve this system of equations. These improvements explore efficiently the usual features of the FEM systems of equations: sparseness and symmetry. To improve the solution of the system, two different preconditioners are used: a generic Incomplete Cholesky (IC) and the Polynomial preconditioning (POLY(0) or Jacobi). It is carried out a full adaptation of the method to parallel computing with a program developed to analyse floor structures. The improved PIM is also used to solve the system of equations of a tri-dimensional truss. It is presented the speed-up, the efficiency and the time used in the resolution of the systems of equations for the floor and for the truss. It is also presented a study of performance in sequential processing of the generic (IC) and the generic Neumann series preconditioners in the analysis of plates in bending and in plane actions.

No desenvolvimento de códigos paralelos, a biblioteca PETSc se destaca como uma ferramenta prática e útil. Com o uso desta ferramenta, este trabalho apresenta um estudo sobre resolvedores de sistemas lineares aplicados a escoamentos incompressíveis de fluidos em microescala, além de uma análise de seu comportamento em paralelo. Após um estudo dos diversos aspectos dos métodos de fronteira imersa, é apresentado um método de fronteira imersa paralelo de primeira ordem. Na sequência, é apresentada uma proposta de melhoria na precisão do método, baseada na minimização da distância entre a condição de contorno exata e aproximada, no sentido de mínimos quadrados. O desenvolvimento de uma ferramenta paralela eficiente é demonstrado na solução numérica de problemas envolvendo escoamentos incompressíveis de fluidos viscosos com fronteiras imersas / In the development of parallel codes, PETSc library has an important position as a practical and useful tool. With this tool, this work presents a study about linear system solvers applied to incompressible flow in microscale problems, furthermore an analysis of the parallel behavior of these methods is presented. After a study of several aspects of immersed boundary methods, and taking advantage of the flexibility of PETSc, a parallel first order immersed boundary method is presented. Thereafter, an improvement in the accuracy of the method is presented, based on the minimization of the distance between exact and approximated boundary conditions, in the least square sense. The development of a parallel and efficient tool is demonstrated in the numerical solution of incompressible viscous flow problems with immersed boundary

Neste trabalho, apresenta-se uma adaptação dos procedimentos utilizados nos códigos computacionais seqüenciais advindos do MEF, para utilizá-los em multicomputadores. Desenvolve-se uma rotina para a montagem do sistema linear particionado entre os diversos processadores. Resolve-se o sistema de equações lineares geradas mediante a rotina do PIM (Parallel Iterative Method). São feitas adaptações deste pacote para se aproveitar as características comuns do sistema linear gerado pelo MEF: esparsidade e simetria. A técnica de resolução do sistema em paralelo é otimizada com o uso de dois tipos de pré-condicionadores: a decomposição incompleta de Cholesky (IC) generalizado e o POLY(0) ou Jacobi. É feita uma aplicação para a solução de pavimento com o algoritmo-base totalmente paralelizado. Também é avaliada a solução do sistema de equações de uma treliça. Mostram-se resultados de speed-up, de eficiência e de tempo para estes dois modelos estruturais. Além disso, é feito um estudo em processamento seqüencial da performance dos pré-condicionadores genéricos (IC) e do advindo de uma série truncada de Neumann, também generalizada, utilizando-se modelos estruturais de placa e chapa. / This work presents an adaptation of conventional finite element method (FEM) computing procedures to multicomputers. It is presented the procedure which the linear system of equations is split among the processor and its solution. It was improved a public software called PIM (Parallel Iterative Method) is used to solve this system of equations. These improvements explore efficiently the usual features of the FEM systems of equations: sparseness and symmetry. To improve the solution of the system, two different preconditioners are used: a generic Incomplete Cholesky (IC) and the Polynomial preconditioning (POLY(0) or Jacobi). It is carried out a full adaptation of the method to parallel computing with a program developed to analyse floor structures. The improved PIM is also used to solve the system of equations of a tri-dimensional truss. It is presented the speed-up, the efficiency and the time used in the resolution of the systems of equations for the floor and for the truss. It is also presented a study of performance in sequential processing of the generic (IC) and the generic Neumann series preconditioners in the analysis of plates in bending and in plane actions.

Orientadores: Christiano Lyra Filho, Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-27T01:38:37Z (GMT). No. of bitstreams: 1 Casacio_Luciana_D.pdf: 3240577 bytes, checksum: f49bb4444bbbfacf0559d3b88d8feee5 (MD5) Previous issue date: 2015 / Resumo: A solução de problemas de otimização linear através de métodos de pontos interiores envolve a solução de sistemas lineares. Esses sistemas quase sempre possuem dimensões elevadas e alto grau de esparsidade em aplicações reais. Para solução, tipicamente são realizadas operações algébricas que os reduzem a duas formulações mais simples: uma delas, conhecida por "sistema aumentado", envolve matrizes simétricas indefinidas e geralmente esparsas; a outra, denominada "sistema de equações normais", usa matrizes de menor dimensão, simétricas e definidas positivas. A solução dos sistemas lineares é a fase que requer a maior parte do tempo de processamento dos métodos de pontos interiores. Consequentemente, a escolha dos métodos de solução é de extrema importância para que se tenha uma implementação eficiente. Normalmente, aplicam-se métodos diretos para a solução como, por exemplo, a fatoração de Bunch-Parllett ou a fatoração de Cholesky. No entanto, em problemas de grande porte, o uso de métodos diretos torna-se desaconselhável, por limitações de tempo e memória. Nesses casos, abordagens iterativas se tornam mais atraentes. O sucesso da implementação de métodos iterativos depende do uso de bons precondicionadores, pois a matriz de coeficientes torna-se muito mal condicionada, principalmente próximo da solução ótima. Uma alternativa para tratar o problema de mal condicionamento é o uso de abordagens híbridas com duas fases: a fase I utiliza um precondicionador para o sistema de equações normais construído com informações de fatorações incompletas, denominado fatoração controlada de Cholesky; a fase II, utilizada nas últimas iterações, adota o precondicionador separador desenvolvido especificamente para sistemas mal condicionados. O trabalho propõe um novo critério de ordenamento das colunas para construção do precondicionador separador, que preserva a estrutura esparsa da matriz de coeficientes original. Os resultados teóricos desenvolvidos mostram que a matriz precondicionada tem o número de condição limitado quando o ordenamento proposto é adotado. Experimentos computacionais realizados com todos os problemas da biblioteca NETLIB mostram que a abordagem é competitiva com métodos diretos e que o número de condição da matriz precondicionada é muito menor do que o da matriz original. Foram também realizadas comparações com a abordagem híbrida anterior, baseada em precondicionadores que reduzem a esparsidade do sistema de equações. Esses experimentos confirmaram o bom desempenho da metodologia em relação ao número de iterações dos métodos de pontos interiores, aos tempos computacionais e à qualidade das soluções. Esses benefícios foram obtidos com a preservação da esparsidade dos sistemas de equações, o que destaca a adequação da abordagem proposta para a solução de problemas de grande porte / Abstract: The solution of linear optimization problems through interior point methods involves the solution of linear systems. These systems often have high dimensions and high sparsity degree, specially in real applications. Typically algebraic operations are performed to reduce the systems in two simpler formulations: one of them is known as the augmented system, and the other one, referred as normal equation systems, has a smaller dimension matrix which is symmetric positive definite. The solution of linear systems is the interior point methods step that requires most of the processing time. Consequently, the choice of the solution methods are extremely important in order to have an efficient implementation. Usually, direct methods are applied for solving these systems as, for example, Bunch-Parllett factorization or Cholesky factorization. However, in large scale problems, the use of direct methods becomes discouraging by limitations of time and memory. In such cases, iterative approaches are more attractive. The success of iterative method approaches depends on good preconditioners once the coefficient matrix becomes very ill-conditioned, especially close to an optimal solution. An alternative to treat the problem of ill conditioning is to use hybrid approaches with two phases: phase I uses a preconditioner for the normal equation systems built with incomplete factorizations information, called controlled Cholesky factorization; phase II, used in the final iterations, adopts the splitting preconditioner, which was developed specifically for such ill conditioned systems. This work proposes a new ordering criterion for the columns of the splitting preconditioner that preserves the sparse structure of the original coefficient matrix. Theoretical results show that the preconditioned matrix has a limited condition number when the proposed idea is adopted. Computational experiments performed with all NETLIB problems show that the approach is competitive with direct methods and the condition number of the preconditioned matrix is much smaller than the original matrix. Comparisons are also performed with the previous hybrid approach. These experiments confirm the good performance of the methodology. The final number of iterations, processing time and quality of solutions of interior point methods are suitable. These benefits are obtained preserving the sparse structure of the systems, which highlights the suitability of the proposed approach for large scale problems / Doutorado / Automação / Doutora em Engenharia Elétrica

[pt] O desenvolvimento e/ou a adaptação de métodos numéricos para aplicação em análises computacionais de estabilidade de sistemas elétricos no domínio do tempo costumam despertar interesse em função das dificuldades de solução das equações diferenciais e algébricas (EDAs) que representam a rede e seus componentes. Condições de operações muito carregadas e compensadas dificultam a solução, devido, p.ex., ao mau condicionamento da matriz Jacobiana, instabilidade numérica e singularidade. Uma dessas dificuldades pode surgir durante a solução de equações não lineares, especificamente no problema linear do tipo Ax = b. Para contornar estas e outras dificuldades, a presente tese procurou contribuir no aspecto numérico do problema destacando a aplicação do método iterativo Resíduo Mínimo Generalizado - GMRES na solução do problema. Optou-se por trabalhar na qualidade do pré-condicionador construído com base na matriz Jacobiana calculada no início do processo de solução. Verificou-se que, se esta matriz estiver bem condicionada, a qualidade do pré-condicionador resultante dela é boa para o GMRES atingir a convergência em poucas iterações. Comprovou-se através de experimentos numéricos com diferentes sistemas-teste e diferentes condições de operação, que o condicionamento da matriz Jacobiana é melhorado se escalonada, normalizada e reordenada antes da construção do pré-condicionador, resultando, de fato, num pré-condicionador de boa qualidade, agindo positivamente no desempenho do GMRES e consequentemente no processo global de solução. / [en] The development and/or adaptation of numerical methods when applied to power systems stability computer simulations in time domain are of interest due to the difficulties related to the solution of the algebraic differential equations (ADEs) which represent the network and its components. The solution of networks operating under heavy load conditions and extremely compensated is difficult due to the ill-conditioning of the Jacobian matrix, numerical instability and singularity. It can happen, for instance, when solving linear problems of type Ax = b. In order to overcome this and other difficulties, this thesis aims to contribute in the numerical aspect of the problem applying the Generalized Minimal Residual method – GMRES to solve the problem. The idea is to work over the preconditioner quality constructed based on the Jacobian matrix. It is shown that, if this matrix is well conditioned, the quality of the resulting preconditioner is good enough to the GMRES reaches convergence in few iterations. It is seen through numerical experiments using different test-systems and different operating conditions as well, that the Jacobian matrix conditioning is improved if scaled, normalized and reordered before the preconditioner construction, resulting, in fact, in a high quality preconditioner, improving the GMRES performance.

Este trabalho propõe uma nova abordagem, baseada em wavelets, para o método Multigrid Algébrico (WAMG). Nesta nova abordagem, a Transformada Discreta Wavelet é aplicada na matriz de coeficientes do sistema linear gerando uma aproximação dessa matriz em cada nível do processo de multiresolução. As vantagens da nova abordagem, que incluem maior facilidade de paralelização e menor tempo de montagem, são apresentadas com detalhes e uma análise quantitativa de convergência do método WAMG é realizada a partir da sua aplicação em problemas testes. O WAMG também é testado como pré- condicionador para métodos iterativos no subespaço de Krylov na análise magnetostática e magnetodinâmica (regime permanente senoidal) pelo Método dos Elementos Finitos, e em matrizes esparsas extraidas das coleções Matrix Market e da Universidade da Flórida. São apresentados resultados numéricos comparando o WAMG com o Multigrid Algébrico tradicional e com os pré-condicionadores baseados em decomposições incompletas de Cholesky e LU. / In this work we propose a wavelet-based algebraic multigrid method (WAMG) as a linear system solver as well as a prediconditioner for Krylov subspace methods. It is a new approach for the Algebraic Multigrid method (AMG), which considers the use of Discrete Wavelet Transform (DWT) in the construction of a hierarchy of matrices. The two-dimensional DWT is applied to produce an approximation of the matrix in each level of the wavelets multiresolution decomposition process. The main advantages of this new approach are presented and a quantitative analysis of its convergence is shown after its application in some test problems. The WAMG also is tested as a preconditioner for Krylov subspace methods in problems with sparse matrices, in nonlinear magnetic field problems and in 3D time-harmonic Electromagnetic Edge-based Finite Element Analysis. Numerical results are presented comparing the WAMG with the standard Algebraic Multigrid method and with the preconditioners based on the incomplete Cholesky and LU decompositions.

Este trabalho propõe uma nova abordagem, baseada em wavelets, para o método Multigrid Algébrico (WAMG). Nesta nova abordagem, a Transformada Discreta Wavelet é aplicada na matriz de coeficientes do sistema linear gerando uma aproximação dessa matriz em cada nível do processo de multiresolução. As vantagens da nova abordagem, que incluem maior facilidade de paralelização e menor tempo de montagem, são apresentadas com detalhes e uma análise quantitativa de convergência do método WAMG é realizada a partir da sua aplicação em problemas testes. O WAMG também é testado como pré- condicionador para métodos iterativos no subespaço de Krylov na análise magnetostática e magnetodinâmica (regime permanente senoidal) pelo Método dos Elementos Finitos, e em matrizes esparsas extraidas das coleções Matrix Market e da Universidade da Flórida. São apresentados resultados numéricos comparando o WAMG com o Multigrid Algébrico tradicional e com os pré-condicionadores baseados em decomposições incompletas de Cholesky e LU. / In this work we propose a wavelet-based algebraic multigrid method (WAMG) as a linear system solver as well as a prediconditioner for Krylov subspace methods. It is a new approach for the Algebraic Multigrid method (AMG), which considers the use of Discrete Wavelet Transform (DWT) in the construction of a hierarchy of matrices. The two-dimensional DWT is applied to produce an approximation of the matrix in each level of the wavelets multiresolution decomposition process. The main advantages of this new approach are presented and a quantitative analysis of its convergence is shown after its application in some test problems. The WAMG also is tested as a preconditioner for Krylov subspace methods in problems with sparse matrices, in nonlinear magnetic field problems and in 3D time-harmonic Electromagnetic Edge-based Finite Element Analysis. Numerical results are presented comparing the WAMG with the standard Algebraic Multigrid method and with the preconditioners based on the incomplete Cholesky and LU decompositions.

Au cours des dernières décennies, des progrès remarquables ont été réalisés au niveau de la simulation d’écoulements sanguins dans des modèles anatomiques réalistes construits à partir de données d'imagerie médicale 3D en vue de simulation hémodynamique et physiologique 3D à grande échelle. Alors que les modèles anatomiques précis sont d'une importance primordiale pour simuler le flux sanguin, des conditions aux limites réalistes sont également importantes surtout lorsqu’il s’agit de calculer des champs de vitesse et de pression. La première cible de cette thèse était d'étudier l'analyse de convergence des inconnus pour différents types de conditions aux limites permettant un cadre flexible par rapport au type de données d'entrée (vitesse, pression, débit, ...). Afin de faire face au grand coût informatique associé, nécessitant un calcul haute performance, nous nous sommes intéressés à comparer les performances de deux préconditionneurs par blocs; le preconditionneur LSC (Least-Squared Commutator et le preconditionneur PCD (Pressure Convection Diffusion). Dans le cadre de cette thèse, nous avons implémenté ce dernier dans la bibliothèque Feel++. Dans le but de traiter l'interaction fluide-structure, nous nous sommes focalisés sur l'approximation de la force exercée par le fluide sur la structure, un champ essentiel intervenant dans la condition de continuité pour assurer le couplage du modèle de fluide avec le modèle de structure. Enfin, afin de valider nos choix numériques, deux cas tests ont été réalisés et une comparaison avec les données expérimentales et numériques a été établie et validée (le benchmark FDA et le benchmark Phantom). / Towards a large scale 3D computational model of physiological hemodynamics, remarkable progress has been made in simulating blood flow in realistic anatomical models constructed from three-dimensional medical imaging data in the past few decades. When accurate anatomic models are of primary importance in simulating blood flow, realistic boundary conditions are equally important in computing velocity and pressure fields. Thus, the first target of this thesis was to investigate the convergence analysis of the unknown fields for various types of boundary conditions allowing for a flexible framework with respect to the type of input data (velocity, pressure, flow rate, ...). In order to deal with the associated large computational cost, requiring high performance computing, we were interested in comparing the performance of two block preconditioners; the least-squared commutator preconditioner and the pressure convection diffusion preconditioner. We implemented the latter, in the context of this thesis, in the Feel++ library. With the purpose of handling the fluid-structure interaction, we focused of the approximation of the force exerted by the fluid on the structure, a field that is essential while setting the continuity condition to ensure the coupling of the fluid model with the structure model. Finally, in order to assess our numerical choices, two benchmarks (the FDA benchmark and the Phantom benchmark) were carried out, and a comparison with respect to experimental and numerical data was established and validated.

[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.