Search

Documento de tesis de maestria ilustraciones, tablas Los métodos de kernel corresponden a un grupo de algoritmos de aprendizaje maquinal que hacen uso de una función de kernel para representar implicitamente datos en un espacio de alta dimensionalidad, donde sistemas de optimización lineal guíen a relaciones no lineales en el espacio original de los datos y por lo tanto encontrando patrones complejos dento de los datos. La mayor desventaja que tienen estos métodos es su pobre capacidad de escalamiento, pues muchos algoritmos basados en kernel requiren calcular una matriz de orden cuadrática respecto al numero de ejemplos en los datos, esta limitación ha provocado que los metodos de kernel sean evitados en configuraciones de datos a gran escala y utilicen en su lugar tecnicas como el aprendizaje profundo. Sin embargo, los metodos de kernel todavía son relevantes para entender mejor los métodos de aprendizaje profundo y ademas pueden mejorarlos haciendo uso de estrategias híbridas que combinen lo mejor de ambos mundos. El principal objetivo de esta tesis es explorar maneras eficientes de utilizar métodos de kernel sin una gran pérdida en precisión. Para realizar esto, diferentes enfoque son presentados y formulados, dentro de los cuales, nosotros proponemos la estrategía de aprendizaje utilizando budget, la cual es presentada en detalle desde una perspectiva teórica, incluyendo un procedimiento novedoso para la selección del budget, esta estrategia muestra en la evaluación experimental un rendimiento competitivo y mejoras respecto al método estandar de aprendizaje utilizando budget, especialmente cuando se seleccionan aproximaciones mas pequeñas, las cuales son las mas útiles en ambientes de gran escala. (Texto tomado de la fuente) Kernel methods are a set of machine learning algorithms that make use of a kernel function in order to represent data in an implicit high dimensional space, where linear optimization systems lead to non-linear relationships in the data original space and therefore finding complex patterns in the data. The main disadvantage of these methods is their poor scalability, as most kernel based algorithms need to calculate a matrix of quadratic order regarding the number of data samples. This limitation has caused kernel methods to be avoided for large scale datasets and use approaches such as deep learning instead. However, kernel methods are still relevant to better understand deep learning methods and can improve them through hybrid settings that combine the best of both worlds. The main goal of this thesis is to explore efficient ways to use kernel methods without a big loss in accuracy performance. In order to do this, different approaches are presented and formulated, from which, we propose the learning-on-a-budget strategy, which is presented in detail from a theoretical perspective, including a novel procedure of budget selection. This strategy shows, in the experimental evaluation competitive performance and improvements to the standard learning-on-a-budget method, especially when selecting smaller approximations, which are the most useful in large scale environments. Maestría Magíster en Ingeniería - Ingeniería de Sistemas y Computación Ciencias de la computación

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)....

RESUMEN: En este trabajo estudiamos algunos de los grandes problemas a los que se enfrenta el Álgebra Lineal Numérica, como el cálculo de los valores propios de una matriz, así como la resolución de sistemas de ecuaciones mediante distintos algoritmos. Se realiza un estudio sobre diversos algoritmos, implementándolos en Matlab. Para el análisis de resultados tomamos matrices aleatorias de tamaño 100, 500 y 1000 tanto para matrices reales como complejas, simétricas/hermíticas o no. Concluimos con una serie de resultados que consolidan lo estudiado en la teoría. ABSTRACT: In this work we deal with some of the most important problems in Numerical Linear Algebra, such as the computation of eigenvalues and the solution of linear systems of equations, using different approaches. We describe different algorithms, and program them in Matlab. For the analysis of the results we use collections of random matrices of sizes 100, 500 and 1000, and we experiment with real and complex matrices, both in the case that they are symmetric (hermitian) or non--symmetric (non--hermitian). Our conclusions support the theoretical properties of the algorithms. Grado en Matemáticas

