Implementación de una librería orientada a objeto para matrices esparcidas en paralelo

Abstract

Al buscar la solución matemática en muchos de los problemas científicos, se ven involucradas matrices de dimensiones altas y cuyos elementos distintos de cero son pocos comparados con el orden de la matriz, estas matrices se conocen como matrices esparcidas y existen diferentes formatos para almacenarlas, entre ellos el Compressed Sparse Rows (CSR). Para lograr la solución de algunos de los problemas que tienen matrices, se necesitarán solucionar sistemas lineales y a su vez se efectuarán un gran número de veces el producto de matrices con vectores. Esta cantidad de operaciones y las dimensiones de las matrices, hacen que se requiera del uso de implementaciones para computadoras en paralelo. Al efectuar el producto de una matriz esparcida con un vector distribuidos en paralelo, debe haber comunicación entre procesadores del vector o parte del vector que cada uno de ellos almacenan y esta comunicación podría hacer que el tiempo de cómputo sea alto.En esta tesis se desarrolló una implementación para matrices esparcidas en paralelo con diferentes estrategias para atacar el problema de comunicación en el producto de una matriz esparcida con un vector. La implementación se realizó con el paradigma orientado a objetos en C++ y para la programación en paralelo con las librerías de openMPI.

The mathematical solution of many scientific problems involves matrices of high dimensions and whose nonzero elements are few compared to the order of the matrix. These matrices are known as sparse matrices and there exist several storage formats, among them the Compressed Sparse Rows (CSR) format. In order to obtain tbe solution of some of the problems involving matrices, it is necessary to solve linear systems requiring the product of a matrix by a vector to be performed a large number of times. The number of operations and the dimensions of the matrices make necessary the use implementations for parallel computers. When performing the product of a sparse matrix by a vector distributed in parallel there must be communication between the processes keeping each part of the vector, and this communication may cause the overall computing time to be high. In this thesis we developed an implementation for parallel sparse matrices with several strate- gies for solving the communication problem for performing the product of a sparse matrix by a vector. The implementation uses the object-oriented paradigm in C++ and the Open MPI library.