Aplicación de la Descomposición de Valores Singulares a un Sistema de Recuperación de Información
Resumen
Este artículo se realiza en el marco de una investigación que tiene por objetivo optimizar un Sistema de Recuperación de Información, de desarrollo propio, mediante implementar y evaluar distintos algoritmos secuenciales y paralelos para resolver eficientemente la Descomposición de Valores Singulares. Dicho proceso comienza con la reducción de la matriz inicial a la forma bidiagonal. Estudios demuestran que la bidiagonalización puede consumir más del 70% del tiempo total del proceso. Por ello, como trabajo preliminar se han estudiado distintos métodos de bidiagonalización y se ha implementado un algoritmo basado en las transformaciones de Householder. El mismo se ha planteado con la suficiente flexibilidad como para ser adaptado fácilmente a otros algoritmos alternativos con el fin de realizar futuras implementaciones en arquitecturas paralelas, en particular las basadas en unidades de procesamiento gráfico.
Citas
M. Mamani Roque. “Descomposición en Valores Singulares y Análisis Semántico Latente”. Tesis de Maestría. Universidad Politécnica de Valencia, España, 2018.
S. Deerwester, S. Dumais, G. Furnas, T. Landauer & R. Harshman. “Indexing by latent semantic analysis”. Journal of the American Society for Information Science. 41(6):391–407. 1990.
Tolosa G. & Bordignon, F. “Introducción a la Recuperación de Información: Conceptos, modelos y algoritmos básicos”. Universidad Nacional de Luján, Argentina, 2008. Recuperado el 01/08/2019 de: http://eprints.rclis.org/12243/1/Introduccion-RI-v9f.pdf.
Berry, M., Dumais, S. & O’Brien, G. “Using Linear Algebra For Intelligent Information Retrieval”. Society for Industrial and Applied Mathematics, Review 37(4): 573-595. Philadelphia, USA, 1995.
L. Fortuna, G. Nunnari & A. Gallo. “Model order reduction techniques with applications in electrical engineering”. Springer-Verlag, 1992.
J. Demmel, M. Gu, S. Eisenstat, et al. “Computing the Singular Value Descomposition with Hight Relative Accuracy”. Linear Algebra and its Application, 299, 21-80, 1999.
Golub, G. & Van Loan, C. Matrix Computation. John Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Third Edition, 1996.
Ltaief, H., Kurzak, J. & Dongarra, J. “Parallel Two-Sided Matrix Reduction to Band Bidiagonal Form on Multicore Architectures”. IEEE Transactions on Parallel and Distributed Systems, 21(4): 417 – 423, 2010.
G. Golub & C. Reinsch. “Singular Value Decomposition and Least Squares Solutions”, Handbook Series Linear Algebra, 14: 403-420, 1970.
T. Chan. “An Improved Algorithm for Computing the Singular Value Decomposition”. ACM Transactions on Mathematical Software, 8(1): 72-83, 1982.
Sangwine, S. & Le Bihan, N. “Quaternion Singular Value Decomposition based on Bidiagonalization to a Real Matrix using Quaternion Householder Transformations” Applied Mathematics and Computation, ELSEVIER, 182(1): 727-738, 2006.
Da Silva Sanches de Campos, C. “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”. Tesis Doctoral. Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia, España, 2014.
Ralha, R. “One-sided reduction to bidiagonal form”. Linear Algebra and Its Applications, ELSEVIER, 358(1-3): 219-238, 2003.
Barlow, J., Bosner, N., Drmač, Z. “A new stable bidiagonal reduction algorithm”. Linear Algebra and Its Applications, ELSEVIER, 397: 35-84, 2005.
Guerrero López, D. “Algoritmos Paralelos para la Reducción de Sistemas Lineales de Control Estables”. Tesis doctoral. Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia, España, 2015.
Faverge M., Langou, J., Robert, Y. & Dongarra, J. “Bidiagonalization and R-Bidiagonalization: Parallel Tiled Algorithms, Critical Paths and Distributed-Memory Implementation”. IEEE Transactions on Parallel and Distributed Processing Symposium, 668 - 677, 2017.
Lahabar, S. & Narayanan, P. “Singular Value Decomposition on GPU using CUDA”. IEEE International Symposium on Parallel & Distributed Processing, 1-10, 2009.
Dong, T., Haidar, A., Tomov, S. & Dongarra, J. “Optimizing the SVD Bidiagonalization Process for a Batch of Small Matrices”. Linear Algebra and Its Applications, ELSEVIER, 108: 1008-1018, 2017.
Hernández Cortés, J. “Implementación paralela y heterogénea de la transformación de Householder y sus aplicaciones”.Tesis de Maestría. Departamento de Computación, Unidad Zacatenco, México, 2017.
