Resumen de Krylov methods for large-scale modern problems in numerical linear algebra
Sergio Andrés González Pizarro
Los problemas numéricos con matrices muy grandes han despertado mucho interés en las últimas décadas dado que surgen de distintas aplicaciones en múltiples campos de investigación. Además, estas matrices son a menudo dispersas, esto es, la mayoría de sus entradas son iguales a cero. Hace aproximadamente 40 años, los problemas más comunes relacionados con matrices muy grandes y dispersas consistían en resolver los problemas clásicos del álgebra lineal numérica, estos son, resolver sistemas de ecuaciones lineales, calcular autovalores y autovectores, resolver problemas de mínimos cuadrados y calcular descomposiciones en valores singulares. Sin embargo, en los últimos años, han aparecido problemas relacionados con matrices grandes y dispersas de diferente índole, motivando y desafiando al álgebra lineal numérica a resolverlos mediante el desarrollo de algoritmos precisos y eficientes.
Algunas de las dificultades más comunes que aparecen en el desarrollo de algoritmos para resolver problemas numéricos que involucren matrices grandes y dispersas están relacionadas con los altos costes computacionales que requieren estos procesos, es decir, los largos períodos de tiempo en que debe trabajar el ordenador para resolverlos y el alto coste de memoria que necesitan estos algoritmos al momento de almacenar matrices de gran tamaño, lo que indica que los métodos directos no pueden ser utilizados en este caso. Estos obstáculos sugieren que una buena alternativa para resolver dichos problemas sea utilizar métodos iterativos, y en particular, nos enfocaremos en métodos de proyección basados en subespacios de Krylov, los cuáles resultan una buena opción al momento de desarrollar algoritmos para resolver problemas modernos que involucren matrices muy grandes y dispersas. En palabras simples, los métodos de Krylov proyectan el problema original, que involucra matrices de gran tamaño, en otro problema de tamaño mucho más reducido, cuya solución contiene información de la solución del problema original y que se puede calcular a un coste mucho más pequeño que el que requeriría resolver el problema original.
En esta tesis de doctorado, desarrollamos algoritmos nuevos y originales para resolver dos problemas modernos de álgebra lineal numérica con matrices muy grandes y dispersas: en primer lugar, introducimos un nuevo método (al que bautizamos R-CORK) para resolver problemas racionales de autovalores, esto es, resolvemos problemas de autovalores para una matriz grande y dispersa que tiene funciones racionales como entradas, y, en segundo lugar, presentamos diferentes métodos de proyección para calcular la solución aproximada de ecuaciones de T-Sylvester (o también llamadas ecuaciones de Sylvester para la T-congruencia).
Para resolver el problema racional de autovalores, comenzamos utilizando una técnica llamada linealización, que consiste en construir una matriz polinomial lineal más grande que la del problema original, y que contiene toda la información sobre la solución del mismo que puede ser calculada de una manera más simple. El método R-CORK puede verse como una extensión de otro método existente previamente en la literatura: el método CORK (cuyas siglas en inglés corresponden a ``Compact Rational Krylov''), el cuál fue introducido para resolver problemas de autovalores de una familia de matrices no lineales que pueden ser expresadas y linealizadas de formas particulares, a la cual pertenecen problemas polinomiales arbitrarios de autovalores pero no problemas racionales arbitrarios de autovalores. El método R-CORK explota la estructura del problema linealizado representando los vectores de Krylov en una forma compacta de manera que se reduce el coste de almacenamiento, lo que resulta en un método con dos niveles de ortogonalización. El primer nivel de ortogonalización trabaja con vectores del mismo tamaño que el problema original, y el segundo nivel trabaja con vectores de tamaño mucho más pequeño que el problema original. Dado que hemos desarrollado el método de manera que los vectores del tamaño de la linealización nunca sean almacenados u ortogonalizados, el método R-CORK es más eficiente, desde el punto de vista de costes de memoria y procesos de ortogonalización, que la utilización directa del método racional clásico de Krylov aplicado a la linealización. Además, dado que el método R-CORK está basado en el método racional clásico de Krylov, puede desarrollarse la implementación de una técnica llamada ``reinicio implícito'' y en este trabajo presentamos una manera eficiente de hacerlo para el problema linealizado, que además preserva la representación compacta de los vectores de Krylov.
En esta tesis doctoral también presentamos métodos de proyección para resolver la ecuación matricial de T-Sylvester, la cuál recientemente ha recibido una atención considerable como consecuencia de su relación cercana a múltiples aplicaciones. Los aspectos teóricos de esta ecuación han sido muy estudiados, y, antes del desarrollo de esta tesis, habían algoritmos estables y eficientes para resolver esta ecuación matricial cuando las matrices eran de tamaños moderados. Sin embargo, el desarrollo de algoritmos numéricos para resolver ecuaciones de T-Sylvester con matrices muy grandes y dispersas era un problema abierto. En esta tesis, presentamos varios métodos de proyección, basados en subespacios de Krylov en bloques y subespacios de Krylov extendidos, para la solución numérica de ecuaciones de T-Sylvester cuando la matriz del lado derecho es una matriz de rango bajo. Para ello, proyectamos el problema original en una ecuación de T-Sylvester de menor tamaño, y resolvemos dicho problema reducido utilizando un algoritmo existente en la literatura para matrices de tamaño moderado. Además, desarrollamos un análisis informal sobre la convergencia esperada del algoritmo basado en subespacios de Krylov en bloques, y una guía clara sobre cuál algoritmo es más conveniente utilizar en cada situación.
Todos los algoritmos presentados en esta tesis han sido probados de manera extensiva, y los resultados numéricos expuestos en este trabajo muestran que, en la práctica, dichos algoritmos funcionan satisfactoriamente.
