Search

[ES] El auge en la aplicación de redes neuronales profundas (RNPs) en una gran variedad de campos científicos ha propiciado su uso no solo en servidores de cómputo sino también en dispositivos de bajo consumo. Los cálculos que se realizan tanto en entrenamiento como en inferencia de las RNPs se descomponen en núcleos de álgebra lineal y se extraen de bibliotecas especializadas como Intel MKL, BLIS, etc. Sin embargo, la memoria requerida por estas bibliotecas puede exceder de la capacidad máxima de estos pequeños dispositivos. Además, la gran variedad de hardware de bajo consumo hace prácticamente imposible contar con núcleos de cómputo optimizados para cada modelo. Una opción para reducir el coste de generación y mantenimiento de estas bibliotecas es la utilización de generadores de código automáticos como Apache TVM. Estas herramientas permiten desarrollar un solo código común para todos los dispositivos y posteriormente generar el código ensamblador para cada uno. Además, con TVM solamente se debe generar los núcleos necesarios para un modelo de RNP concreto evitando utilizar memoria del dispositivo con funcionalidad que no se utiliza para cada caso. En este proyecto se pretende generar núcleos computacionales para distintas arquitecturas de forma automática utilizando Apache TVM con el objetivo de reproducir las necesidades de los RNPs., [EN] The boom in the application of Deep Neural Networis (DNNs) in a wide variety of scientific fields has led to their use not only in compute-intensive servers but also in low-power devices. Many of the computations performed m RNPs, both in training and inference, are decomposed into linear algebra kernels and extracted from specialised libraries such as Intel Mkl or BLIS. However, the amount of memory required by these libraries can exceed the maximum capacity of these small devices. In addition, the wide variety of low-power hardware makes it virtually impossible to have optimised compute cores for each modeL One option to reduce the cost of generating and maintaming these libraries is the use of automatic code generators such as Apache TVM. These tools allow you to generate a single common code for all devices and then ,generate the assembly code for each device. With TVM, only the cores needed for a specific RNP model must be generated, avoiding the use of device memory with functionality that is not going to be used. This project aims to generate optimised computational kernels for different'architectures automatically using Apache TVM with the objective of reproducing the needs of RNP.

Se desarrolló un software educativo de Álgebra Lineal Numérica (ALN) amigable y con los más recientes desarrollos en esquemas de almacenamiento compacto o formatos comprimidos. Este software genera la posibilidad de contar con herramientas propias, manipulables e intervenibles para procesos de docencia e investigación. Contar con una herramienta computacional propia para la solución de problemas de álgebra lineal genera ventajas muy importantes, toda vez que se pueden conocer todos los detalles, hipótesis, restricciones, aplicaciones y bondades del software de primera mano, sin la dependencia de costosos servicios de soporte. La incorporación de elementos avanzados de almacenamiento, programación y aceleración de la solución de problemas de ALN en el software, permite no sólo resolver casos académicos, si no también problemas reales que llevan al usuario a comprender mejor la resolución de sistemas de manera eficiente y generalizada. Educational software of Numerical Linear Algebra (NLA) friendly was developed, with the last developments in compact storage formats or compressed formats. This software generates the possibility to have own tools, handling for teaching processes in undergraduate, research and advanced formation. Having a tool own computational for the solution of lineal algebra problems generates advantages, since, all the details, hypothesis, restrictions, applications and kindness of the software can be known of first hand, without necessity of requesting expensive support services. The incorporation of storage advanced elements, programming and acceleration of the solution of NLA problems in the software, not allow alone solve academic cases, but also real problems that induce the user to a better understanding of the problems in an efficient and widespread way.

Esta tesis se enmarca dentro del campo de la Alta Precisión Relativa (HRA) en Álgebra Lineal Numérica (ALN). Sus líneas maestras son dos. Por un lado, el diseño y análisis de algoritmos que permitan resolver problemas de Álgebra Lineal con más precisión de la habitual para matrices con estructura. Y por otro el estudio de la teoría específica de perturbaciones necesaria para tratar los problemas que nos ocupan. En nuestra investigación hemos tratado dos: La obtención de soluciones precisas del problema de mínimos cuadrados para matrices con estructura (Capítulo 3). La obtención de autovalores y autovectores precisos para matrices simétricas graduadas (Capítulo 4)....

