¿Cuál es la complejidad temporal real de la eliminación gaussiana?

En una respuesta a una pregunta anterior , mencioné la creencia común pero falsa de que la eliminación "gaussiana" se ejecuta en el tiempo $O(n^3)$ . Si bien es obvio que el algoritmo utiliza operaciones aritméticas $O(n^3)$ , la implementación descuidada puede crear números con exponencialmente muchos bits. Como un ejemplo simple, supongamos que queremos diagonalizar la siguiente matriz:

[\begin{matrix} 2 & 0 & 0 & \dots & 0 \\ 1 & 2 & 0 & \dots & 0 \\ 1 & 1 & 2 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & 1 & 1 & \dots & 2 \end{matrix}]

$\begin{bmatrix} 2 & 0 & 0 & \cdots & 0 \\ 1 & 2 & 0 & \cdots & 0 \\ 1 & 1 & 2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & 1 & \cdots & 2 \\ \end{bmatrix}$

Si utilizamos una versión del algoritmo de eliminación sin división, que solo agrega múltiplos enteros de una fila a otra, y siempre pivotamos en una entrada diagonal de la matriz, la matriz de salida tiene el vector $(2, 4, 16, 256, \dots, 2^{2^{n-1}})$ largo de la diagonal.

Pero, ¿cuál es la complejidad del tiempo real de la eliminación gaussiana? La mayoría de los autores de optimización combinatoria parecen estar contentos con "fuertemente polinomial", pero tengo curiosidad por saber qué es realmente el polinomio.

$n\times n$ $m$ $O(n(m+\log n))$ $m=O(\log n)$ $O(n^5)$ $\tilde{O}(n^4)$ $O(\log n)$

¿Sigue siendo este el mejor análisis conocido? ¿Existe una referencia estándar que ofrezca un límite de tiempo explícito mejor, o al menos un límite mejor en la precisión requerida?

Más en general: ¿Cuál es el tiempo de ejecución (en la RAM entera) del algoritmo más rápido conocido para resolver sistemas arbitrarios de ecuaciones lineales?

ds.algorithms reference-request linear-algebra Jeffε
fuente

(insertando una onda de mano violenta) ¿no podría solucionar el gran problema de los enteros en este caso particular usando el módulo de hash pequeños trucos principales? el algoritmo sería aleatorio, pero aún así ... Es cierto que esto no responde la pregunta que hizo ...

Suresh Venkat

O (n^{3} M_{B} [n (\log n + L)])

$O(n^3 M_B[n (\log n + L)])$

El algoritmo de eliminación gaussiano estándar divide la fila pivote por el elemento pivote antes de reducir las filas posteriores. La pregunta abierta se refiere a esta versión estándar. El ejemplo que di al comienzo de mi pregunta usa una variante diferente, que NO se divide por el elemento pivote.

Jeffε

Curioso. El límite de tiempo de Yap para el algoritmo de Bereiss es idéntico al límite de tiempo que implica el análisis de Edmonds sobre la eliminación gaussiana.

Jeffε

rjlipton examinó el área recientemente y cita la tesis doctoral de Kannan sobre el tema. una parte clave del análisis es la forma normal de

vzn

Respuestas:

$\widetilde O(n^3 \log( \|A\| + \|b\|))$

Elias
fuente

Gracias por la referencia! Esto responde mi segunda pregunta, pero no la primera.

Jeffε

Si usa pivotar, el tamaño de bits de los resultados intermedios en la eliminación gaussiana (GE) es polinomial, no hay una explosión exponencial. Creo que este es el resultado de Bareiss. En cuanto a la complejidad de GE, hay un algoritmo en el libro de Gathen y Gerhard, "Modern Computer Algebra" para calcular el determinante de una matriz , que se basa en GE, la aritmética modular y el teorema del resto chino (Sec. 5.5, pp 101-105). La complejidad es . Creo que un factor de podría guardarse usando la aritmética rápida. Si no me equivoco, este es el límite que mencionó user834.

A

$A$

O (n^{4} \log^{2} ‖ A ‖)

$O(n^4 \log^2\|A\|)$

n

$n$

Elias

@Elias, ¿cuál es la definición de la norma en esa expresión? ¿Es el coeficiente más grande en tamaño absoluto? ¿Es el tamaño del bit? Además, ¿es este resultado para matrices racionales arbitrarias?

Juan Bermejo Vega

Creo que la respuesta a su primera pregunta también es debido a los siguientes argumentos: el artículo de Edmonds no describe una variante de eliminación gaussiana pero demuestra que cualquier número calculado en un paso del algoritmo es un determinante de alguna submatriz de A. Por el libro de Schrijver sobre Teoría de la programación lineal y entera , sabemos que si la codificación de A necesita b bits (b debería estar en $\widetilde O(n^3 \log( \|A\| + \|b\|))$ $\widetilde O(\log( \|A\|)$ ) entonces cualquiera de sus subdeterminantes necesita como máximo 2b bits (Teorema 3.2). Para que la eliminación gaussiana sea un algoritmo de tiempo polinómico, debemos preocuparnos por los cocientes calculados: tenemos que cancelar los factores comunes de cada fracción que calculamos en cualquier paso intermedio y luego todos los números tienen una longitud de codificación lineal en la longitud de codificación de A.

Matthias Walter
fuente