Matrices dispersas en Java para el procesamiento de grandes ...

Matrices dispersas en Java para el procesamiento de grandes volúmenes de datos Reinier Millo-Sánchez *1 , Isabel Cristina Pérez Verona2 , Jarvin Antón Vargas2 and Tania Rama Hernández3 1

2

Universidad Central “Marta Abreu” de Las Villas, Santa Clara, Cuba Universidad “Máximo Gómez Báez” de Ciego de Ávila, Ciego de Ávila, Cuba 3 Ciego de Ávila, Cuba

Resumen Las matrices dispersas son matrices en las cuales existen gran cantidad de valores nulos o ceros. El aprovechamiento de este conocimiento permite reducir el costo computacional de las operaciones que se pueden realizar sobre estas matrices, así como el costo espacial para el almacenamiento de la información. Las matrices dispersas permiten el procesamiento de grandes volúmenes de información de conjuntos de datos no densos. En muchos casos el manejo de estos volúmenes de datos sin tener en cuenta la densidad de estos, se vuelve impracticable, pues operaciones como la multiplicación de matrices, se vuelve un proceso altamente costoso desde el punto de vista computacional, tanto temporal como espacial. Muchas implementaciones sobre este tipo de matrices han sido llevadas a cabo con estructuras como listas y arreglos dinámicos, los cuales mejoran el procesamiento de matrices dispersas, pero no logran aprovechar todas las potencialidades de estas matrices, pues solo tienen en cuenta una sola dimensión dispersa. En este trabajo se propone una implementación de matrices dispersas en el lenguaje de programación Java empleando árboles balanceados para su implementación. Se comparan los resultados con otras implementaciones de matrices dispersas. Abstract The sparse matrices are matrices in which there are lots of zeros. The use of this knowledge can reduce the computational cost of operations that can be performed on these matrices and reduce the space cost for storage of information. These matrices allow the processing of large volumes of information of not dense data sets. In many cases the management of these data volumes regardless of the density, becomes impracticable for operations such as matrix multiplication. This operation becomes a highly expensive process from a computational point of view. Many implementations of this type of matrices have been carried out with structures such as lists and dynamic arrays, which improve the processing of sparse matrices, but don’t exploit the full potential of these matrices. This paper propose an implementation of sparse matrices in the Java programming language using balanced trees for implementation. The results are compared with other implementations of sparse matrices. *

[email protected]

1

1.

Introducción

En muchas ocasiones el procesamiento computacional de grandes volúmenes de datos, donde una gran parte de estos datos son ceros o valores nulos, se convierte en una tarea muy compleja y en ocasiones imposible de realizar. En muchas ocasiones este análisis demanda gran cantidad de recursos computacionales, tanto recursos de hardware como recursos de cómputo. El conocimiento de las características de la información permite el empleo de estructuras de datos especiales para optimizar el rendimiento del sistema durante el procesamiento de la información. Las matrices dispersas (Golub and Vanloan, 1996; Stoer and Bulirsch, 2002) son matrices donde una gran parte de sus valores son ceros, por lo cual, estos valores pueden ser omitidos en su almacenamiento tanto en memoria física como en los dispositivos de almacenamiento. Este tipo de matrices es muy empleado en problemas de modelación de grafos, permitiendo la representación de grandes volúmenes de información. En el campo de la inteligencia artificial las matrices dispersas han sido muy empleadas debido a la cantidad de información que en ocasiones procesan los algoritmos de aprendizaje automático (Mitchell, 1997; Abeel, 2006). Por otra parte en el campo de la recuperación de información también han sido muy empleadas para establecer relaciones entre la información. Otras aplicaciones de las matrices dispersas son la modelación de sistemas multicuerpos complejos (Hidalgo et al., 2014). Uno de los elementos a tener en cuenta cuando se trabaja con matrices dispersas es la estructura de datos que se emplea para su representación, así como la implementación de las operaciones sobre las matrices. Estas operaciones deben ser implementadas de forma específica para la estructura de datos que se emplea. En este trabajo se propone el empleo de árboles balanceados en Java para la implementación de matrices dispersas. Se describen las operaciones básicas matriciales (suma, resta, multiplicación, traspuesta) y las operaciones con valores escalares (multiplicación, división).

2.

Las matrices dispersas