The solution of a system of linear equations is by far the most important problem in Applied Mathematics. It is important both in itself and because it is an intermediate step in many other important problems. Gaussian elimination is nowadays the standard method for solving this problem numerically on a computer and it was the first numerical algorithm to be subjected to rounding error analysis. In 1948, Alan Turing published a remarkable paper on this topic: “Rounding-off errors in matrix processes” (Quart. J. Mech. Appl. Math. 1, pp. 287-308). In this paper, Turing formulated Gaussian elimination as the matrix LU factorization and introduced the “condition number of a matrix”, both of them fundamental notions of modern Numerical Analysis. In addition, Turing presented an error analysis of Gaussian elimination for general matrices that deeply influenced the spirit of the definitive analysis developed by James Wilkinson in 1961. Alan Turing’s work on Gaussian elimination appears in a fascinating period for modern Numerical Analysis. Other giants of Mathematics, as John von Neumann, Herman Goldstine, and Harold Hotelling were also working in the mid-1940s on Gaussian elimination. The goal of these researchers was to find an efficient and reliable method for solving systems of linear equations in modern “automatic computers”. At that time, it was not clear at all whether Gaussian elimination was a right choice or not. The purpose of this paper is to revise, at an introductory level, the contributions of Alan Turing and other authors to the error analysis of Gaussian elimination, the historical context of these contributions, and their influence on modern Numerical Analysis., La resolución de sistemas de ecuaciones lineales es sin duda el problema más importante en Matemática Aplicada. Es importante en sí mismo y también porque es un paso intermedio en la resolución de muchos otros problemas de gran relevancia. La eliminación Gaussiana es hoy en día el método estándar para resolver este problema en un ordenador y, además, fue el primer algoritmo numérico para el que se realizó un análisis de errores de redondeo. En 1948, Alan Turing publicó un artículo de gran relevancia sobre este tema: “Rounding-off errors in matrix processes” (Quart. J. Mech. Appl. Math. 1, pp. 287-308). En este artículo, Turing formuló la eliminación Gaussiana en términos de la factorización LU de una matriz e introdujo la noción de número de condición de una matriz, que son dos de las nociones más fundamentales del Análisis Numérico moderno. Además, Turing presentó un análisis de errores de la eliminación Gaussiana para matrices generales que influyó profundamente en el espíritu del análisis de errores definitivo desarrollado por Wilkinson en 1961. El trabajo de Alan Turing sobre la eliminación Gaussiana aparece en un periodo fascinante del Análisis Numérico moderno. Otros gigantes de las matemáticas como John von Neumann, Herman Goldstine y Harold Hotelling también realizaron investigaciones sobre la eliminación Gaussiana en la década de 1940-50. El objetivo de estos investigadores era encontrar un método eficiente y fiable para resolver sistemas de ecuaciones lineales en los ordenadores modernos que estaban desarrollándose por entonces. En aquella época, no estaba claro en absoluto si utilizar la eliminación Gaussiana era una elección adecuada o no. El propósito de este artículo es revisar, a nivel básico, las contribuciones realizadas por Alan Turing y otros investigadores al análisis de errores de la eliminación Gaussiana, el contexto histórico de esas contribuciones y su influencia en el Análisis Numérico moderno.

