Métodos multiniveles para discretizaciones generadas por el método "Local Discontinuous Galerkin"

Abstract

Un desafío computacional de interés es cómo acelerar un método iterativo para resolver un sistema lineal proveniente de ecuaciones diferenciales parciales discretizados por métodos discontinuos. Los métodos “Discontinuous Galerkin” (DG) son utilizados por sus atractivas propiedades tales como aproximación de alto orden, ser un método conservador y por no imponer continuidad entre celdas. Sin embargo, se conoce que el condicionamiento de la matriz de rigidez tiene un comportamiento asintótico de O(h^{−2}), donde h es el tamaño de la malla. Es necesario el uso de una estrategia que reduzca el condicionamiento y mejore la convergencia del método iterativo, a esto se le conoce como precondicionador. Las técnicas multiniveles son bien conocidas por su buen desempeño en reducir el condicionamiento de sistemas lineales derivados de la discretización de ecuaciones diferenciales parciales lineales; ya sea por el método de diferencias finitas, método de los elementos finitos y métodos DG. En este trabajo se presenta un análisis de Fourier de tres técnicas multiniveles, dos versiones geométricas y una versi ́on semi-algebraica, aplicada a discretizaciones del método LDG. Se compararán dos estrategias geométricas, una utiliza la prolongación natural, y la otra, una prolongación formulada en esta tesis. Este operador de prolongación está basado en transferir al espacio de mayor dimensión unas combinaciones convexas de funciones que pertenecen al espacio de menor dimensión. Con la ayuda del análisis de Fourier se seleccionan los valores apropiados para la prolongación que depende de los parámetros del método LDG, con el propósito de minimizar el factor de convergencia. El análisis de dos niveles es extendido para estimar el radio de convergencia de la técnica multiniveles semi-algebraica, estrategia basada en el colapsado de nodos y se ilustra su buen rendimiento como método iterativo de dos niveles. Se hará un estudio del espectro de las técnicas de relajación tales como los métodos Jacobi, Gauss Seidel y Gauss Seidel simétrico, en el dominio de la frecuencia. Se plasma una serie de experimentos para validar los estimados obtenidos por el análisis de Fourier. Los resultados sugieren que la versión semi-algebraica es la más rápida en converger, seguido por la técnica de multiniveles propuesta en esta tesis.

A computational challenge of interest is how to accelerate an iterative method to solve a linear system arising from partial differential equations discretized by discontinuous methods. Discontinuous Galerkin (DG) methods are used for their attractive properties such as high order of approximation, being a conservative method, and for not imposing continuity between cells. However, it is known that the condition number of the stiffness matrix has an asymptotic behavior of O(h^{−2}), where h is the mesh size. The use of a strategy that reduces the condition number and improves the convergence of the iterative solver is necessary. This is known as a preconditioner. Multilevel techniques are well known for their good performance in reducing the conditioning of linear systems derived from the discretization of linear partial differential equations; either by the finite difference method, finite element method, or DG methods. In this work, we present a Fourier analysis of three multilevel techniques, two geometric versions, and a semi-algebraic version, applied to discretizations of the LDG method. Two geometrical strategies have been compared. One using the natural prolongation, and the other, a prolongation formulated in this thesis. This prolongation operator is based on transferring convex combinations of functions belonging to the low dimension space to the high dimension space. With the help of the Fourier analysis, the appropriate values are selected for the prolongation, which depends on the parameters of the LDG method, in order to minimize the convergence factor. The two-level analysis is extended to estimate the convergence rate of the semi-algebraic multilevel technique, a strategy based on collapsing nodes, and its good performance is illustrated as a two-level method. A study has been made of the spectrum of relaxation techniques such as the Jacobi, Gauss Seidel and Gauss Seidel symmetric methods, in the frequency domain. A series of experiments are carried out to validate the estimates obtained by the Fourier analysis. The results suggest that the semi-algebraic version is the fastest to converge, followed by the multi-level technique proposed in this thesis.