Esta tesis tiene el objetivo de estudiar aplicaciones de la transformada wavelet discreta (DWT) al álgebra lineal numérica. Se hace un estudio de las distintas variantes de paralelización de la DWT y se propone una nueva variante paralela, en memoria distribuida, con distribuciones de datos orientadas a bloques de matrices, como la 2DBC de ScaLAPACK. La idea es que la DWT en muchos casos es una operación intermedia y debe ajustarse a las distribuciones de datos que se estén usando. Se define y demuestra una forma de calcular exactamente la cantidad de elementos que debe comunicar cada procesador para que se puedan calcular de forma independiente todo los coeficientes wavelet en una cantidad de niveles determinada. Finalmente se propone una variante específica, más eficiente, para el cálculo de la DWT-2D cuando se aplica como paso previo a la resolución de un sistema de ecuaciones distribuido 2DBC, considerando una permutación de las filas y columnas del sistema que minimiza las comunicaciones. Otro de los aportes de esta tesis es el de considerar como un caso típico, el cálculo de la DWT-2D no estándar en matrices dispersas, proponemos algoritmos para realizar esta operación sin necesidad de construir explícitamente la matriz wavelet. Además tenemos en cuenta el fenómeno de rellenado (fill-in) que ocurre al aplicar la DWT a una matriz dispersa. Para ello exploramos con los métodos de reordenamiento clásicos de grado mínimo y de reducción a banda. De forma adicional sugerimos como pueden influir esos reordenamientos a la convergencia de los métodos multimalla ya que ocurre una redistribución de la norma de la matriz hacia los niveles inferiores de la representación multi-escala, lo que garantizaría una mejor compresión. El campo de aplicación de la transformada wavelet que se propone es la resolución de grandes sistemas de ecuaciones lineales., Acevedo Martínez, L. (2009). Computación paralela de la transformada Wavelet; Aplicaciones de la transformada Wavelet al Álgebra Lineal Numérica [Tesis doctoral no publicada]. Universitat Politècnica de València. doi:10.4995/Thesis/10251/7107.

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.

El modelamiento matemático ha sido siempre fundamental para las ciencias y las ingenierías pero ha cobrado mucha mas importancia desde que se empezaron a usar computadores en gran escala. LAPACK (Linear Algebra Package) es una colección de subrutinas escritas en FORTRAN 77 para resolver problemas matemáticos comunes que surgen a partir del modelamiento y que se enmarcan en el campo del álgebra lineal numérica.