The proceeding at: The International Symposium "The Alan Turing Legacy" held in Madrid (Spain) in October 23-24, 2012. This symposium was organized and funded by the Real Academia de Ciencias Exactas, Físicas y Naturales of Spain and Fundación Ramón Areces. The solution of a system of linear equations is by far the most important problem in Applied Mathematics. It is important both in itself and because it is an intermediate step in many other important problems. Gaussian elimination is nowadays the standard method for solving this problem numerically on a computer and it was the first numerical algorithm to be subjected to rounding error analysis. In 1948, Alan Turing published a remarkable paper on this topic: "Rounding-off errors in matrix processes" (Quart. J. Mech. Appl. Math. 1, pp. 287-308). In this paper, Turing formulated Gaussian elimination as the matrix LU factorization and introduced the "condition number of a matrix", both of them fundamental notions of modern Numerical Analysis. In addition, Turing presented an error analysis of Gaussian elimination for general matrices that deeply influenced the spirit of the definitive analysis developed by James Wilkinson in 1961. Alan Turing's work on Gaussian elimination appears in a fascinating period for modern Numerical Analysis. Other giants of Mathematics, as John von Neumann, Herman Goldstine, and Harold Hotelling were also working in the mid-1940s on Gaussian elimination. The goal of these researchers was to find an efficient and reliable method for solving systems of linear equations in modern "automatic computers". At that time, it was not clear at all whether Gaussian elimination was a right choice or not. The purpose of this paper is to revise, at an introductory level, the contributions of Alan Turing and other authors to the error analysis of Gaussian elimination, the historical context of these contributions, and their influence on modern Numerical Analysis. La resolución de sistemas de ecuaciones lineales es sin duda el problema más importante en Matemática Aplicada. Es importante en sí mismo y también porque es un paso intermedio en la resolución de muchos otros problemas de gran relevancia. La eliminación Gaussiana es hoy en día el método estándar para resolver este problema en un ordenador y, además, fue el primer algoritmo numérico para el que se realizó un análisis de errores de redondeo. En 1948, Alan Turing publicó un artículo de gran relevancia sobre este tema: “Rounding-off errors in matrix processes” (Quart. J. Mech. Appl. Math. 1, pp. 287-308). En este artículo, Turing formuló la eliminación Gaussiana en términos de la factorización LU de una matriz e introdujo la noción de número de condición de una matriz, que son dos de las nociones más fundamentales del Análisis Numérico moderno. Además, Turing presentó un análisis de errores de la eliminación Gaussiana para matrices generales que influyó profundamente en el espíritu del análisis de errores definitivo desarrollado por Wilkinson en 1961. El trabajo de Alan Turing sobre la eliminación Gaussiana aparece en un periodo fascinante del Análisis Numérico moderno. Otros gigantes de las matemáticas como John von Neumann, Herman Goldstine y Harold Hotelling también realizaron investigaciones sobre la eliminación Gaussiana en la década de 1940-50. El objetivo de estos investigadores era encontrar un método eficiente y fiable para resolver sistemas de ecuaciones lineales en los ordenadores modernos que estaban desarrollándose por entonces. En aquella época, no estaba claro en absoluto si utilizar la eliminación Gaussiana era una elección adecuada o no. El propósito de este artículo es revisar, a nivel básico, las contribuciones realizadas por Alan Turing y otros investigadores al análisis de errores de la eliminación Gaussiana, el contexto histórico de esas contribuciones y su influencia en el Análisis Numérico moderno. This work was partially supported by the Ministerio de Economía y Competitividad of Spain through grant MTM-2009-09281. Publicado

Desde los inicios de la escritura se ha visto la necesidad de transmitir mensajes de manera que sean ocultos para aquellos que no sean el destinatario. Las t�ecnicas de cifrar mensajes han sido desarrolladas desde tiempos remotos, lo cual permitió la proliferación de diversos métodos, algunos de ellos aun no han logrado ser totalmente desmantelados, como es el caso del cifrado por sustitución monoalfabética. En este trabajo se establece un método, basado en la descomposición en valores singulares y herramientas computacionales, que permite mejorar los resultados obtenidos con otros métodos de descifrado basados en el análisis de frecuencias. / Abstract. From the beggining of writing we have seen the need to hide and transmit mes- sages in a way that they will be hidden to everybody but the receiver of the message. Techniques to encrypt messages have been developed from a long time ago, which al- lowed the proliferation for diverse methods, some of them have not been completely dismantled, like the monoalphabetic substitution encryption. In this work we are looking to establish a method, based on the singular value decomposition and computational tools, to improve the results obtained with other decoding methods. Maestría

The arrival of hardware accelerators has created a new gold rush to be the rst to deliver their promise of high performance for numerical applications. Since they are relatively hard to program, with limited language and compiler support, it is generally accepted that one needs to roll up one's sleeves and tough it out, not unlike the early days of distributed me- mory parallel computing (or any other period after the introduction of a drastically di erent architecture). In this paper we remind the community that while this is a noble endeavor, there is a lot of low hanging fruit that can be harvested easily. Picking this low hanging fruit bene ts the scienti c computing community immediately and prototypes the approach that the further optimizations may wish to follow. We demonstrate this by focusing on a widely used set of operations, the level-3 BLAS, targeting the NVIDIA family of GPUs La llegada de los aceleradores hardware ha creado una nueva fiebre del oro en ser los primeros en conseguir las prometidas elevadas prestaciones en aplicaciones numéricas. Ya que son relativamente difíciles de programar, con un soporte de lenguajes y compiladores limitado, se acepta que uno tiene que arremangarse la camisa y apretar los dientes, de forma no muy distinta a los primeros días de la programación de máquinas con memoria distribuida (o a cualquier otro periodo tras la introducción de una arquitectura drásticamente diferente). En este trabajo recordamos a la comunidad que mientras ésa es una actitud noble, hay un montón de fruta que puede ser recogida mucho más fácilmente. Recoger esta fruta beneficia a la comunidad científica inmediatamente y sirve para prototipar las aproximaciones que las subsiguientes optimizaciones deberían seguir. En este artículo demostramos lo anterior aplicándolo a un amplio conjunto de operaciones, el BLAS de nivel 3, orientado la la familia de GPUs de NVIDIA