Muchas han sido las estructuras de datos empleadas para la representación de matrices dispersas. Entre ellas las estructuras de datos más sencilla se encuentran las listas enlazadas y los diccionarios o tablas hash, que nos permiten optimizar el espacio de almacenamiento de la matriz, pero añade un nivel de complejidad computacional durante el acceso a los elementos de la matriz. En ambos casos es necesario almacenar el valor y la posición (fila, columna) en la cual está ubicado el elemento. Otra forma de almacenamiento de las matrices dispersas muy similar a las listas enlazadas es el formato coordenado, en el cual se emplean tres arreglos. Un arreglo almacena la información de la matriz dispersa y los otros dos arreglos son empleados para almacenar las coordenadas de la información. Esta representación aunque resulta ser un poco más eficiente computacionalmente respecto a las listas enlazadas, aún resulta compleja el acceso a la información de la matriz, así como la construcción dinámica de la matriz.

2

Aprovechando las ventajas que brinda el empleo de listas enlazadas y el empleo de arreglos, surgen dos representaciones de matrices dispersas ampliamente usadas (Pissanetzky, 1984), las matrices comprimidas por filas CSR (Compressed Sparse Row) y matrices comprimidas por columnas CSC (Compressed Sparse Column). Estas dos representaciones aunque surgen de la combinación de las listas enlazadas con los arreglos, han sido implementadas empleando tres arreglos para su representación. Las matrices comprimidas por filas y por columnas a diferencia del formato coordenado, no guardan toda la información de la posición donde se encuentra cada elemento. Por ejemplo, las matrices comprimidas por filas, emplean tres arreglos para la representación de la información, consideremos la matriz: 

1 0 8 3 0

  0 4 0 0   A= 0 0 0 8   5 7 9 0 

 

0     1  

0 

(1)

0 3 0 0 0 La representación de la matriz dispersa por filas tiene un arreglo para almacenar todos los valores no ceros o nulos de la matriz A, ordenados por filas, llamemos a este arreglo valores: [

valores =

]

(2)

1 8 3 4 8 5 7 9 1 3

Un segundo arreglo que llamaremos columnas se almacena la columna en la que se encuentra cada elemento almacenado en el arreglo valores, por lo que este arreglo tendrá la misma cantidad de elementos que el arreglo valores: [

columnas =

]

1 3 4 2 4 1 2 3 5 2

(3)

El tercer arreglo a diferencia del formato coordenado no almacena la fila de cada uno de los elementos, sólo almacena un puntero a la posición donde comienza la representación de la fila, llamemos a este arreglo f ilas. Este arreglo tendrá n + 1 elementos, siendo n la cantidad de filas de la matriz A: [

f ilas =

]

1 4 5 6 10 11

(4)

Si queremos localizar todos los elementos de la cuarta fila de la matriz, simplemente buscamos todos los elementos del arreglo valores que se encuentran a partir de f ilas[4] hasta f ilas[5], en este caso desde la posición 6 hasta la 10, sin incluir esta última, se encuentran los elementos de la cuarta fila. Estas dos representaciones de matrices dispersas son muy empleadas, siendo CSC el formato para representar las matrices dispersas en el MATLAB. Estos formatos son eficientes para las operaciones aritméticas y el producto vectorial, pero su construcción y modificación dinámica puede resultar un proceso costoso, por lo que generalmente emplean otro formato 3

Figura 1: Representación parcial de la matriz A empleando AVL para la construcción de la matriz dispersa. Existen otras representaciones de matrices dispersas como son la representación por bandas, matrices comprimidas por diagonales CSD (Compressed Sparse Diagonal) y matrices comprimidas por bloques BCSR (Block Compressed Sparse Row). Estas implementaciones son muy dependientes de las características propias de la información, y su empleo en matrices dispersas de forma general, lejos de mejorar el rendimiento computacional, lo empeoran.

3.

Matrices dispersas empleando árboles balanceados

Existen otras estructuras de datos que pueden explotar las características de la información y ser empleadas para la implementación de matrices dispersas, tal es el caso de los árboles binarios autobalanceados o AVL. Los AVL son estructuras de datos con un alto rendimiento computacional. Tienen una complejidad espacial de O(n) (Knuth, 1997) donde n es la cantidad de elementos que almacena la estructura, por lo que espacialmente son eficientes para la implementación de las matrices dispersas. Las operaciones básicas de las estructuras de datos: insertar, buscar y eliminar, todas tienen un costo computacional en el peor de los casos de O(logn) (Knuth, 1997), lo cual permite mantener un costo computacional adecuado para la operaciones básicas con las matrices dispersas. La implementación de las matrices dispersas se basa en la implementación de un arreglo disperso de forma genérica. Un arreglo disperso es un árbol AVL que almacena en cada nodo, el índice o posición del arreglo y el valor contenido en el arreglo. El valor del índice o posición es el valor empleado para dar orden en el AVL. Una vez implementado un arreglo disperso genérico, declarar una matriz dispersa usando AVL, se declara como se declaran las matrices de forma normal, un arreglo de arreglo, en este caso un arreglo disperso de arreglo disperso, o un AVL de AVL. De forma similar se pueden definir matrices dispersas multidimensionales. En la figura 1 se representa de forma parcial la matriz A antes descrita. En la figura solo se ha representado el AVL (a la izquierda) que representa las filas de la matriz y el AVL (a la derecha) que contiene la información de las columnas de la cuarta fila. Como se planteó anteriormente la implementación de matrices dispersas tiene dos puntos claves, la selección de la estructura de datos a emplear y la implementación de las operaciones con las matrices. Como la construcción de los AVL

