Title: Application of hp-adaptive discontinuous Galerkin method to com- pressible flow simulation Author: Karol Tarčák Department: Department of Numerical Mathematics Supervisor: prof. RNDr. Vít Dolejší, Ph.D., DSc. Abstract: In the present work we study an residuum estimate of disconti- nuous Galerkin method for the solution of Navier-Stokes equations. Firstly we summarize the construction of the viscous compressible flow model via Navier-Stokes partial differential equation and discontinuous Galerkin met- hod. Then we propose an extension of an already known residuum estimate for stationary problems to non-stationary problems. We observe the beha- vior of the proposed estimate and modify an existing hp-adaptive algorithm to use our estimate. Finally we apply the modified algorithm on test cases and present adapted meshes from the numerical experiments. Keywords: discontinuous Galerkin method, adaptivity, error estimate 4

This thesis is concerned with the study of transient scattering of acoustic waves by an obstacle in an infinite domain, where the scattered wave is represented in terms of time domain boundary layer potentials. The problem of finding the unknown solution of the scattering problem is thus reduced to the problem of finding the unknown density of the time domain boundary layer operators on the obstacle’s boundary, subject to the boundary data of the known incident wave. Using a Galerkin approach, the unknown density is replaced by a piecewise polynomial approximation, the coefficients of which can be found by solving a linear system. The entries of the system matrix of this linear system involve, for the case of a two dimensional scattering problem, integrals over four dimensional space-time manifolds. An accurate computation of these integrals is crucial for the stability of this method. Using piecewise polynomials of low order, the two temporal integrals can be evaluated analytically, leading to kernel functions for the spatial integrals with complicated domains of piecewise support. These spatial kernel functions are generalised into a class of admissible kernel functions. A quadrature scheme for the approximation of the two dimensional spatial integrals with admissible kernel functions is presented and proven to converge exponentially by using the theory of countably normed spaces. A priori error estimates for the Galerkin approximation scheme are recalled, enhanced and discussed. In particular, the scattered wave’s energy is studied as an alternative error measure. The numerical schemes are presented in such a way that allows the use of non-uniform meshes in space and time, in order to be used with adaptive methods that are based on a posteriori error indicators and which modify the computational domain according to the values of these error indicators. The theoretical analysis of these schemes demands the study of generalised mapping properties of time domain boundary layer potentials and integral operators, analogously to the well known results for elliptic problems. These mapping properties are shown for both two and three space dimensions. Using the generalised mapping properties, three types of a posteriori error estimators are adopted from the literature on elliptic problems and studied within the context of the two dimensional transient problem. Some comments on the three dimensional case are also given. Advantages and disadvantages of each of these a posteriori error estimates are discussed and compared to the a priori error estimates. The thesis concludes with the presentation of two adaptive schemes for the two dimensional scattering problem and some corresponding numerical experiments.

