Técnicas Algebraicas de Precondicionamiento para la resolución de Sistemas Lineales

Abstract

Esta tesis se centra en el estudio de tecnicas de precondicionamiento para la resolucion de sistemas lineales de ecuaciones, provenientes de la resolucion de ecuaciones diferenciales en derivadas parciales. La caracteristica comun de los sistemas lineales objeto de interes es su enorme tamano, y el hecho de que la matriz de coeficientes asociada a estos sistemas es dispersa. Se utilizan los modelos de programacion de paso de mensajes y memoria compartida, y se orienta este trabajo a problemas de un tamano medio, hasta 10^5 ecuaciones. <br/><br/>La resolucion de sistemas lineales de ecuaciones es, comunmente, el nucleo computacional mas costoso, en cuanto a tiempo de ejecucion, de muchas simulaciones numericas industriales, aunque otros problemas tales como calculo de autovalores tambien suelen ocurrir.<br/><br/>Tipicamente, estos problemas consumen una significante porcion del tiempo computacional requerido por una simulacion completa. Una reciente revision sobre el actual uso de supercomputadores de alto rendimiento indica que mas del 70% del tiempo computacional es usado para resolver grandes sistemas lineales de ecuaciones. Un impacto industrial muy importante debe ocurrir si el rendimiento de los metodos usados para resolver estos sistemas pudiera ser mejorado. <br/><br/>El problema de resolver sistemas lineales ha sido ampliamente analizado para arquitecturas de memoria compartida, donde el paralelismo que se suele explotar es de grano fino. Sin embargo, el interes en explotar el paralelismo grano grueso, junto con la aparicion de librerias que garantizan la portabilidad de los programas basados en paso de mensaje y junto al avance de la tecnologia, ha hecho posible que en estos momentos se este comenzado a desarrollar aplicaciones industriales sobre multicomputadores de memoria compartida-distribuida. Las tecnicas de descomposicion en dominios son una forma de distribucion de datos que permiten la explotacion del paralelismo de paso de mensaje, y todo el paralelismo interno de cada dominio permite la explotacion del paralelismo de memoria compartida.<br/><br/>En esta tesis se intenta cubrir todos los aspectos teoricos y algoritmicos de los metodos mas usados para resolver sistemas lineales dispersos de ecuaciones. Por ello en primer lugar, se estudia los metodos iterativos más importantes, las técnicas más comunes de precondicionamiento y los metodos multinivel.<br/><br/>En segundo lugar, se analiza la formulacion numerica del problema y su paralelismo, y se propone el uso de un precondicionador paralelo que disminuye significativamente el tiempo de ejecucion. Finalmente, se muestran los resultados obtenidos para un conjunto de problemas provenientes de la resolucion de ecuaciones diferenciales en derivadas parciales.

The study of preconditioning techniques to solve linear systems arising to solve partial differential equations is the focus of this thesis. The common feature of the matrices associated to linear systems are large size and sparse. We use two programming models: message passing and threads. This work has been oriented to solve problems up to 10^5 freedom degree.<br/><br/>The problem to solve linear systems is, frecuently, the computational kernel most expensive (execution time) of many numerical industrial simulations, although others problems such as eigenvalues compute usually it appear. Typically, it problems consume a significant part of the computational time required by a complete simulation. A newly review about the high performance supercomputers suggest that 70% or more of the computational time is used to solve large linear systems. An industrial impact very important should happen if the performance of the methods used to solve these linear systems can be improved. <br/><br/>The problem to solve linear systems has been analized to shared memory architecture, where the paralelism that it exploit is fine grain. Nevertheless, the interest to exploit coarse grain paralelism together with the developed of library where it guarantee portability of the programs based in message passing and together with technology advancement has done possible that in this moment the programmer's develop industrial applications on supercomputers with shared-distributed memory. The domain decomposition techniques are a way to exploit the data distribution that permit the explotation of message passing paralelism, and all the internal paralelism in each domain permit the explotation of the shared memory paralelism (threads).<br/><br/>In this thesis, I have tried to include all the theorycal and algorithmics aspect of the methods used more often to solve sparse linear system of equations. The first one, I have studied the iterative methods more important, the algebraic preconditioning technique and multilevel methods. The second one, I have analized the numerical formulation of the problem and it paralelism, and I have proposed to use a parallel preconditioner where it reduce the execution time of the algorithm. Finally, I have showed the numerical results for a set problems arising partial differential equations.