Implementación de mejoras en el tratamiento numérico e informático de problemas de gran tamaño de cálculo matricial de estructuras

• Autores: Isaac Lázaro Durán
• Directores de la Tesis: Ignacio López Torres (dir. tes.) , Angel Julián Martín Fernández (dir. tes.)
• Lectura: En la Universidad Politécnica de Madrid ( España ) en 2009
• Idioma: español
• Tribunal Calificador de la Tesis: Antonio Ruiz Perea (presid.) , Carlos Manzano del Moral (secret.) , Antonio Rúa Vieites (voc.) , Mariano Fernández López (voc.) , Juan Ignacio Sanz Fuentes (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • En esta Tesis se aborda el problema de la resolución, mediante equipos informáticos convencionales, de sistemas de ecuaciones lineales del tipo Ax=b, en los que el orden de la matriz A es muy grande ('varios' millones de filas y columnas, realizándose, en particular, una de las pruebas finales sobre un problema de dimensión 28 millones), Este tipo de problemas surge en numerosos ámbitos de la ciencia y la ingeniería, en particular en el Cálculo de Estructuras, si bien existen muchos otros campos donde los resultados de esta Tesis pueden ser directamente aplicados (estadística, economía, dinámica de poblaciones, genética, meteorología,...).

    En el Capítulo 1 se desarrolla el método de compresión EBnN (Existencia de Bloques no Nulos) propuesto, realizándose una comparación con otros métodos de almacenamiento (y compresión de información) de matrices de gran tamaño y escasamente pobladas (también llamadas matrices ralas). Se contrasta el método EBnN con los métodos CRS (Compressed Row Storage), CCS (Compressed Column Storage), BCRS (Block Compressed Row Storage), BCCS (Block Compressed Column Storage), CDS (Compressed Diagonal Storage), JDS (Jagged Diagonal Storage), y SKS (Skyline Storage). Estos métodos se basan en indexar listas que incrementan el número de accesos no continuos a la memoria de sistema. El método EBnN reduce estos efectos maximizando el rendimiento, obteniendo un coeficiente de compresión entorno a 9,96:1, ratio que mayora el de la mayoría de los anteriores métodos, y está situado a menos de 0,03 puntos por debajo del mejor de todos ellos, correspondiente a los métodos BCRS y BCCS con 9,99:1 de ratio de compresión.

    En el Capítulo 2 se diseña e implementa una clase, objeto de bajo nivel, capaz de almacenar informáticamente cualquier tipo de matriz según el método EBnB. Se establecen las estructuras de almacenamiento de datos, los modelos de memoria, y el interface de comunicación con el usuario.

    En el Capítulo 3 se desarrolla una clase, objeto de alto nivel, que dota al usuario final de capacidades operativas y ejecutivas de trabajo con matrices almacenadas según la clase desarrollada en el capítulo 2.

    En el Capítulo 4 se diseñan algoritmos informáticos, adaptados al método EBnN, de los principales métodos de resolución de sistemas lineales de ecuaciones basados en subespacios de Krylov, métodos directos, y métodos indirectos. Se implementan clases objeto para el método de Gauss con Pivote Parcial, factorizaciones LU, método Gauss-Seidel, método GMRES (Generalized Minimal Residual), método del Gradiente Conjugado, y métodos SOR(Successive Over Relaxation) y SSOR (Symmetric Successive Over Relaxation).

    En el Capítulo 5 se amplía el modelo anterior, dotándole de capacidades para la computación distribuida en clústeres de computadoras, generando un sistema cliente/servidor con comunicación vía sockets, contra un entorno de base de datos relacional, y soporte para miles de computadores. Se añade en este capítulo la implementación a través del modelo distribuido de un método de Gauss con pivote parcial.

    El Capítulo 6 se centra en el análisis del rendimiento del método. Se obtienen los costos de ejecución de todas las clases implementadas, mediante la aplicación de criterios asintóticos a las medidas.

    En los anexos se recogen los resultados pormenorizados de las pruebas, una descripción detallada de los entornos de prueba, un manual y los códigos de una aplicación completamente funcional, para el trabajo tanto en monopuesto, como en entornos distribuidos (con módulos cliente y servidor incluidos), con matrices de cualquier tamaño, utilizando el método EBnN. Se incluyen en la aplicación funciones para aplicar los diversos métodos de solución de sistemas lineales de ecuaciones estudiados.

    Como resultados obtenidos, citaremos (resumiendo) los siguientes:

    1.- Diez registros en la Agencia de la Propiedad Intelectual.

    2.- Modelo de almacenamiento de matrices EBnN.

    3.- Código de la clase para el almacenamiento de matrices según el modelo EBnN.

    4.- Código de la clase con funcionalidades de alto nivel optimizadas para el modelo EBnN (suma, producto, producto escalar, traza, normas, permutaciones, simetrías, trasposición, clonación).

    5.- Código de varias clases implementando los métodos de Gauss con Pivote Parcial, factorizaciones LU, de Gauss-Seidel, método GMRES, método del Gradiente Conjugado, y métodos SOR y SSOR, de forma optimizada para el método de almacenamiento EBnN propuesto.

    6.- Índices de rendimiento del método de forma comparada con otros métodos.

    7.- Costes asintóticos de las principales implementaciones de la Tesis.

    8.- Sistema cliente/servidor para trabajo distribuido sobre clústeres de miles de computadores.

    9.- Aplicación funcional para cálculo matricial mediante el modelo EBnN.