O Método dos Elementos Finitos Generalizados (MEFG) propõe, basicamente, uma ampliação no espaço de aproximação do Método dos Elementos Finitos (MEF) convencional por meio de funções de enriquecimento que representem bem comportamentos locais da solução do problema. Ele tem se apresentado como uma alternativa eficaz para a obtenção de soluções numéricas com boa precisão para problemas nos quais o MEF convencional requer custo computacional bastante elevado. Em relação ao controle sobre a precisão da resposta numérica obtida, o estudo e análise de erros de discretização, assim como a implementação de estratégias adaptativas, são temas que já foram amplamente abordados para o MEF e recentemente vêm sendo explorados no contexto do MEFG e suas versões estáveis. Neste trabalho, trata-se do tema de adaptatividade para o MEFG, objetivando melhor avaliar a precisão das soluções encontradas assim como garantir que elas atendam a limitações pré-especificadas para medidas dos erros. Em primeiro lugar, avalia-se a utilização de um estimador de erro a posteriori, recentemente proposto, como indicador de regiões onde a adaptatividade h ou p possa ser aplicada. Com o indicador adotado, estende-se para o MEFG estratégias h-adaptativas comumente utilizadas para o MEF, realizadas a partir de sucessivas gerações da malha. Além disso, explora-se neste trabalho uma técnica de agrupamento de partições da unidade, específica do MEFG, para tratar problemas de malhas irregulares e possibilitar análises h-adaptativas realizadas sobre sub-regiões do domínio do problema. Já no que se refere às análises p-adaptativas, a estratégia consiste em definir regiões de interesse para ativar o enriquecimento polinomial da solução aproximada. Exemplos numéricos ilustram a efetividade de todas as análises adaptativas implementadas, propostas para o MEFG e suas versões estáveis, as quais proporcionam respostas que atendem a limites de tolerância previamente estabelecidos. / The Generalized Finite Element Method (GFEM) proposes the generation of numerical approximations that belong to an space obtained by augmenting low-order standard finite element approximation spaces by enrichment functions that well represent local behaviours of the problem solution. The method has become an efficient alternative to obtain solutions with good accuracy for problems in which the standard Finite Element Method (FEM) would require excessively high computational cost. Regarding the control over the numerical solutions\' accuracy, discretization error analysis and study, as well as the implementation of adaptive strategies, are subjects largely studied for the FEM and they are recently being exploited in the GFEM and its stable versions context. In this work, adaptivity for the GFEM is addressed, looking for better evaluate the solutions\' accuracy and ensure that they meet users\' pre-specified limits for error measures. Firstly, the use of a recently proposed a posteriori error estimator as an indicator of the regions where h- or p-adaptivity can be performed is evaluated. With this chosen indicator, h-adaptive strategies commonly used for the FEM are extended to the GFEM by performing successive remeshings. Moreover, a partition of unity clustering technique is also exploited in order to treat nonmatching meshes and to enable h-adaptive analysis to be performed over some pre-defined domain subregions. Regarding the p-adaptive analysis, the basic strategy consists of defining some regions over which it will be set polynomial enrichments for the approximate solution using a particular GFEM stable version. Numerical examples show the effectiveness of all performed adaptive analysis, proposed for conventional and stable GFEMs. All implementations provide responses that can meet the users\' pre-specified tolerance.

Esta tese apresenta a formulação de uma extensão da tabela de decisão adaptativa, denominada Tabela de Decisão Adaptativa Estendida (TDAE), que tem por objetivo apoiar aplicações de tomada de decisão multicritério. É implementado um algoritmo de tomada de decisão para a TDAE que incorpora os mecanismos de tabelas de decisão tradicionais, técnicas adaptativas e procedimentos de métodos multicritério. A descrição e execução do algoritmo e a aplicabilidade da TDAE em problemas de decisão multicritério são mostradas numa aplicação particular. É apresentada uma avaliação de desempenho do algoritmo de decisão, em relação ao custo de tempo e de memória exigidos para a sua execução. Uma ferramenta de apoio à decisão baseada na TDAE é descrita e implementada. Os resultados do trabalho mostram que a TDAE é viável e pode ser uma opção alternativa de dispositivo para apoiar processos decisórios de problemas de decisão multicritério. / This thesis presents the formulation of an extension of the adaptive decision table called Table of Extended Adaptive Decision (TDAE), which aims at supporting applications of multicriteria decision making. A decision making algorithm is implemented for the TDAE embodying the traditional decision tables mechanisms, adaptive techniques, and multicriteria methods procedures. The description and implementation of the algorithm and the applicability of TDAE in multicriteria decision problems are shown in a particular application. A perform evaluation of the decision algorithm is presented in relation to time and memory costs required for its implementation. A tool for decision support based on TDAE is described and implemented. The results of the study show that TDAE is viable and can be a device alternative option to support the decision making problems of multicriteria decision.