4

Figura 2: Esquema básico para la multiplicación de matrices es eficiente, consideramos no significativo el costo computacional de la construcción de las nuevas matrices dispersas para retornar los valores de las operaciones. Las operaciones con valores escalares, multiplicación y división son las operaciones más sencillas de implementar. Básicamente se recorre cada elemento del AVL correspondiente a las filas y para cada elemento se recorren los elementos contenidos en el AVL que contiene la información de las filas, realizando la operación de multiplicación o división por el escalar correspondiente. Ambas operaciones tienen un costo computacional O(n), siendo n la cantidad de valores no ceros o nulos de la matriz dispersa. Las operaciones directamente con matrices resultan un proceso un poco más complejo. De todas ellas hallar la traspuesta de una matriz es la operación más sencilla, pues simplemente se recorre cada elemento del AVL correspondiente a las filas y para cada elemento se recorren los elementos contenidos en el AVL que contiene la información de las filas, y los valores son almacenados en otra matriz dispersas intercambiando las filas por columnas. Para implementar la suma y la resta de dos matrices dispersas M1 y M2 , ambas implementadas de igual forma, se inicializa la nueva matriz M3 con los valores correspondientes de la matriz M1 . Luego se recorren todos los elementos de M2 , sumándolos o restándolos de los valores correspondientes en M3 . De esta forma se garantiza que se sumen o resten todos los valores existentes en ambas matrices sin ser necesario verificar los valores ceros o nulos. Estas operaciones tienen un costo computacional de O(max(m, n)), siendo m la cantidad de elementos no ceros o nulos de M1 y n la cantidad de elementos de M2 . La multiplicación de dos matrices dispersas es una operación que ha sido ampliamente estudiada (Pinar and Heath, 1999; Bell and Garland, 2009). En (McCourt et al., 2013) se propone un método para la multiplicación de matrices dispersas empleando la coloración de grafos y en (Yuster and Zwick, 2005) se propone un nuevo algoritmo para la multiplicación de matrices dispersas, basado en el algoritmo de multiplicación rápida de matrices. En la implementación de matrices dispersas propuesta en este trabajo se empleó el algoritmo de multiplicación de matrices básico como se muestra en la figura 2, que tiene una complejidad computacional de O(n3). Para el caso de las matrices dispersas se pueden hacer algunas optimizaciones en este algoritmo. Optimizando la operación de multiplicación teniendo en cuenta las características de las matrices dispersas se procede 5

Tabla 1: Descripción de los datos empleados para la validación Características HB/bcsstk23 HB/bcsstk29 Número de filas 3134 12992 Número de columnas 3134 12992 Valores no cero 45178 619488 Componentes fuertemente conexa 1 28 de la siguiente forma: Sean M1 y M2 las dos matrices dispersas que se desean multiplicar, M3 la matriz traspuesta de M2 y M4 una matriz dispersa nula. Se recorren todas las filas i de M1 , que contienen valores no ceros o nulos. Para cada una de estas filas i, se recorren las filas j de la matriz M3 , que contiene valores no ceros o nulos. En cada una de las correspondencias de (i, j) con valores no ceros o nulos en ambas filas, se recorren las columnas de las filas que contienen menos valores no ceros o nulos, multiplicándolos y acumulándolos con sus correspondientes valores de la otra fila, y finalmente almacenando el valor calculado en M4 [i, j]. La implementación de la multiplicación siguiendo este esquema, permite aprovechar las facilidades para recorrer los AVL, teniendo en cuanta las características de las matrices dispersas.

4.

Resultados y discusión