[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.

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.

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.

In many research areas, such as computer vision, image processing, pattern recognition, or systems identification, the segmentation of heterogeneous high-dimensional data sets is one of the most common and important tasks. Based on the subspace clustering approach, the Generalized Principal Component Analysis (GPCA) is an algebraic-geometric method that attempts to perform this task. However, due to GPCA requires performing matrix decompositions whose computational cost is cubic with respect to the size of the matrix (in the worst case), the data segmentation becomes expensive when such size is very large. Consequently, the present thesis work is intended to support our initial hypothesis: it is possible to find matrix decompositions via randomized schemes that not only reduce the computational costs, but also they maintain the effectiveness of their results. This allows GPCA to manipulate both large and heterogeneous high-dimensional data sets, and thus GPCA can enter into domains where its applicability has been partially or totally restricted.

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

El presente proyecto puede resumirse en tres etapas o tres grupos de actividades en las que el alumno ha desarrollado su trabajo: Implementación y depuración del algoritmo SSVD definitivo en lenguaje FORTRAN. La implementación se ha llevado a cabo en el entorno VISUAL STUDIO 2005 de Microsoft. Se ha utilizado el lenguaje FORTRAN por su extendido uso en Álgebra Lineal Numérica para la programación de algoritmos formales debido a su eficiencia y potencia. Es también el lenguaje en el que están escritas las rutinas de la librería LAPACK (Linear Algebra Package). A lo largo del proyecto también se ha hecho uso de MATLAB como herramienta auxiliar por su mayor versatilidad y sencillez de utilización. Realización de experimentos numéricos con el algoritmo SSVD. Se han realizado extensivos experimentos numéricos con el algoritmo SSVD. Como consecuencia se ha obtenido la descomposición espectral para varios centenares de miles de matrices, matrices generadas aleatoriamente controlando diversos parámetros y matrices especialmente diseñadas para llevar al límite la precisión del algoritmo SSVD. Los resultados han sido analizados cuidadosamente comprobando que reproducen fielmente lo que la teoría predice. Presentación y documentación del algoritmo SSVD. El trabajo que se resume en este documento: ² Presentación del algoritmo SSVD a la comunidad no especializada. ² Repaso de los principios fundamentales del Álgebra Lineal (AL) y del Álgebra Lineal Numérica (ALN) necesarios para comprender el algoritmo. ² Descripción de los fundamentos en los que el algoritmo SSVD se basa, desde el punto de vista del AL y el ALN. ² Descripción de los experimentos numéricos realizados y presentación de los resultados. Ingeniería Industrial

La teoría de perturbaciones constituye un tópico de estudio dentro del análisis matricial y la teoría de operadores. Asociados a este tópico, se encuentran los temas clásicos de álgebra lineal numérica y teoría de la aproximación. En este contexto, podemos pensar en el estudio de la sensibilidad de los valores de Ritz y los cocientes de Rayleigh de matrices autoadjuntas, es decir, los cambios en los autovalores de compresiones de matrices autoadjuntas, que es un campo de investigación sólido y bien establecido en estas áreas., Facultad de Ciencias Exactas

Esta tesis doctoral es un compendio de 11 artículos científicos. El tema principal de la tesis es el Álgebra Lineal Numérica, con énfasis en dos clases de matrices estructuradas: las matrices totalmente positivas y las M-matrices. Para algunas subclases de estas matrices, es posible desarrollar algoritmos para resolver numéricamente varios de los problemas más comunes en álgebra lineal con alta precisión relativa independientemente del número de condición de la matriz. La clave para lograr cálculos precisos está en el uso de una parametrización diferente que represente la estructura especial de la matriz y en el desarrollo de algoritmos adaptados que trabajen con dicha parametrización.Las matrices totalmente positivas no singulares admiten una factorización única como producto de matrices bidiagonales no negativas llamada factorización bidiagonal. Si conocemos esta representación con alta precisión relativa, se puede utilizar para resolver ciertos sistemas de ecuaciones y para calcular la inversa, los valores propios y los valores singulares con alta precisión relativa. Nuestra contribución en este campo ha sido la obtención de la factorización bidiagonal con alta precisión relativa de matrices de colocación de polinomios de Laguerre generalizados, de matrices de colocación de polinomios de Bessel, de clases de matrices que generalizan la matriz de Pascal y de matrices de q-enteros. También hemos estudiado la extensión de varias propiedades óptimas de las matrices de colocación de B-bases normalizadas (que en particular son matrices totalmente positivas). En particular, hemos demostrado propiedades de optimalidad de las matrices de colocación del producto tensorial de B-bases normalizadas.Si conocemos las sumas de filas y las entradas extradiagonales de una M-matriz no singular diagonal dominante con alta precisión relativa, entonces podemos calcular su inversa, determinante y valores singulares también con alta precisión relativa. Hemos buscado nuevos métodos para lograr cálculos precisos con nuevas clases de M-matrices o matrices relacionadas. Hemos propuesto una parametrización para las Z-matrices de Nekrasov con entradas diagonales positivas que puede utilizarse para calcular su inversa y determinante con alta precisión relativa. También hemos estudiado la clase denominada B-matrices, que está muy relacionada con las M-matrices. Hemos obtenido un método para calcular los determinantes de esta clase con alta precisión relativa y otro para calcular los determinantes de las matrices de B-Nekrasov también con alta precisión relativa. Basándonos en la utilización de dos matrices de escalado que hemos introducido, hemos desarrollado nuevas cotas para la norma infinito de la inversa de una matriz de Nekrasov y para el error del problema de complementariedad lineal cuando su matriz asociada es de Nekrasov. También hemos obtenido nuevas cotas para la norma infinito de las inversas de Bpi-matrices, una clase que extiende a las B-matrices, y las hemos utilizado para obtener nuevas cotas del error para el problema de complementariedad lineal cuya matriz asociada es una Bpi-matriz. Algunas clases de matrices han sido generalizadas al caso de mayor dimensión para desarrollar una teoría para tensores extendiendo la conocida para el caso matricial. Por ejemplo, la definición de la clase de las B-matrices ha sido extendida a la clase de B-tensores, dando lugar a un criterio sencillo para identificar una nueva clase de tensores definidos positivos. Hemos propuesto una extensión de la clase de las Bpi-matrices a Bpi-tensores, definiendo así una nueva clase de tensores definidos positivos que puede ser identificada en base a un criterio sencillo basado solo en cálculos que involucran a las entradas del tensor. Finalmente, hemos caracterizado los casos en los que las matrices de Toeplitz tridiagonales son P-matrices y hemos estudiado cuándo pueden ser representadas en términos de una factorización bidiagonal que sirve como parametrización para lograr cálculos con alta precisión relativa.

The dissemination of multi-core architectures and the later irruption of massively parallel devices, led to a revolution in High-Performance Computing (HPC) platforms in the last decades. As a result, Field- Programmable Gate Arrays (FPGAs) are re-emerging as a versatile and more energy-efficient alternative to other platforms. Traditional FPGA design implies using low-level Hardware Description Languages (HDL) such as VHDL or Verilog, which follow an entirely different programming model than standard software languages, and their use requires specialized knowledge of the underlying hardware. In the last years, manufacturers started to make big efforts to provide High-Level Synthesis (HLS) tools, in order to allow a grater adoption of FPGAs in the HPC coimnunity. Our work studies the use of multi-core hardware and different FPGAs to address Numerical Linear Algebra (NLA) kernels such as the general matrix multiplication (GEMM) and the sparse matrix-vector multiplication (SpMV). Specifically, we compare the behavior of fine-tuned kernels in a multi-core CPU processor and HLS implementations on FPGAs. We perform the experimental evaluation of our implementations on a low-end and a cutting-edge FPGA platform, in terms of runtime and energy consumption, and compare the results against the Intel MKL library in CPU., La masificación de arquitecturas de multinúcleo y la posterior irrupción de dispositivos masivamente paralelos produjeron una revolución en las plataformas de computación de altas prestaciones. Como resultado, las FPGAs (del inglés, Field-Programmable Gate Arrays) están resurgiendo como una alternativa versátil y más eficiente desde el punto de vista energético. El flujo de diseño tradicional en FPGAs implica el uso de lenguajes de descripción de hardware de bajo nivel, como VHDL o Verilog, que siguen un modelo de programación completamente diferente al de los lenguajes de software estándar, y su uso requiere un conocimiento especializado del hardware subyacente. En los últimos años, los fabricantes comenzaron a hacer grandes esfuerzos para proporcionar herramientas de síntesis de alto nivel, con el fin de permitir una mayor adopción de las FPGAs en la comunidad de computación de altas prestaciones. Nuestro trabajo estudia el uso de plataformas multinúcleo y diferentes FPGAs para abordar problemas de álgebra lineal numérica (NLA) como la multiplicación de matrices (GEMM) y la multiplicación de matriz dispersa por vector (SpMV). Específicamente, comparamos el comportamiento de implementaciónes optimizadas para un procesador multinúcleo y las im- plementaciones con síntesis de alto nivel en FPGAs. Realizamos la evaluación experimental de nuestras im- plementaciones en una plataforma FPGA de gama baja y otra de gama alta, analizando tiempo de ejecución y consumo de energía, y comparamos los resultados con la biblioteca Intel MKL para CPU., Facultad de Informática

[ES] El aprendizaje automático mediante redes neuronales profundas ha experimentado un gran auge en la última década, principalmente por la combinación de varios factores, entre los que se incluyen la avalancha de datos para entrenar este tipo de sistemas (big data), una mayor capacidad de los sistemas de computación (procesadores gráficos de NVIDIA, TPUs de Google, etc.), los avances en técnicas algorítmicas de aprendizaje (por ejemplo, redes de tipo transformer para procesamiento del lenguaje), y la disponibilidad de entornos amigables para la tarea. En la actualidad existen diferentes paquetes de software para el entrenamiento de redes neuronales profundas sobre clusters de computadores (TensorFlow de Google y PyTorch de Facebook), e incluso los mismos paquetes tienen versiones especializadas (TensorFlow Lite, NVIDIA RT, QNNPACK, etc.) para realizar el proceso de inferencia sobre procesadores de bajo consumo, como los que pueden encontrarse en un móvil Android o iOS o en un vehículo sin conductor. Muchos de los sistemas tratan redes neuronales convolucionales, especialmente aquellos que tratan con imágenes. A un nivel más bajo de detalle podemos observar que el entrenamiento y la inferencia en las capas convolucionales de las redes neuronales mencionadas aparece un producto matricial con características particulares, bien definidas y que requieren de un tratamiento especial cuando se trata de su optimización. Este trabajo de fin de máster trata de la optimización de esta operación, en particular, sobre arquitectura ARM, cuyo procesador multinúcleo puede encontrarse en gran parte de los dispositivos de bajo consumo donde se pretende ejecutar la inferencia de una red previamente entrenada. La optimización planteada está inspirado en un paquete de rutinas optimizadas de álgebra lineal numérica denominado BLIS, de donde se obtienen los algoritmos básicos sobre los que se realiza el trabajo. El proyecto permitirá al estudiante adquirir un buen conocimiento de los aspectos computacionales relacionados con el proceso inferencia con redes neuronales profundas, así como profundizar en la interacción entre el algoritmo y la arquitectura del procesador y cómo esta determina el rendimiento., [EN] The use of machine learning in deep neural networks has experienced a boom in the last decade, mainly due to a combination of several factors, including the abundance of data to train such systems (big data), increased computing power (NVIDIA graphics processors, Google TPUs, etc.), advances in algorithmic learning techniques (transformer neural networks for language processing) and the availability of user-friendly environments for the task. There are currently different software packages for training deep neural networks on computer clusters (TensorFlow and PyTorch) and even the same packages have specialized versions (TensorFlow Lite, NVIDIA RT, QNNPACK, etc.) to perform the inference process on low-power processors, such as those that can be found in an Android or iOS mobile phone or in a driverless car. Many of the systems deal with convolutional neural networks, especially those that deal with images. At a lower level of detail, we can observe that the training and inference in the convolutional layers of the aforementioned neural networks result in a matrix product with particular, well-defined characteristics that require special treatment when it comes to optimization. This master's thesis deals with the optimization of this operation, in particular, on an ARM architecture, whose multicore processor can be found in most of the low-power devices where it is intended to execute the inference of a previously trained network. The proposed optimization is inspired by a package of optimized numerical linear algebra routines called BLIS, from which the basic algorithms on which the work is carried out are obtained. The project will allow the student to acquire a good knowledge of the computational aspects related to the inference process with deep neural networks, as well as to deepen the interaction between the algorithm and the architecture of the processor and how this determines the performance.

Traballo Fin de Grao en Matemáticas. Curso 2018-2019 [ES] En esta memoria se describen los métodos directos de factorización de matrices basados en estrategias de pivoteo que se aplican a la resolución de sistemas de ecuaciones lineales. En concreto se verá la factorización LU, derivada de la eliminación de Gauss, con pivote parcial y total, la factorización de Cholesky con pivote y la factorización QR con matrices de Householder y pivoteo de columnas. Cuando los métodos numéricos se implementan en el ordenador pueden aparecer problemas de estabilidad numérica en las versiones básicas, que los hacen inadecuados para resolver sistemas mal condicionados o con perturbaciones en los datos. Por ello es necesario introducir estrategias de pivoteo que eliminan o reducen, en la mayoría de los casos, esos comportamientos indeseables. Una vez calculada la factorización se puede resolver con mucho menor coste un gran número de problemas del álgebra lineal numérica. Se incluyen las aplicaciones al cálculo de inversas, determinantes y rango de una matriz. [EN] This work describes the direct methods of pivoting based matrix decompositions in order to solve linear systems. Specifically, the LU decomposition will be derived from the Gaussian elimination, and partial and total pivoting will be introduced. For the Cholesky decomposition, the symmetric pivoting will be implemented and for Householder QR decomposition, the column pivoting will be carried out. The use of these strategies is necessary in computer calculations because the basic direct methods exhibit numerical instabilities in the ill-conditioned case. These problems are avoided in most cases by pivoting. Knowing a matrix decomposition, it will be very easy to obtain the rank, the determinant and the inverse.

The problem of computing eigenvalues, eigenvectors, and invariant subspaces of symplectic matrices plays a major role in many applications, in particular in control theory when the focus is on discrete systems. If standard numerical methods for the solution of the symplectic eigenproblem are applied that do not take into account the special symmetry structure of the problem, then not only the existing symmetry in the spectrum of symplectic matrices may be lost in finite precision arithmetic, but more importantly other relevant intrinsic features or invariants may be ignored although they have a major influence in the corresponding computed eigenvalues. The importance of structure-preservation has been acknowledged in the Numerical Linear Algebra community since several decades, and consequently many algorithms have been developed for the symplectic eigenvalue problem that preserve the given structure at each iteration step. The error analysis for such algorithms requires a corresponding stucture-preserving perturbation theory. This is the general framework in which this dissertation can be placed. In this work, a first order perturbation theory for eigenvalues of real or complex Jsymplectic matrices under structure-preserving perturbations is developed. Since the class of symplectic matrices has an underlying multiplicative structure, Lidskii’s classical formulas for small additive perturbations of the form b A = A+εB cannot be applied directly, so a new multiplicative perturbation theory is first developed: given an arbitrary square matrix A, we obtain the leading terms of the asymptotic expansions in the small, real parameter ε of multiplicative perturbations b A(ε) = (I +εB +· · · )A(I +εC +· · · ) of A for arbitrary matrices B and C. The analysis is separated in two complementary cases, depending on whether the unperturbed eigenvalue is zero or not. It is shown that in either case the leading exponents are obtained from the partial multiplicities of the eigenvalue of interest, and the leading coefficients generically involve only appropriately normalized left and right eigenvectors of A associated with that eigenvalue, with no need of generalized eigenvectors. It should be noted that, although initially motivated by the needs for the symplectic case, this multiplicative (unstructured) perturbation theory is of independent interest and stands on its own. After showing that any small structured perturbation bS of a symplectic matrix S can be written as bS = bS(ε) = (I + εB + · · · ) S with Hamiltonian first-order coefficient B, we apply the previously obtained Lidskii-like formulas for multiplicative perturbations to the symplectic case by exploiting the particular connections that symplectic structure induces in the Jordan form between normalized left and right eigenvectors. Special attention is given to eigenvalues on the unit circle, particularly to the exceptional eigenvalues ±1, whose behavior under structure-preserving perturbations is known to differ significantly from the behavior under arbitrary ones. Also, several numerical examples are generated Although the approach described above via multiplicative expansions works in most situations, there is a very specific one, the one we call the nongeneric case, which requires a separate, completely different analysis. It corresponds to the case in which, in the absence of structure, the rank of the perturbation would break an odd number of oddsized Jordan blocks corresponding to the eigenvalue either 1 or −1. Since this is not allowed by symplecticity, one among that odd number of Jordan blocks does not break, but increases its size by one becoming an even-sized block. This very special behavior lies outside of the theory developed for what we might call the generic cases, and requires a completely different perturbation analysis, based on Newton diagram techniques like the one performed to obtain the multiplicative expansions. The main difference with the previous expansions is that in this nongeneric case the leading coefficients depend not only on eigenvectors, but also on first generalized Jordan vectors. El problema de calcular autovalores, autovectores y subespacios invariantes de matrices simplécticas juega un papel crucial en muchas aplicaciones, en particular en la Teoría de Control cuando ésta se centra en sistemas discretos. Si para resolver el problema simpléctico de autovalores se emplean métodos numéricos estándar que no tienen en cuenta la simetría especial del problema, entonces no solo se perderá en aritmética finita la simetría natural del espectro de las matrices simplécticas, sino que, aún más importante, podemos estar ignorando otras características o invariantes intrínsecas que tienen una influencia crucial en los correspondientes autovalores calulados. La importancia de preservar la estructura ha sido reconocida por la comunidad del Álgebra Lineal Numérica desde hace varias décadas y, en consecuencia, se han desarrollado diversos algoritmos para el problema simpléctico de autovalores que mantienen la estructura simpléctica en cada paso del proceso iterativo. El análisis de errores de tales algoritmos demanda una teoría de perturbación asociada que también preserve la estructura. Este es el marco general en el que se puede inscribir esta tesis doctoral. En este trabajo se desarrolla una teoría de perturbación de autovalores de matrices J-simplécticas frente a perturbaciones que preservan la simplecticidad de la matriz. Dado que la clase de matrices simplécticas tiene una estructura multiplicativa subyacente, las fórmulas clásicas de Lidskii para perturbaciones aditivas pequeñas de la forma b A = A + εB no se pueden aplicar de manera directa, de modo que desarrollamos una nueva teoría de perturbación multiplicativa: dada cualquier matriz cuadrada A, obtenemos el término director del desarrollo asintótico en el parámetro real (y pequeño) ε de autovalores de perturbaciones multiplicativas b A(ε) = (I + εB + · · · )A(I + εC + · · · ) de A para matrices arbitrarias B y C. El análisis se separa en dos casos complementarios, dependiendo de que el autovalor a perturbar sea nulo o no. Se demuestra que en ambos casos los exponentes directores se obtienen a partir de las multiplicidades parciales del autvalor bajo estudio, y que los coeficientes directores solo involucran genéricamente autovectores derechos e izquierdos adecuadamente normalizados, sin necesidad de autovalor generalizado alguno. Debe señalarse que, aunque inicialmente motivados por la necesidad para el caso simpléctico, esta teoría (no estructurada) de perturbación multiplicativa reviste interés per se independientemente de su aplicación al caso simpléctico. Tras mostrar que cualquier perturbación estructurada peque na bS de una matriz simpléctica S puede escribirse como bS = bS(ε) = (I + εB + · · · ) S con coeficiente de primer orden B Hamiltoniano, aplicamos las fórmulas tipo Lidskii obtenidas para perturbaciones multiplicativas al caso simpléctico, explotando la particular conexión que la estructura simpléctica induce entre los autovectores derechos e izquierdos normalizados por la forma de Jordan. Especial atención se le dedica a los autovalores sobre el círculo unidad, particularmente a los autovalores excepcionales ±1, cuyo comportamiento frente a perturbaciones estructuradas es sabido que difiere muy significativemente del comportamiento frente a perturbaciones arbitrarias. Además, presentamos varios ejemplos numéricos que ilustran (y confirman) los desarrollos asintóticos obtenidos. Aunque el enfoque que acabamos de describir via desarrollos multiplicativos funciona en la mayor parte de las situaciones, hay una muy específica, la que llamamos el caso no-genérico, que requiere de un análisis por separado, completamete distinto del anterior. Corresponde al caso en que, en ausencia de estructura, el rango de la perturbación rompería un número impar de bloques de Jordan de tamaño impar asociados a uno de los autovalores 1 ó −1. Como esto es incompatible con la simplecticidad, uno de entre los bloques de tamaño impar no se rompe, sino que incrementa en uno su dimensión, conviertiéndose en un bloque de Jordn de tamaño par. Este comportamiento tan especial no está explicado por la teoría de lo que podríamos llamar los casos ‘genéricos’ , y requiere de un análisis de perturbación completamente distinto, basado en técnicas del Diagrama de Newton, como el llevado a cabo para obtener los desarrollos multiplicativos. La diferencia principal con los desarrollos anteriores es que en el caso no genérico los coeficientes directores dependen no solo de autovectores, sino también de vectores primeros generalizados de Jordan. Este trabajo ha sido desarrollado en el Departamento de Matemáticas de la Universidad Carlos III de Madrid (UC3M) bajo la dirección del profesor Julio Moro Carreño. Se contó con una beca de la UC3M de ayuda al estudio de máster y posteriormente con un contrato predoctoral de la UC3M. Adicionalmente se recibió ayuda parcial del proyecto de investigación: “Matemáticas e Información Cuántica: de las Álgebras de Operadores al Muestreo Cuántico” (Ministerio de Economía y Competitividad de España, Número de proyecto: MTM2014-54692-P). Programa de Doctorado en Ingeniería Matemática por la Universidad Carlos III de Madrid Presidente: Luis Alberto Ibort Latre.- Secretario: Rafael Cantó Colomina.- Vocal: Francisco Enrique Velasco Angulo

En el presente trabajo de tesis, utilizamos algunos algoritmos para calcular los autovalores máximo y mínimo de matrices autoadjuntas. Si bien es cierto, el problema del autovalor es uno de los problemas que resuelve el Álgebra Lineal Numérica y existen algoritmos de métodos iterativos que lo hacen, lo que investigamos en el presente trabajo es como poder acelerar la convergencia de estos algoritmos a partir de la obtención de una región de acotación de los autovalores de una matriz A (autoadjunta). Es decir, podemos obtener un autovalor aproximado el mismo que nos ayudará a determinar su autovector asociado. Este puede ser utilizado para iniciar los procesos iterativos para calcular el autovalor máximo de una matriz A. Tesis

Durante el período comprendido entre abril de 2015 y febrero de 2016, he aprobado con final las materias: Funciones Reales, Álgebra Lineal Numérica, Álgebras de Hilbert y Introducción a las Representaciones Topológicas. Me encuentro preparando los respectivos finales de Teoria de Representaciones para semirreticulos distributivos y Variable Compleja. Por otra parte, estoy finalizando la redacción de un capítulo de mi tesis, donde se estudian los operadores de Moisil sobre álgebras de Hilbert con ínfimo. En le que presentamos un Toerema de Representación por medio de algebras simples, dado que las álgebras subdiretamente iredducibles se probaron ser simple, y por lo tanto, la variedad es semisimple. Estos resultado, permitieron presentar un Cálculo estilo Hilbert correcto y completo, lo que dió respuesta sobre uno de nuestros objetivos generales. La labor desarrollada permitió estudiar el fragmento intuisionista de la lógica de las álgebras de Lukasiewicz-Moisil. En efecto, es bien sabido que en las álgebras de Lukasiewiwz-Moisil (LM-álgebras) de orden n < 5, se les puede definir una implicación de Lukasiewicz y una implicación de Heyting, y en el caso general solo se puede definir la de Heyting. Por otra parte, las implicaciones de Heyting que se pueden definir en cadenas, coinciden con las implicación de Gödel (ver [3]) (o implicación trivial de Hilbert), este hecho permite axiomatizar a los respectivos fragmentos implicativos de las LM-álgebras, por medio de Algebras de Hilbert n-valentes . Estos resultados están motivados en los trabajos fundacionales de M. Canals Frou y A. V. Figallo (ver [3, 4]). Los aportes fueron comunicados en la Reunión Anual de la Unión Matemática Argentina (ver [7]) y están siendo preparado en formato de paper para ser sometido a una revista internacional con referato.

Esta tesis tiene el objetivo de estudiar aplicaciones de la transformada wavelet discreta (DWT) al álgebra lineal numérica. Se hace un estudio de las distintas variantes de paralelización de la DWT y se propone una nueva variante paralela, en memoria distribuida, con distribuciones de datos orientadas a bloques de matrices, como la 2DBC de ScaLAPACK. La idea es que la DWT en muchos casos es una operación intermedia y debe ajustarse a las distribuciones de datos que se estén usando. Se define y demuestra una forma de calcular exactamente la cantidad de elementos que debe comunicar cada procesador para que se puedan calcular de forma independiente todo los coeficientes wavelet en una cantidad de niveles determinada. Finalmente se propone una variante específica, más eficiente, para el cálculo de la DWT-2D cuando se aplica como paso previo a la resolución de un sistema de ecuaciones distribuido 2DBC, considerando una permutación de las filas y columnas del sistema que minimiza las comunicaciones. Otro de los aportes de esta tesis es el de considerar como un caso típico, el cálculo de la DWT-2D no estándar en matrices dispersas, proponemos algoritmos para realizar esta operación sin necesidad de construir explícitamente la matriz wavelet. Además tenemos en cuenta el fenómeno de rellenado (fill-in) que ocurre al aplicar la DWT a una matriz dispersa. Para ello exploramos con los métodos de reordenamiento clásicos de grado mínimo y de reducción a banda. De forma adicional sugerimos como pueden influir esos reordenamientos a la convergencia de los métodos multimalla ya que ocurre una redistribución de la norma de la matriz hacia los niveles inferiores de la representación multi-escala, lo que garantizaría una mejor compresión. El campo de aplicación de la transformada wavelet que se propone es la resolución de grandes sistemas de ecuaciones lineales.

Estre trabajo tiene como objetivo presentar uno de los temas clásicos del Álgebra Lineal Numérica: la descomposición en valores singulares de una matriz. No es nuestra intención dar las demostraciones de los resultados matemáticos, ya que pueden encontrarse en la bibliografía citada, sino hacer hincapié en la interpretación geométrica, su relación con la descomposición en autovalores y su aplicación al problema de transmisión de imágenes.