Aquesta tesi ha tingut com a doble objectiu l'estudi de la computació paral·lela de la Transformada Wavelet Discreta (DWT), i l'estudi de les aplicacions de la DWT en el camp de l'àlgebra lineal numèrica

Inicialment es realitza un estudi de les diferents variants de paral·lelització de la DWT i es proposa una nova variant paral·lela, en memòria distribuïda, amb distribucions de dades orientades a blocs de matrius, com la distribució bidimensional cíclica a blocs (2DBC) típica de la llibreria ScaLAPACK. La idea és que la DWT en molts casos és una operació intermèdia i s'ha d'ajustar a les distribucions de dades que s'estiguen utilitzant. Es defineix i demostra una forma de calcular exactament la quantitat d'elements que ha de comunicar cada processador per tal que es puguen calcular de forma independent (sense necessitat de comunicacions posteriors) tots els coeficients de la DWT en una quantitat de nivells determinada. Finalment es proposa una variant específica, més eficient, per al càlcul de la DWT-2D quan s'aplica com pas previ a la resolució d'un sistema d'equacions distribuït 2DBC. Aquesta proposta consisteix a realitzar una permutación de les files i columnes del sistema, i disminueix les comunicacions.

Una altra aportació d'aquesta tesi és el de considerar com un cas típic, el càlcul de la DWT-2D no estàndard en matrius disperses; proposem algorismes per realitzar aquesta operació sense necessitat de construir explícitament la matriu DWT. A més tenim en compte el fenomen d'emplenat (fill-in) que ocorre en aplicar la DWT a una matriu dispersa. Per a això explorem amb els mètodes de reordenació clàssics de grau mínim i de reducció a banda. De manera addicional suggerim com poden influir aquests reordenaments a la convergència dels mètodes multimalla ja que ocorre una redistribució de la norma de la matriu cap als nivells inferiors de la representació multi-escala, el que garantiria una millor compressió.

El camp d'aplicació de la transformada wavelet que es proposa és la resolució de grans sistemes d'equacions lineals. En aquesta tesi exposarem dues aplicacions específiques: paral·lelització de precondicionadors de sistemes lineals basats en la DWT, i el càlcul eficient de la DWT-2D en matrius disperses en conjunció amb l'anàlisi multi-resolució inherent a les wavelet i els mètodes multimalla. S'estudien els Mètodes Wavelet Multimalla Algebraics (Wavelet Algebraic Multigrid Methods, WAMG), algorismes que combinen els mètodes multimalla amb les wavelet, i que no necessiten cap coneixement del problema a resoldre; només la matriu de coeficients i la part dreta del sistema. En particular es proposen dues noves variants dels algorismes WAMG. La primera es basa en la descomposició induïda del sistema lineal en aplicar la DWT i la segona redueix el cost computacional dels cicles de l'algorisme multimalla saltant operacions en alguns nivells o malles. Finalment s'estudia l'aplicació dels WAMG a la resolució eficient de sistemes lineals desplaçats.