Este trabalho apresenta um estudo sobre como a tecnologia adaptativa pode ser utilizada para aprimorar métodos existentes de gerenciamento de diálogo. O gerenciamento de diálogo é a atividade central em um sistema computacional de diálogo falado, sendo a responsável por decidir as ações comunicativas que devem ser enviadas ao usuário. Para evidenciar pontos que pudessem ser melhorados através do uso da tecnologia adaptativa, faz-se uma revisão literária ampla do gerenciamento do diálogo. Esta revisão também permite elencar critérios existentes e criar outros novos para avaliar gerenciadores de diálogos. Um modelo de gerenciamento adaptativo baseado em máquinas de estados, denominado Adaptalker, é então proposto e utilizado para criar um framework de desenvolvimento de gerenciadores de diálogo, o qual foi exercitado pelo desenvolvimento ilustrativo de uma aplicação simples de venda de pizzas. A análise desse exemplo permite observar como a adaptatividade é utilizada para aperfeiçoar o modelo, tornando-o capaz, por exemplo, de lidar de forma mais eficiente tanto com o reparo do diálogo quanto com a iniciativa do usuário. As regras de gerenciamento do Adaptalker são organizadas em submáquinas, que trabalham de forma concorrente para decidir qual a próxima ação comunicativa. / This work presents a study on how to apply adaptive technologies to improve existing dialog management methodologies. Dialog management is the central activity of a spoken dialog system, being responsible for choosing the communicative actions sent to the system user. In order to evidence parts that can be improved with adaptive technology, a large review on dialog management is presented. This review allows us to point existing criteria and create new ones to evaluate dialog managers. An adaptive management model based on finite state-based spoken dialog systems, Adaptalker, is proposed and used to build a development framework of dialog managers, which is illustrated by creating a pizza selling application. Analysis of this example allows us to observe how to use adaptivity to improve the model, allowing it to handle both dialog repair and user initiative more efficiently. Adaptalker groups its management rules in submachines that work concurrently to choose the next communication action.

Este trabalho apresenta um estudo sobre como a tecnologia adaptativa pode ser utilizada para aprimorar métodos existentes de gerenciamento de diálogo. O gerenciamento de diálogo é a atividade central em um sistema computacional de diálogo falado, sendo a responsável por decidir as ações comunicativas que devem ser enviadas ao usuário. Para evidenciar pontos que pudessem ser melhorados através do uso da tecnologia adaptativa, faz-se uma revisão literária ampla do gerenciamento do diálogo. Esta revisão também permite elencar critérios existentes e criar outros novos para avaliar gerenciadores de diálogos. Um modelo de gerenciamento adaptativo baseado em máquinas de estados, denominado Adaptalker, é então proposto e utilizado para criar um framework de desenvolvimento de gerenciadores de diálogo, o qual foi exercitado pelo desenvolvimento ilustrativo de uma aplicação simples de venda de pizzas. A análise desse exemplo permite observar como a adaptatividade é utilizada para aperfeiçoar o modelo, tornando-o capaz, por exemplo, de lidar de forma mais eficiente tanto com o reparo do diálogo quanto com a iniciativa do usuário. As regras de gerenciamento do Adaptalker são organizadas em submáquinas, que trabalham de forma concorrente para decidir qual a próxima ação comunicativa. / This work presents a study on how to apply adaptive technologies to improve existing dialog management methodologies. Dialog management is the central activity of a spoken dialog system, being responsible for choosing the communicative actions sent to the system user. In order to evidence parts that can be improved with adaptive technology, a large review on dialog management is presented. This review allows us to point existing criteria and create new ones to evaluate dialog managers. An adaptive management model based on finite state-based spoken dialog systems, Adaptalker, is proposed and used to build a development framework of dialog managers, which is illustrated by creating a pizza selling application. Analysis of this example allows us to observe how to use adaptivity to improve the model, allowing it to handle both dialog repair and user initiative more efficiently. Adaptalker groups its management rules in submachines that work concurrently to choose the next communication action.

