Estoy buscando un documento de encuesta o un libro que cubra los resultados sobre la complejidad espacial de las operaciones comunes de álgebra lineal, como el rango de la matriz, el cálculo de valores propios, etc. Insisto en la parte de "complejidad espacial" que significa la complejidad del espacio de trabajo, en lugar de la complejidad del tiempo ya que Es más fácil rastrear los resultados de tiempo. Agradezco cualquier referencia al respecto.
Gracias.
Respuestas:
Las versiones de decisión de muchos problemas comunes en álgebra lineal sobre los enteros (o racionales) están en la clase , vea el documentoD E T
Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Estructura e importancia de la clase Logspace-MOD. Teoría de sistemas matemáticos 25 (3): 223-237 (1992)
está contenido en D S P A C E ( log 2 ) .D E T D S P A C E ( log2)
Calcular los valores propios es un poco más delicado:
1) En , se pueden calcular los coeficientes del polinomio característico.D S P A C E ( log2)
2) Luego puede usar el algoritmo paralelo de Reif y Neff para calcular aproximaciones a los valores propios. El algoritmo se ejecuta en una CREW-PRAM en tiempo logarítmico con muchos procesadores polinomiales, por lo que se puede simular con un espacio polilogarítmico. (No se indica explícitamente en el documento, pero su PRAM debe ser uniforme en el espacio logarítmico). El espacio utilizado es polilogarítmico en el tamaño de la matriz de entrada y la precisión . La precisión p significa que obtiene aproximaciones hasta un error aditivo de 2 - p .pag pag 2- p
Esta es una concatenación de funciones computables en el espacio polilogarítmico. (Las cintas de salida son de solo escritura y unidireccionales).
C. Andrew Neff, John H. Reif: Un algoritmo eficiente para el problema de raíces complejas. J. Complejidad 12 (2): 81-115 (1996)
fuente
fuente