Computación paralela de la transformada wavelet; aplicaciones de la transformada wavelet al álgebra lineal numérica

Resumen

Esta tesis tiene el objetivo de estudiar aplicaciones de la transformada wavelet discreta (DWT) al álgebra lineal numérica, Se hace un estudio de las distintas variantes de paralelización de la DWT y se propone una nueva variante paralela, en memoria distribuida, con distribuciones de datos orientadas a bloques de matrices, como la 2DBC de ScaLAPACK. La idea es que la DWT en muchos casos es una operación intermedia y debe ajustarse a las distribuciones de datos que se estén usando. Se define y demuestra una forma de calcular exactamente la cantidad de elementos que debe comunicar cada procesador para que se puedan calcular de forma independiente todo los coeficientes wavelet en una cantidad de niveles determinada. Finalmente se propone una variante específica, más eficiente, para el cálculo de la DWT-2D cuando se aplica como paso previo a la resolución de un sistema de ecuaciones distribuido 2DBC, considerando una permutación de las filas y columnas del sistema que minimiza las comunicaciones. Otro de los aportes de esta tesis es el de considerar como un caso típico, el cálculo de la DWT-2D no estándar en matrices dispersas, proponemos algoritmos para realizar esta operación sin necesidad de construir explícitamente la matriz wavelet. Además tenemos en cuenta el fenómeno de rellenado (fill-in) que ocurre al aplicar la DWT a una matriz dispersa. Para ello exploramos con los métodos de reordenamiento clásicos de grado mínimo y de reducción a banda. De forma adicional sugerimos como pueden influir esos reordenamientos a la convergencia de los métodos multimalla ya que ocurre una redistribución de la norma de la matriz hacia los niveles inferiores de la representación multi-escala, lo que garantizaría una mejor compresión. El campo de aplicación de la transformada wavelet que se propone es la resolución de grandes sistemas de ecuaciones lineales. En esta tesis expondremos dos aplicaciones específicas: paralelización de precondicionadores de sistemas lineales basados en la DWT, y el cálculo eficiente de la DWT-2D en matrices dispersas en conjunción con el análisis multi-resolución inherente a las wavelet y los métodos multimalla. Se estudian los Métodos Wavelet Multimalla Algebraicos (Wavelet Algebraic Multigrid Methods, WAMG), algoritmos que combinan los métodos multimalla con las wavelet, y que no necesitan de ningún conocimiento del problema a resolver; solo la matriz de coeficientes y la parte derecha del sistema. En particular se proponen dos nuevas variantes de los algoritmos WAMG. La primera se basa en la descomposición inducida del sistema lineal al aplicar la DWT y la segunda reduce el costo de los ciclos del algoritmo multimalla saltando operaciones en algunos niveles o mallas. Finalmente se estudia la aplicación de los WAMG a la resolución eficiente de sistemas lineales desplazados.