Para validar la propuesta de matrices dispersas empleando AVL, se implementó la estructura de datos y las operaciones en Java. Las operaciones fueron validadas con datos aleatorios validados por operaciones de fuerza bruta. La implementación propuesta se comparó con otras implementaciones de matrices dispersas en Java. Para la comparación se emplearon las matrices dispersas HB/bcsstk23 y HB/bcsstk29 (Duff et al., 1989; Davis and Hu, 2011), las cuales se describen en la tabla 1. En la comparación se empleó la biblioteca la4j (Kostyukov, 2011) con implementaciones de matrices dispersas empleando CSR y CSC y la biblioteca JavaML (Abeel, 2006). Para cada una de las implementaciones se midió el tiempo (en segundos) de inicialización de la matriz dispersa, así como el tiempo de duplicación de la matriz mediante suma y el tiempo de la multiplicación de la matriz por ella misma. Los resultados obtenidos se muestran en la tabla 2. De los resultados obtenidos en la tabla 2 podemos afirmar que la implementación de matrices dispersas empleando AVL tiene un mejor rendimiento que las implementaciones basadas en arreglos CSR y CSC.

5.

Conclusiones

Las matrices dispersas son una herramienta muy útil para el procesamiento computacional de grandes volúmenes de datos. Es necesario tener especial cuidado en el diseño de la estructura de datos para el almacenamiento de la información y

6

Tabla 2: Descripción de los datos empleados para la validación Datos AVL la4j CSR la4j CSC JavaML Carga de las matrices HB/bcsstk23 0.237 0.254 0.248 0.250 HB/bcsstk29 0.330 1.088 0.570 0.308 Duplicación de las matrices mediante suma HB/bcsstk23 0.326 0.556 0.563 HB/bcsstk29 0.987 9.873 10.153 Multiplicación de matrices HB/bcsstk23 3.666 487.773 573.594 4540.668 HB/bcsstk29 231.721 +5 horas +5 horas + 5horas en la implementación de las operaciones con las matrices, pues de obviarse estos dos elementos, puede empeorar el rendimiento computacional del procesamiento de la información. En este trabajo se propuso una implementación de matrices dispersas empleando árboles autobalanceados o AVL. Un AVL representa un arreglo disperso donde sólo se almacena la información, indexada por la posición dentro del arreglo donde se encuentra la información. Las matrices dispersas se definen como arreglos dispersos de arreglos dispersos, o sea AVL de AVL. La implementación realizada fue validada con las operaciones básicas de matrices, suma, resta, traspuesta y multiplicación. Esta demostró tener un mejor rendimiento respecto a otras implementaciones basadas en arreglos CSR y CSC. Se recomienda continuar el estudio de las operaciones sobre las matrices dispersas, para continuar optimizando la operación de multiplicación de matrices, así como lograr la incorporación de otras operaciones más complejas a la estructura de datos. También se recomienda su empleo en herramientas de algoritmos empleados en el campo de la Inteligencia Artificial como el caso de Weka y KEEL.

Referencias Abeel, T. (2006): Java Machine Learning Library. Bell, N. and M. Garland (2009): Implementing sparse matrix-vector multiplication on throughput-oriented processors. In: Proceedings of the 2009 ACM/IEEE Conference on Supercomputing. Davis, T. A. and Y. Hu (2011): The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software, 38:1–25. Duff, I. S.; R. G. Grimes; and J. G. Lewis (1989): Sparse matrix test problems. ACM Transactions on Mathematical Software, 15:1–14.

7

Golub, G. H. and C. F. Vanloan (1996): Matrix Computations. Baltimore, Johns Hopkins. Hidalgo, A. F.; J. G. D. Jalón; and A. Callejo (2014): Introducción de funciones BLAS y matrices Sparse en la dinámica de sistemas multicuerpo. In: XVIII Congreso Nacional de Ingeniería Mecánica. España. Knuth, D. (1997): The Art of Computer Programming, Addison-Wesley, chap. Sorting and Searching. Kostyukov, V. (2011): la4j Linear Algebra for Java. McCourt, M.; B. F. Smith; and H. Zhang (2013): Efficient Sparse Matrix-Matrix Products Using Colorings. SIAM Journal on Matrix Analysis and Applications. Mitchell, T. (1997): Machine Learning. McGraw Hill. Pinar, A. and M. T. Heath (1999): Improving performance of sparse matrix-vector multiplication. In: Proceedings of the 1999 ACM/IEEE Conference on Supercomputing. ACM, New York, USA. Pissanetzky, S. (1984): Sparse Matrix Technology. Academic Press. Stoer, J. and R Bulirsch (2002): Introduction to Numerical Analysis. Springer-Verlag, Berlin. Yuster, R. and U. Zwick (2005): Fast sparse matrix multiplication. ACM Transactions on Algorithms, 1:2–13.

8