Computación Paralela de la Transformada Wavelet; Aplicaciones de la Transformada Wavelet al Álgebra Lineal Numérica

Abstract

Esta tesis ha tenido como doble objetivo el estudio de la computación paralela de la TransformadaWavelet Discreta (DWT), y el estudio de las aplicaciones de la DWT en el campo del álgebra lineal numérica Inicialmente se realiza 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 distribución bidimensional cíclica a bloques (2DBC) típica de la librería 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 (sin necesidad de comunicaciones posteriores) todos los coeficientes de la DWT 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. Esta propuesta consiste en realizar una permutación de las filas y columnas del sistema que disminuye 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 algoritmosWAMG. La primera se basa en la descomposición inducida del sistema lineal al aplicar la DWT y la segunda reduce el coste computacional 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.