Esta tese apresenta a formulação de uma extensão da tabela de decisão adaptativa, denominada Tabela de Decisão Adaptativa Estendida (TDAE), que tem por objetivo apoiar aplicações de tomada de decisão multicritério. É implementado um algoritmo de tomada de decisão para a TDAE que incorpora os mecanismos de tabelas de decisão tradicionais, técnicas adaptativas e procedimentos de métodos multicritério. A descrição e execução do algoritmo e a aplicabilidade da TDAE em problemas de decisão multicritério são mostradas numa aplicação particular. É apresentada uma avaliação de desempenho do algoritmo de decisão, em relação ao custo de tempo e de memória exigidos para a sua execução. Uma ferramenta de apoio à decisão baseada na TDAE é descrita e implementada. Os resultados do trabalho mostram que a TDAE é viável e pode ser uma opção alternativa de dispositivo para apoiar processos decisórios de problemas de decisão multicritério. / This thesis presents the formulation of an extension of the adaptive decision table called Table of Extended Adaptive Decision (TDAE), which aims at supporting applications of multicriteria decision making. A decision making algorithm is implemented for the TDAE embodying the traditional decision tables mechanisms, adaptive techniques, and multicriteria methods procedures. The description and implementation of the algorithm and the applicability of TDAE in multicriteria decision problems are shown in a particular application. A perform evaluation of the decision algorithm is presented in relation to time and memory costs required for its implementation. A tool for decision support based on TDAE is described and implemented. The results of the study show that TDAE is viable and can be a device alternative option to support the decision making problems of multicriteria decision.

In this thesis we develop and analyze the performance ofadaptive finite element methods for multiphysics problems. Inparticular, we propose a methodology for deriving computable errorestimates when solving unidirectionally coupled multiphysics problemsusing segregated finite element solvers.  The error estimates are of a posteriori type and are derived using the standard frameworkof dual weighted residual estimates.  A main feature of themethodology is its capability of automatically estimating thepropagation of error between the involved solvers with respect to anoverall computational goal. The a posteriori estimates are used todrive local mesh refinement, which concentrates the computationalpower to where it is most needed.  We have applied and numericallystudied the methodology to several common multiphysics problems usingvarious types of finite elements in both two and three spatialdimensions. Multiphysics problems often involve convection-diffusion equations for whichstandard finite elements can be unstable. For such equations we formulatea robust discontinuous Galerkin method of optimal order with piecewiseconstant approximation. Sharp a priori and a posteriori error estimatesare proved and verified numerically. Fractional step methods are popular for simulating incompressiblefluid flow. However, since they are not genuine Galerkin methods, butrather based on operator splitting, they do not fit into the standardframework for a posteriori error analysis. We formally derive an aposteriori error estimate for a prototype fractional step method byseparating the error in a functional describing the computational goalinto a finite element discretization residual, a time steppingresidual, and an algebraic residual.

The main focus of this thesis is on fast numerical methods, where adaptivity is an important mechanism to lowering the methods' complexity. The application of the methods are in the areas of wireless communication, antenna design, radar signature computation, noise prediction, medical ultrasonography, crystal growth, flame propagation, wave propagation, seismology, geometrical optics and image processing.   We first consider high frequency wave propagation problems with a variable speed function in one dimension, modeled by the Helmholtz equation. One significant difficulty of standard numerical methods for such problems is that the wave length is very short compared to the computational domain and many discretization points are needed to resolve the solution. The computational cost, thus grows algebraically with the frequency w. For scattering problems with impenetrable scatterer in homogeneous media, new methods have recently been derived with a provably lower cost in terms of w. In this thesis, we suggest and analyze a fast numerical method for the one dimensional Helmholtz equation with variable speed function (variable media) that is based on wave-splitting. The Helmholtz equation is split into two one-way wave equations which are then solved iteratively for a given tolerance. We show rigorously that the algorithm is convergent, and that the computational cost depends only weakly on the frequency for fixed accuracy.  We next consider interface tracking problems where the interface moves by a velocity field that does not depend on the interface itself. We derive fast adaptive  numerical methods for such problems. Adaptivity makes methods robust in the sense that they can handle a large class of problems, including problems with expanding interface and problems where the interface has corners. They are based on a multiresolution representation of the interface, i.e. the interface is represented hierarchically by wavelet vectors corresponding to increasingly detailed meshes. The complexity of standard numerical methods for interface tracking, where the interface is described by marker points, is O(N/dt), where N is the number of marker points on the interface and dt is the time step. The methods that we develop in this thesis have O(dt^(-1)log N) computational cost for the same order of accuracy in dt. In the adaptive version, the cost is O(tol^(-1/p)log N), where tol is some given tolerance and p is the order of the numerical method for ordinary differential equations that is used for time advection of the interface.   Finally, we consider time-dependent Hamilton-Jacobi equations with convex Hamiltonians. We suggest a numerical method that is computationally efficient and accurate. It is based on a reformulation of the equation as a front tracking problem, which is solved with the fast interface tracking methods together with a post-processing step.  The complexity of standard numerical methods for such problems is O(dt^(-(d+1))) in d dimensions, where dt is the time step. The complexity of our method is reduced to O(dt^(-d)|log dt|) or even to O(dt^(-d)). / <p>QC 20121116</p>

