Técnicas baseadas na Equação de Fluxo Bem-Balanceada têm sido muitas vezes empregadas como eficientes ferramentas para eliminação de ruídos e preservação de arestas em imagens digitais. Embora efetivas, essas técnicas demandam alto custo computacional. Este trabalho objetiva propor uma técnica baseada na abordagem multigrid para acelerar a solução numérica da Equação de Fluxo Bem-Balanceada. A equação de difusão é resolvida em uma malha grossa e uma correção do erro na malha grossa para as mais finas é aplicada para gerar a solução desejada. A transferência entre malhas grossas e finas é feita pelo filtro de Mitchell, um esquema bem conhecido que é projetado para preservação de arestas. Além disso, a equação do transporte e a Equação do Fluxo de Curvatura são adaptadas à nossa técnica para retoque em imagens e eliminação de ruí?dos. Resultados numéricos são comparados quantitativamente e qualitativamente com outras abordagens, mostrando que o método aqui introduzido produz qualidade de imagens similares com muito menos tempo computacional. / Techniques based on the Well-Balanced Flow Equation have been employed as an efficient tool for edge preserving noise removal. Although effective, this technique demands high computational effort, rendering it not practical in several applications. This work aims at proposing a multigrid-like technique for speeding up the solution of the Well- Balanced Flow equation. In fact, the diffusion equation is solved in a coarse grid and a coarse-to-fine error correction is applied in order to generate the desired solution. The transfer between coarser and finer grids is made by the Mitchell-Filter, a well known interpolation scheme that is designed for preserving edges. Furthermore, the solution of the transport and the Mean Curvature Flow equations is adapted to the multigrid like technique for image inpainting and denoising. Numerical results are compared quantitative and qualitatively with other approaches, showing that our method produces similar image quality with much lower computational time.

Depuis ces trente dernières années, les systèmes d'observation de la Terre et les modèles numériques se sont perfectionnés et complexifiés pour nous fournir toujours plus de données, réelles et numériques. Ces données, de nature très diverse, forment maintenant un ensemble conséquent d'informations précises mais hétérogènes sur les structures et la dynamique des fluides géophysiques. Dans les années 1980, des méthodes d'optimisation, capables de combiner les informations entre elles, ont permis d'estimer les paramètres des modèles numériques et d'obtenir une meilleure prévision des courants marins et atmosphériques. Ces méthodes puissantes, appelées assimilation variationnelle de données, peinent à tirer profit de la toujours plus grande complexité des informations de par le manque de puissance de calcul disponible. L'approche, que nous développons, s'intéresse à l'utilisation des méthodes multigrilles, jusque là réservées à la résolution de systèmes d'équations différentielles, pour résoudre l'assimilation haute résolution de données. Les méthodes multigrilles sont des méthodes de résolution itératives, améliorées par des corrections calculées sur des grilles de plus basses résolutions. Nous commençons par étudier dans le cas d'un modèle linéaire la robustesse de l'approche multigrille et en particulier l'effet de la correction par grille grossière. Nous dérivons ensuite les algorithmes multigrilles dans le cadre non linéaire. Les deux types d'algorithmes étudiés reposent d'une part sur la méthode de Gauss Newton multigrille et d'autre part sur une méthode sans linéarisation globale : le Full Approximation Scheme (FAS). Ceux-ci sont appliqués au problème de l'assimilation variationnelle de données dans le cadre d'une équation de Burgers 1D puis d'un modèle Shallow-water 2D. Leur comportement est analysé et comparé aux méthodes plus traditionnelles de type incrémentale ou multi-incrémentale. / For these last thirty years, earth observation and numerical models improved greatly and provide now a huge amount of accurate, yet heterogeneous, information on geophysics fluids dynamics and structures. Optimization methods from the eighties called variational data assimilation are capable of merging information from different sources. They have been used to estimate the parameters of numerical models and better forecast oceanic and atmospheric flows. Unfortunately, these powerful methods have trouble making benefit of always more complex information, suffering from the lack of available powerful calculators. The approach developed here, focuses on the use of multigrid methods, that are commonly used in the context of differential equations systems, to solve high resolution data assimilation. Multigrid methods are iterative methods improved by the use of feedback corrections evaluated on coarse resolution. First in the case of linear assimilation, we study the robustness of multigrid approach and the efficiency of the coarse grid correction step. We then apply the multigrid algorithms on a non linear 1-D Burgers equation and on a 2-D Shallow-Water model. We study two types of algorithms, the Gauss Newton Multigrid, which lays on global linearization, and the Full Approximation Scheme. Their behavior is compared to more traditional approaches as incremental and multi-incremental ones.

