Algoritmos de Altas Prestaciones para el Cálculo de la Descomposición en Valores Singulares y su Aplicación a la Reducción de Modelos de Sistemas Lineales de Control

Abstract

P ARA calcular la descomposición en valores singulares (DVS) de una matriz real densa, los métodos tradicionales empiezan por reducir la matriz a una forma bidiagonal y seguidamente calculan la DVS de esa matriz bidiagonal. El proceso para reducir la matriz inicial a la forma bidiagonal es conocido como el método de la bidiagonalización, que en general consiste en la aplicación de sucesivas transformaciones de Householder, por la izquierda y por la derecha de la matriz. El hecho de que las transformaciones sean aplicadas por los dos lados de la matriz, repercute negativamente en los costes de comunicaciones de una implementación paralela destinada a sistemas de memoria distribuida. Ralha y Barlow presentaron dos nuevos métodos para la bidiagonalización de matrices densas en los que las transformaciones de Householder son aplicadas solamente por el lado derecho de la matriz. Esto permite de nir todas las operaciones en términos de las columnas de la matriz a transformar, facilitando así el desarrollo de implementaciones paralelas y que además reducen las comunicaciones necesarias. En esta tesis se ha realizado un estudio comparativo entre las implementaciones secuenciales y paralelas de los métodos presentados por Ralha y por Barlow, desarrolladas en el entorno de las librerías LAPACK y SCALAPACK, y las correspondientes rutinas de estas librerías. Como trabajo novedoso se han introducido algunas modi caciones en el método de Barlow con el objetivo de reducir el número de comunicaciones en la implementación paralela. Tras estas líneas de investigación, el paso siguiente es calcular la DVS de la matriz bidiagonal superior. Sin embargo, el problema de calcular la DVS de una matriz bidiagonal superior puede verse como el problema de calcular la descomposición en valores propios (DVP) de una matriz tridiagonal simétrica. Una vez calculada la DVP de la matriz tridiagonal simétrica es posible obtener la DVS de la matriz bidiagonal superior y con ella, la DVS de la matriz inicial. La principal motivación para esta estrategia es el desarrollo de una implementación paralela, sin comunicaciones, del método zeroinNR propuesto por Ralha en su tesis doctoral, para el cálculo de la DVP de matrices tridiagonales simétricas y el correspondiente estudio comparativo con la implementación paralela estándar, la cual contiene comunicaciones. Como ámbito de aplicación de la DVS se ha estudiado la reducción de modelos de sistemas lineales de control, basado en la diagonalización simultánea de los Gramianos de controlabilidad y de observabilidad, y nuestro enfoque va dirigido a la reducción a la forma bidiagonal superior del producto matricial sin calcular explícitamente ese producto y, para ello, se han desarrollado implementaciones secuenciales y paralelas del método propuesto por Golub, por Sølna y por van Dooren. Los resultados presentados en esta tesis han sido obtenidos en los recursos computacionales ofrecidos por el Grupo de Redes y Computación de Altas Prestaciones (GRyCAP) de la Universitat Politècnica de València (UPV) y por el consorcio SEARCH1 de la Universidad del Minho (UM).