Numerical approximations with tensor-based techniques for high-dimensional problems

Abstract

[ES] La idea de seguir una secuencia de pasos para lograr un resultado deseado es inherente a la naturaleza humana: desde que empezamos a andar, siguiendo una receta de cocina o aprendiendo un nuevo juego de cartas. Desde la antigüedad se ha seguido este esquema para organizar leyes, corregir escritos, e incluso asignar diagnósticos. En matemáticas a esta forma de pensar se la denomina 'algoritmo'. Formalmente, un algoritmo es un conjunto de instrucciones definidas y no-ambiguas, ordenadas y finitas, que permite solucionar un problema. Desde pequeños nos enfrentamos a ellos cuando aprendemos a multiplicar o dividir, y a medida que crecemos, estas estructuras nos permiten resolver diferentes problemas cada vez más complejos: sistemas lineales, ecuaciones diferenciales, problemas de optimización, etcétera.

Hay multitud de algoritmos que nos permiten hacer frente a este tipo de problemas, como métodos iterativos, donde encontramos el famoso Método de Newton para buscar raíces; algoritmos de búsqueda para localizar un elemento con ciertas propiedades en un conjunto mayor; o descomposiciones matriciales, como la descomposición LU para resolver sistemas lineales. Sin embargo, estos enfoques clásicos presentan limitaciones cuando se enfrentan a problemas de grandes dimensiones, problema que se conoce como `la maldición de la dimensionalidad'.

El avance de la tecnología, el uso de redes sociales y, en general, los nuevos problemas que han aparecido con el desarrollo de la Inteligencia Artificial, ha puesto de manifiesto la necesidad de manejar grandes cantidades de datos, lo que requiere el diseño de nuevos mecanismos que permitan su manipulación. En la comunidad científica, este hecho ha despertado el interés por las estructuras tensoriales, ya que éstas permiten trabajar eficazmente con problemas de grandes dimensiones. Sin embargo, la mayoría de métodos clásicos no están pensados para ser empleados junto a estas operaciones, por lo que se requieren herramientas específicas que permitan su tratamiento, lo que motiva un proyecto como este.

El presente trabajo se divide de la siguiente manera: tras revisar algunas definiciones necesarias para su comprensión, en el Capítulo 3, se desarrolla la teoría de una nueva descomposición tensorial para matrices cuadradas. A continuación, en el Capítulo 4, se muestra una aplicación de dicha descomposición a grafos regulares y redes de mundo pequeño. En el Capítulo 5, se plantea una implementación eficiente del algoritmo que proporciona la nueva descomposición matricial, y se estudian como aplicación algunas EDP de orden dos. Por último, en los Capítulos 6 y 7 se exponen unas breves conclusiones y se enumeran algunas de las referencias consultadas, respectivamente.

[CA] La idea de seguir una seqüència de passos per a aconseguir un resultat desitjat és inherent a la naturalesa humana: des que comencem a caminar, seguint una recepta de cuina o aprenent un nou joc de cartes. Des de l'antiguitat s'ha seguit aquest esquema per a organitzar lleis, corregir escrits, i fins i tot assignar diagnòstics. En matemàtiques a aquesta manera de pensar se la denomina algorisme. Formalment, un algorisme és un conjunt d'instruccions definides i no-ambigües, ordenades i finites, que permet solucionar un problema. Des de xicotets ens enfrontem a ells quan aprenem a multiplicar o dividir, i a mesura que creixem, aquestes estructures ens permeten resoldre diferents problemes cada vegada més complexos: sistemes lineals, equacions diferencials, problemes d'optimització, etcètera.

Hi ha multitud d'algorismes que ens permeten fer front a aquesta mena de problemes, com a mètodes iteratius, on trobem el famós Mètode de Newton per a buscar arrels; algorismes de cerca per a localitzar un element amb unes certes propietats en un conjunt major; o descomposicions matricials, com la descomposició DL. per a resoldre sistemes lineals. No obstant això, aquests enfocaments clàssics presenten limitacions quan s'enfronten a problemes de grans dimensions, problema que es coneix com `la maledicció de la dimensionalitat'.

L'avanç de la tecnologia, l'ús de xarxes socials i, en general, els nous problemes que han aparegut amb el desenvolupament de la Intel·ligència Artificial, ha posat de manifest la necessitat de manejar grans quantitats de dades, la qual cosa requereix el disseny de nous mecanismes que permeten la seua manipulació. En la comunitat científica, aquest fet ha despertat l'interés per les estructures tensorials, ja que aquestes permeten treballar eficaçment amb problemes de grans dimensions. No obstant això, la majoria de mètodes clàssics no estan pensats per a ser emprats al costat d'aquestes operacions, per la qual cosa es requereixen eines específiques que permeten el seu tractament, la qual cosa motiva un projecte com aquest.

El present treball es divideix de la següent manera: després de revisar algunes definicions necessàries per a la seua comprensió, en el Capítol 3, es desenvolupa la teoria d'una nova descomposició tensorial per a matrius quadrades. A continuació, en el Capítol 4, es mostra una aplicació d'aquesta descomposició a grafs regulars i xarxes de món xicotet. En el Capítol 5, es planteja una implementació eficient de l'algorisme que proporciona la nova descomposició matricial, i s'estudien com a aplicació algunes EDP d'ordre dos. Finalment, en els Capítols 6 i 7 s'exposen unes breus conclusions i s'enumeren algunes de les referències consultades, respectivament.

[EN] The idea of following a sequence of steps to achieve a desired result is inherent in human nature: from the moment we start walking, following a cooking recipe or learning a new card game. Since ancient times, this scheme has been followed to organize laws, correct writings, and even assign diagnoses. In mathematics, this way of thinking is called an algorithm. Formally, an algorithm is a set of defined and unambiguous instructions, ordered and finite, that allows for solving a problem. From childhood, we face them when we learn to multiply or divide, and as we grow, these structures will enable us to solve different increasingly complex problems: linear systems, differential equations, optimization problems, etc.

There is a multitude of algorithms that allow us to deal with this type of problem, such as iterative methods, where we find the famous Newton Method to find roots; search algorithms to locate an element with specific properties in a more extensive set; or matrix decompositions, such as the LU decomposition to solve some linear systems. However, these classical approaches have limitations when faced with large-dimensional problems, a problem known as the `curse of dimensionality'.

The advancement of technology, the use of social networks and, in general, the new problems that have appeared with the development of Artificial Intelligence, have revealed the need to handle large amounts of data, which requires the design of new mechanisms that allow its manipulation. This fact has aroused interest in the scientific community in tensor structures since they allow us to work efficiently with large-dimensional problems. However, most of the classic methods are not designed to be used together with these operations, so specific tools are required to allow their treatment, which motivates work like this.

This work is divided as follows: after reviewing some definitions necessary for its understanding, in Chapter 3, the theory of a new tensor decomposition for square matrices is developed. Next, Chapter 4 shows an application of said decomposition to regular graphs and small-world networks. In Chapter 5, an efficient implementation of the algorithm provided by the new matrix decomposition is proposed, and some order two PDEs are studied as an application. Finally, Chapters 6 and 7 present some brief conclusions and list some of the references consulted.