Estoy buscando una buena encuesta sobre algoritmos y complejidad del álgebra lineal (operaciones como rango, inverso, valores propios, ... para matrices booleanas, y enteros / racionales) con énfasis en paralelo ( jerarquía ) y algoritmos polytime. No pude encontrar uno reciente. NC
¿Conoces una buena encuesta reciente o libro sobre la complejidad del álgebra lineal?
Este libro no menciona explícitamente algoritmos paralelos, pero el libro de Yap "Problemas fundamentales del álgebra algorítmica" es una muy buena referencia y discute la complejidad de muchas preguntas de álgebra lineal. Hay un capítulo específicamente sobre Sistemas lineales que discute la complejidad de tiempo / bit del cálculo determinante, la inversión de matriz, los algoritmos de forma normal de Hermite, entre otros.
El libro también trata la complejidad de la multiplicación, las bases de Grobner y las técnicas de reducción de celosía (como LLL). No puedo recomendarlo lo suficiente y apuesto a que encontrarás algo que valga la pena.
fuente