Orientador: Eduardo Cardoso de Abreu / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-26T22:28:13Z (GMT). No. of bitstreams: 1 Ferraz_PaolaCunha_M.pdf: 6535346 bytes, checksum: 5f9c9ba53cd3e63fc60c09c90ad2c625 (MD5) Previous issue date: 2015 / Resumo: O foco deste trabalho é aproximação numérica de problemas envolvendo equações diferenciais parciais (EDPs), de natureza elíptica, no contexto de aplicações em dinâmica de fluidos em meios porosos. Especificamente, a dissertação pretende contribuir com uma implementação de um algoritmo multiescala e multigrid, recentemente introduzido na literatura, para resolução aproximada de sistemas de equações lineares de grande porte e mal condicionados, proveniente dessa classe de EDPs, tipicamente associada a problemas de Poisson de pressão-velocidade com condições de contornos típicas de fluxo em meios porosos. O problema concreto de Poisson discutido neste trabalho será desacoplado do sistema de transporte de EDPs de convecção-difusão, com convecção dominante, e linearizado por meio do emprego de uma técnica de decomposição de operadores. A metodologia para a discretização do problema elíptico de Poisson é elementos finitos mistos híbridos. A resolução numérica do sistema linear resultante deste procedimento será realizado via um método do tipo Gradientes Conjugados com Pré-condicionamento (PCG) multiescala e multigrid. Combinamos as metodologias multi-escala e multigrid de modo a capturar os distintos comprimentos de onda associados aos diferentes comprimentos de onda do operador diferencial auto-adjunto de Poisson, fortemente influenciado pela heterogeneidade das propriedades geológicas do meio poroso, em particular da permeabilidade absoluta, que pode exibir flutuações em várias ordens de grandeza. Experimentos computacionais em aplicações de problemas de dinâmica de fluidos em meios porosos são apresentados e discutidos para verificação dos resultados obtidos / Abstract: The focus of this work is the numerical approximation of differential problems involving partial differential equations (PDE's) of elliptic nature, in the context of modelling and simulation in fluid dynamics in porous media. The dissertation aims to contribute with an implementation of a multiscale multigrid algorithm, recently introduced in the literature, designed for solving ill-conditioned large linear systems of equations derived from those classes of PDE's, typically associated with Poisson problems of pressure-velocity with boundary conditions typical of flow in porous media. The Poisson problem discussed here is identified from the coupled convection-diffusion transport system counterpart of PDE's, with dominated convection, and by a linearization by means the use of an operator splitting approach. The methodology used for the discretization of the Poisson elliptic problem is by mixed hybrid finite elements. The numerical solution of the resulting linear system will be addressed by a multiscale multigrid preconditioned conjugate gradient (PCG) method. We combine both methodologies in order to capture the distinct wavelengths associated with the different wavelengths from the assosiated self-adjoint Poisson operator, strongly influenced by the heterogeneity of the geological properties of the porous media, in particular to the absolute permeability tensor, which in turn might exhibit very large fluctuations of orders of magnitude. Numerical experiments in applications of fluid dynamics problems in porous media are presented and discussed for a verification of the results obtained by direct numerical simulations with the multiscale multigrid algorithm under consideration / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Técnicas baseadas na Equação de Fluxo Bem-Balanceada têm sido muitas vezes empregadas como eficientes ferramentas para eliminação de ruídos e preservação de arestas em imagens digitais. Embora efetivas, essas técnicas demandam alto custo computacional. Este trabalho objetiva propor uma técnica baseada na abordagem multigrid para acelerar a solução numérica da Equação de Fluxo Bem-Balanceada. A equação de difusão é resolvida em uma malha grossa e uma correção do erro na malha grossa para as mais finas é aplicada para gerar a solução desejada. A transferência entre malhas grossas e finas é feita pelo filtro de Mitchell, um esquema bem conhecido que é projetado para preservação de arestas. Além disso, a equação do transporte e a Equação do Fluxo de Curvatura são adaptadas à nossa técnica para retoque em imagens e eliminação de ruí?dos. Resultados numéricos são comparados quantitativamente e qualitativamente com outras abordagens, mostrando que o método aqui introduzido produz qualidade de imagens similares com muito menos tempo computacional. / Techniques based on the Well-Balanced Flow Equation have been employed as an efficient tool for edge preserving noise removal. Although effective, this technique demands high computational effort, rendering it not practical in several applications. This work aims at proposing a multigrid-like technique for speeding up the solution of the Well- Balanced Flow equation. In fact, the diffusion equation is solved in a coarse grid and a coarse-to-fine error correction is applied in order to generate the desired solution. The transfer between coarser and finer grids is made by the Mitchell-Filter, a well known interpolation scheme that is designed for preserving edges. Furthermore, the solution of the transport and the Mean Curvature Flow equations is adapted to the multigrid like technique for image inpainting and denoising. Numerical results are compared quantitative and qualitatively with other approaches, showing that our method produces similar image quality with much lower computational time.

An adaptive mesh redistribution method for efficient and accurate simulation of multi dimensional hyperbolic conservation laws is developed. The algorithm consists of two coupled steps; evolution of the governing PDE followed by a redistribution of the computational nodes. The second step, i.e. mesh redistribution is carried out at each time step iteratively with the primary aim of adapting the grid to the computed solution in order to maximize accuracy while minimizing the computational overheads. The governing hyperbolic conservation laws, originally defined on the physical domain, are transformed on to a simplified computational domain where the position of the nodes remains independent of time. The transformed governing hyperbolic equations are recast in a strong conservative form and are solved directly on the computational domain without the need for interpolation that is typically associated with standard mesh redistribution algorithms. Several standard test cases involving numerical solution of scalar and system of hyperbolic conservation laws in one and two dimensions are presented in order to demonstrate the accuracy and computational efficiency of the proposed technique.

This thesis treats two essentially different subjects: V-cycle schemes are considered in Chapters 2-4, whereas the aggregation-based coarsening is analysed in Chapters 5-6. As a matter of paradox, these two multigrid ingredients, when combined together, can hardly lead to an optimal algorithm. Indeed, a V-cycle needs more accurate prolongations than the simple piecewise-constant one, associated to aggregation-based coarsening. On the other hand, aggregation-based approaches use almost exclusively piecewise constant prolongations, and therefore need more involved cycling strategies, K-cycle <a href=http://www3.interscience.wiley.com/journal/114286660/abstract?CRETRY=1&SRETRY=0>[Num.Lin.Alg.Appl. vol.15(2008), pp.473-487]</a> being an attractive alternative in this respect.<p><br><p><br><p>Chapter 2 considers more precisely the well-known V-cycle convergence theories: the approximation property based analyses by Hackbusch (see [Multi-Grid Methods and Applications, 1985, pp.164-167]) and by McCormick [SIAM J.Numer.Anal. vol.22(1985), pp.634-643] and the successive subspace correction theory, as presented in [SIAM Review, vol.34(1992), pp.581-613] by Xu and in [Acta Numerica, vol.2(1993), pp.285-326.] by Yserentant. Under the constraint that the resulting upper bound on the convergence rate must be expressed with respect to parameters involving two successive levels at a time, these theories are compared. Unlike [Acta Numerica, vol.2(1993), pp.285-326.], where the comparison is performed on the basis of underlying assumptions in a particular PDE context, we compare directly the upper bounds. We show that these analyses are equivalent from the qualitative point of view. From the quantitative point of view,<p>we show that the bound due to McCormick is always the best one.<p><br><p><br><p>When the upper bound on the V-cycle convergence factor involves only two successive levels at a time, it can further be compared with the two-level convergence factor. Such comparison is performed in Chapter 3, showing that a nice two-grid convergence (at every level) leads to an optimal McCormick's bound (the best bound from the previous chapter) if and only if a norm of a given projector is bounded on every level.<p><br><p><br><p>In Chapter 4 we consider the Fourier analysis setting for scalar PDEs and extend the comparison between two-grid and V-cycle multigrid methods to the smoothing factor. In particular, a two-sided bound involving the smoothing factor is obtained that defines an interval containing both the two-grid and V-cycle convergence rates. This interval is narrow when an additional parameter α is small enough, this latter being a simple function of Fourier components.<p><br><p><br><p>Chapter 5 provides a theoretical framework for coarsening by aggregation. An upper bound is presented that relates the two-grid convergence factor with local quantities, each being related to a particular aggregate. The bound is shown to be asymptotically sharp for a large class of elliptic boundary value problems, including problems with anisotropic and discontinuous coefficients.<p><br><p><br><p>In Chapter 6 we consider problems resulting from the discretization with edge finite elements of 3D curl-curl equation. The variables in such discretization are associated with edges. We investigate the performance of the Reitzinger and Schöberl algorithm [Num.Lin.Alg.Appl. vol.9(2002), pp.223-238], which uses aggregation techniques to construct the edge prolongation matrix. More precisely, we perform a Fourier analysis of the method in two-grid setting, showing its optimality. The analysis is supplemented with some numerical investigations. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

No description available.

No description available.