Implementación Paralela y Heterogénea de la Transformación de Householder y sus aplicaciones

Implementación Paralela y Heterogénea de la Transformación de Householder y sus aplicaciones

Juan Cipriano Hernández Cortés
 

Texto completo de la Tesis     

 


Resumen

La transformación de Householder es utilizada en distintos métodos de álgebra lineal numérica como lo son: solucionadores de sistemas de ecuaciones, encontrar la forma triangular de matrices, bifactorización de matrices, bidiagonalización de matrices, calculo de la descomposición en valores singulares de una matriz. Problemas como las ecuaciones de Schrödinger, sistemas de Química Cuántica o el problema de muchos cuerpos involucran operadores matriciales de grandes dimensiones. En la actualidad las arquitecturas multi-many core se han consolidado en los distintos tipos de plataformas computacionales desde dispositivos móviles hasta servidores y centros de supercomputación. Este tipo de arquitecturas tienen gran aceleración al realizar operaciones vectoriales, sin embargo, uno de los grandes retos que se presentan al utilizar estas arquitecturas es la limitada memoria con la que cuentan, por ello es necesario realizar implementaciones que sean escalables y utilicen un modelo de memoria distribuida para poder resolver problemas de dimensiones grandes. En el presente trabajo se propone una forma de distribuir el trabajo entre distintos nodos para implementar la transformación de Householder y aplicarla a la bifactorización y bidiagonalización de matrices utilizando MPI como interfaz de comunicación y CUDA para la programación de tarjetas de procesamiento de gráficos, con la finalidad de poder trabajar con matrices de grandes dimensiones

 

Abstract

Householder’s transformation is widely used in several linear algebra numeric methods instances of this are: equations systems solvers, getting triangular matrices form, matrices bifactorization, bidiagonalization of a matrix, computing singular value decomposition. There are problems such as Schrödinger’s equations, Quantum Chemistry or the many bodies problem that use high dimensional matrix operators. Nowadays the multi-many core architectures have been consolidated in all kind of computing platforms from mobile devices to computing servers and supercomputing centers. This kind of architectures has a great speed-up in vectorial operations, nevertheless, their limited memory is a challenge when you have to do computations on large matrices, for this reason is necessary develop scalable applications that could use a memory distributed model. In this work we propose a way to split the Householder’s transformation in several computing nodes and apply it to bifactorization and bidiagonalization problems using MPI as communication interface and CUDA as graphic processing units application programming interface