logo móvil
Contáctanos

Ingeniería de un Solucionador Laplaciano Combinatorio: Lecciones Aprendidas

Autores: Hoske, Daniel; Lukarski, Dimitar; Meyerhenke, Henning; Wegner, Michael

Idioma: Inglés

Editor: MDPI

Año: 2016

Descargar PDF

Acceso abierto

Artículo científico
2016

Ingeniería de un Solucionador Laplaciano Combinatorio: Lecciones Aprendidas


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Sistema lineal de resolución
Algoritmos
Matriz Laplaciana
Flujo eléctrico
árbol de expansión
Solucionador combinatorio

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 29

Citaciones: Sin citaciones


Descripción
La resolución de sistemas lineales es un pilar fundamental en matemáticas aplicadas. Recientemente, los científicos informáticos teóricos han contribuido con algoritmos sofisticados para resolver sistemas lineales con matrices simétricas diagonalmente dominantes (SDD) en tiempo casi linealmente demostrable. Estos algoritmos son muy interesantes desde una perspectiva teórica, pero su rendimiento práctico no estaba claro. Aquí abordamos esta brecha. Proporcionamos la primera implementación del solucionador combinatorio de Kelner et al. (STOC 2013), que es atractivo para la implementación debido a su simplicidad conceptual. El algoritmo explota que una matriz laplaciana (que es SDD) corresponde a un grafo; resolver sistemas lineales laplacianos simétricos equivale a encontrar un flujo eléctrico en este grafo con la ayuda de ciclos inducidos por un árbol de expansión con la propiedad de baja elongación. Los resultados de nuestros experimentos son ambivalentes. Si bien confirman el tiempo de ejecución casi lineal predicho, los factores constantes hacen que el solucionador sea mucho más lento para entradas razonables que los métodos básicos con una complejidad asintótica más alta. Tampoco pudimos utilizar el solucionador de manera efectiva como un suavizante o precondicionador. Además, si bien los árboles de expansión con menor elongación reducen efectivamente el tiempo de ejecución del solucionador, experimentamos nuevamente una discrepancia en la práctica: en nuestros experimentos, los algoritmos de árboles de expansión simples funcionan mejor que aquellos con una elongación baja garantizada. Esperamos que nuestros resultados brinden ideas para futuras mejoras de los solucionadores lineales combinatorios.

Otros recursos que podrían interesarte

Temas Virtualpro