This thesis is devoted to the numerical analysis of mesh-free methods and, in particular, to the study of the possible advantages of the EFG (Element Free Galerkin) mesh-free method against the well-known FE (Finite Element) method. More precisely, the EFG method and the FE method behavior are compared in two particular interesting problems: (1) analysis of volumetric locking in mechanical problems and (2) accurate resolution of transient convection dominated problems. In both cases the good properties and possibilities of mesh-free methods become apparent. However, in several situations the FE method is still more competitive: for instance, the computation of the FE shape functions and its integrals are less costly, and essential boundary conditions can be easily imposed. Thus, in order to take advantage of the good properties of both methods, a mixed interpolation combining FE and EFG is proposed. This formulation can be applied in two useful situations: (i) enrichment of finite elements with EFG, and (ii) coupling of FE and EFG. An a priori error estimate for the first one is presented and proved. Several examples show the applicability of the mixed interpolation in adaptive computations. / Aquesta tesi està dedicada a l'anàlisi numèrica dels mètodes sense malla i, en particular, a l'estudi dels possibles avantatges del mètode EFG (Element Free Galerkin) davant del ben conegut MEF (Mètode dels Elements Finits). Concretament, es comparen el mètode EFG i el MEF en dos problemes concrets d'interès: (1) l'anàlisi del bloqueig volumètric en problemes mecànics i (2) la resolució precisa de problemes transitoris amb convecció dominant. Les bones propietats i possibilitats dels mètodes sense malla es fan evidents en tots dos casos.Tot i així, en varis aspectes el MEF resulta més competitiu: per exemple, el càlcul de les funcions de forma i de les seves integrals es menys costós, i les condicions de contorn essencials es poden imposar fàcilment. Amb l'objectiu d'aprofitar les bones qualitats dels dos mètodes, es proposa una interpolació mixta combinant elements finits y EFG, aplicable en dues situacions: (i) enriquiment d'elements finits amb EFG i (ii) acoblament d'elements finits i EFG. Per al primer cas, es presenta i demostra una cota a priori de l'error. L'aplicabilitat d'aquesta interpolació mixta en processos adaptatius es mostra amb varis exemples. / Esta tesis está dedicada al análisis numérico de los métodos sin malla y, en particular, al estudio de las posibles ventajas del método EFG (Element Free Galerkin) frente al bien conocido MEF (Método de los Elementos Finitos). Concretamente, se comparan el método EFG y el MEF en dos problemas concretos de interés: (1) el análisis del bloqueo volumétrico en problemas mecánicos y (2) la resolución precisa de problemas transitorios con convección dominante. Las buenas propiedades y posibilidades de los métodos sin malla se hacen evidentes en ambos casos.Sin embargo, en varios aspectos el MEF resulta más competitivo: por ejemplo, el cálculo de las funciones de forma y sus integrales es menos costoso, y las condiciones de contorno esenciales se pueden imponer fácilmente. Con el objetivo de aprovechar las buenas cualidades de ambos métodos, se propone una interpolación mixta combinando elementos finitos y EFG, aplicable en dos situaciones: (i) enriquecimiento de elementos finitos con EFG, y (ii) acoplamiento de elementos finitos y EFG. Para el primer caso, se presenta y demuestra una cota a priori del error. La aplicabilidad de esta interpolación mixta en procesos adaptativos se muestra con varios ejemplos.