The arrival of hardware accelerators has created a new gold rush to be the rst to deliver their promise of high performance for numerical applications. Since they are relatively hard to program, with limited language and compiler support, it is generally accepted that one needs to roll up one's sleeves and tough it out, not unlike the early days of distributed me- mory parallel computing (or any other period after the introduction of a drastically di erent architecture). In this paper we remind the community that while this is a noble endeavor, there is a lot of low hanging fruit that can be harvested easily. Picking this low hanging fruit bene ts the scienti c computing community immediately and prototypes the approach that the further optimizations may wish to follow. We demonstrate this by focusing on a widely used set of operations, the level-3 BLAS, targeting the NVIDIA family of GPUs La llegada de los aceleradores hardware ha creado una nueva fiebre del oro en ser los primeros en conseguir las prometidas elevadas prestaciones en aplicaciones numéricas. Ya que son relativamente difíciles de programar, con un soporte de lenguajes y compiladores limitado, se acepta que uno tiene que arremangarse la camisa y apretar los dientes, de forma no muy distinta a los primeros días de la programación de máquinas con memoria distribuida (o a cualquier otro periodo tras la introducción de una arquitectura drásticamente diferente). En este trabajo recordamos a la comunidad que mientras ésa es una actitud noble, hay un montón de fruta que puede ser recogida mucho más fácilmente. Recoger esta fruta beneficia a la comunidad científica inmediatamente y sirve para prototipar las aproximaciones que las subsiguientes optimizaciones deberían seguir. En este artículo demostramos lo anterior aplicándolo a un amplio conjunto de operaciones, el BLAS de nivel 3, orientado la la familia de GPUs de NVIDIA

La resolución de una gran cantidad de modelos presentes en la computación científica se basan en la solución de problemas del álgebra lineal numérica (ALN). Esta situación ha motivado fuertemente el desarrollo del área. En contraposición al importante desarrollo se ha incrementado en forma abrupta la complejidad de las estrategias de resolución, dificultando la comprensión por parte de los alumnos de los algoritmos utilizados. En este contexto la propuesta se centra en el desarrollo de una biblioteca de ALN de carácter didáctico. Por esta razón, la documentación es vasta y el código fue escrito pensando en su fácil lectura. Las rutinas implementadas son eficientes desde el punto de vista algorítmico. Pero determinadas mejoras de desempeño, propias de la implementación, fueron descartadas para mantener la legibilidad del código. Este documento presenta el diseño, las funcionalidades y la implementación realizada.

En el presente trabajo se han aplicado técnicas de computación paralela en la resolución de problemas de álgebra lineal numérica. El principal problema estudiado ha sido el de cálculo de valores propios de matrices estructuradas. Se ha estudiado el caso de las matrices tridiagonales (Capítulo 4), el de las matrices Toeplitz simétricas (Capítulo 6) y un caso de estudio particular proveniente de un problema de ingeniería (Capítulo 3). Se han aplicado técnicas de computación paralela tanto homogénea como heterogénea. Con el fin de disponer de una plataforma donde ejecutar nuestros algoritmos heterogéneos, se ha diseñado, ensamblado y configurado un clúster de computadores heterogéneos. El Capítulo 2 documenta dicha experiencia.

Sound transmission through partitions can be modelled as an acoustic fluid-elastic structure interaction problem. The block Gauss-Seidel iterative method is used in order to solve the finite element linear system of equations. The blocks are defined in a natural way, respecting the fluid and structural domains. The convergence criterion (spectral radius of iteration matrix smaller than one) is analysed and interpreted in physical terms by means of simple one-dimensional problems. This analysis highlights the negative influence on the convergence of a strong degree of coupling between the acoustic domains. A selective coupling strategy has been developed and successfully applied to problems with strong coupling (i.e. sound transmission through double walls).