Efficient iterative solvers and fast integration for high-order Discontinuous Galerkin methods on polytopic grids

This thesis addresses the design, analysis and implementation of efficient solvers for the solution of the linear system of equations stemming from discontinuous Galerkin discretizations of second-order elliptic partial differential equations on polytopic meshes. In particular, we analyze the convergence properties of geometric V-cycle multigrid algorithms where the sequence of spaces which form the basis of the multigrid scheme are possibly non-nested and are obtained based on employing agglomeration algorithms with possible edge/face coarsening. We prove that the method converges uniformly with respect to the granularity of the grid and the polynomial approximation degree p, provided that the minimum number of smoothing steps, which depends on p, is chosen sufficiently large. In order to improve the V-cycle solver we design and analyze a class of two-level non-overlapping Additive Schwarz preconditioners which are employed as a smoothing operator for the multigrid algorithm. The preconditioner is based on a coarse space which can possibly be chosen to be non-embedded with respect to the finer space. We investigate the dependence of the condition number of the preconditioned system with respect to the diffusion coefficient and the discretization parameters, i.e., the mesh size and the polynomial degree of the fine and coarse spaces. Several numerical tests confirm the theoretical bounds as well as demonstrating a considerable improvement of the iterative V-cycle algorithm in terms of the number of iterations needed to reduce the residual below a given tolerance. We also investigate the implementation aspects of the proposed methods by presenting efficient quadrature rules for the numerical approximation of integrals of polynomial functions over general polygonal/polyhedral elements that do not require an explicit construction of a sub-tessellation into triangular/tetrahedral elements. The proposed "Quadrature free" method is based on recursive applications of Stokes' theorem on homogeneous functions; thereby, the underlying integral may be evaluated using only the values of the integrand and its derivatives at the vertices of the polytopic domain, and hence leads to an exact cubature rule whose quadrature points are the vertices of the polytope. We demonstrate the capabilities of the proposed approach by efficiently computing the stiffness and mass matrices arising from discontinuous Galerkin discretizations of second-order elliptic partial differential equations in both two- and three-dimensions.

Questa tesi affronta la progettazione, l'analisi e l'implementazione di solutori efficienti per la soluzione del sistema lineare di equazioni derivanti da discretizzazioni di tipo Discontinuous Galerkin di equazioni alle derivate parziali ellittiche di secondo ordine su mesh politopiche. In particolare, analizziamo le proprietà di convergenza degli algoritmi multigrid geometrici di tipo V-cycle in cui la sequenza di spazi che costituisce la base dello schema multigrid può essere non nidificata e viene ottenuta sulla base dell'impiego di tecniche di agglomerazione. Dimostriamo che il metodo converge uniformemente rispetto alla granularità della griglia e al grado di approssimazione polinomiale p, a condizione che il numero minimo di passi di smoothing, che dipende da p, sia scelto sufficientemente grande. Al fine di migliorare il solutore V-cycle, progettiamo e analizziamo una classe di precondizionatori di tipo Schwarz additivo che vengono impiegati come operatori di smoothing per l'algoritmo multigrid. Il precondizionatore si basa su uno spazio coarse che può essere scelto non nidificato rispetto allo spazio più fine. Studiamo quindi la dipendenza del numero di condizione del sistema precondizionato rispetto al coefficiente di diffusione e ai parametri di discretizzazione, cioè la dimensione delle griglie e il grado polinomiale degli spazi fini e coarse. Numerosi test numerici confermano le stime teoriche e dimostrano un notevole miglioramento dell'algoritmo V-cycle iterativo in termini di numero di iterazioni necessarie per ridurre il residuo al di sotto di una determinata tolleranza. Consideriamo anche gli aspetti di implementazione dei metodi proposti presentando regole di quadratura efficienti per l'approssimazione numerica di integrali di funzioni polinomiali su elementi poligonali/poliedrici generici che non richiedono una sotto-partizione in elementi triangolari/tetraedrici. Il metodo proposto, denominato "Quadrature free", è basato su applicazioni ricorsive del teorema di Stokes su funzioni omogenee; in tal modo, l'integrale sottostante può essere valutato usando solo i valori della funzione integranda, e delle sue derivate, ai vertici del dominio politopoico, e quindi porta ad una regola di cubatura esatta i cui punti di quadratura sono i vertici del politopo. Dimostriamo le capacità dell'approccio proposto calcolando in modo efficiente le matrici di massa e di stiffness derivanti dalla discretizzazione di tipo Discontinuous Galerkin di equazioni differenziali alle derivate parziali ellittiche del secondo ordine.