Qual é a complexidade de tempo real da eliminação gaussiana?

Em resposta a uma pergunta anterior , mencionei a crença comum, mas falsa, de que a eliminação "gaussiana" ocorre no tempo . Embora seja óbvio que o algoritmo usa operações aritméticas , a implementação descuidada pode criar números com muitos bits exponencialmente. Como um exemplo simples, suponha que desejemos diagonalizar a seguinte matriz: $O(n^3)$ $O(n^3)$

[\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}$

Se usarmos uma versão do algoritmo de eliminação sem divisão, que apenas adiciona múltiplos inteiros de uma linha a outra, e sempre rodarmos em uma entrada diagonal da matriz, a matriz de saída terá o vetor ao longo da diagonal. $(2, 4, 16, 256, \dots, 2^{2^{n-1}})$

Mas qual é a complexidade de tempo real da eliminação gaussiana? A maioria dos autores de otimização combinatória parece estar feliz com "fortemente polinomial", mas estou curioso sobre o que realmente é o polinômio.

Um artigo de 1967 de Jack Edmonds descreve uma versão da eliminação gaussiana ("possivelmente devido a Gauss") que é executada em tempo fortemente polinomial. O principal insight de Edmonds é que cada entrada em cada matriz intermediária é o determinante de uma menor da matriz de entrada original. Para uma matriz com entradas inteiras de bits, Edmonds prova que seu algoritmo requer números inteiros com no máximo bits. Sob a suposição "razoável" de que , o algoritmo de Edmonds é executado em se usarmos aritmética de número inteiro do livro, ou em se use multiplicação baseada em FFT, em uma RAM inteira padrão, que pode executar $n\times n$ $m$ $O(n(m+\log n))$ $m=O(\log n)$ $O(n^5)$ $\tilde{O}(n^4)$ $O(\log n)$ aritmética de bits em tempo constante. (Edmonds não fez essa análise do tempo; ele apenas afirmou que seu algoritmo é "bom".)

Essa ainda é a melhor análise conhecida? Existe uma referência padrão que fornece um limite de tempo explícito melhor ou pelo menos um limite melhor na precisão necessária?

De maneira mais geral: qual é o tempo de execução (na RAM inteira) do algoritmo mais rápido conhecido por resolver sistemas arbitrários de equações lineares?

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

(inserindo ondas de mão violentas), você não conseguia resolver o grande problema inteiro nesse caso específico usando pequenos truques primos do módulo hash? o algoritmo seria randomizados, mas ainda .. É certo que este não responde à pergunta que você fez ...

Suresh Venkat

Talvez as seguintes referências ajudassem? notas de aula de lovasz , capítulo de yap sobre determinantes (Yap fornece complexidade de bits para cálculo determinante através do algoritmo de Bareiss). No livro de Yap (exercício 10.1.1 (iii)), fiquei com a impressão de que não se sabia se a redução gaussiana deu valores intermediários que cresceram exponencialmente em tamanho de bit, mas agora não tenho certeza.

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

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

user834

O algoritmo de eliminação gaussiano padrão divide a linha dinâmica pelo elemento dinâmico antes de reduzir as linhas posteriores. A questão em aberto refere-se a esta versão padrão. O exemplo que dei no início da minha pergunta usa uma variante diferente, que NÃO é dividida pelo elemento pivô.

Jeffε

Curioso. O tempo limite de Yap para o algoritmo de Bereiss é idêntico ao tempo implícito na análise de Edmonds da eliminação gaussiana.

Jeffε

rjlipton pesquisou a área recentemente e cita a tese de Kannan Phd sobre o assunto. uma parte fundamental da análise é wrt Smith forma normal

vzn

Respostas:

Penso que a resposta é , onde omitimos os fatores (poli) logarítmicos. O limite é apresentado em "W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann, G. Villard. Resolução de sistemas lineares inteiros esparsos. Proc. ISSAC'06, Genova, Itália, ACM Press, 63-70, julho 2006 ", mas é baseado em um artigo de Dixon:" Solução exata de equações lineares usando expansões P-adic, John D. Dixon, NUMERISCHE MATHEMATIK, Volume 40, Número 1, 137-141 ". $\widetilde O(n^3 \log( \|A\| + \|b\|))$

Elias
fonte

Obrigado pela referência! Isso responde à minha segunda pergunta, mas não à minha primeira.

Jeffε

Se você usar pivotagem, o tamanho de bits dos resultados intermediários na eliminação gaussiana (GE) será polinomial, não haverá explosão exponencial. Eu acho que esse é o resultado da Bareiss. Quanto à complexidade da GE, há um algoritmo no livro de Gathen e Gerhard, "Álgebra Moderna de Computadores" para calcular o determinante de uma matriz , baseada na GE, aritmética modular e teorema chinês do restante (Seção 5.5, 101-105). A complexidade é . Eu acho que um fator de poderia ser salvo usando aritmética rápida. Se não estou errado, esse é o limite mencionado pelo usuário834.

A

$A$

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

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

n

$n$

Elias

@Elias, qual é a definição da norma nessa expressão? É o maior coeficiente em tamanho absoluto? É o tamanho do bit? Além disso, esse resultado é para matrizes racionais arbitrárias?

Juan Bermejo Vega

Eu acho que a resposta para sua primeira pergunta também é devido aos seguintes argumentos: O artigo de Edmonds não descreve uma variante da eliminação gaussiana mas prova que qualquer número calculado em uma etapa do algoritmo é determinante de alguma submatriz de A. Pelo livro de Schrijver sobre Teoria da Programação Linear e Inteira , sabemos que se a codificação de A precisa de b bits (b deve estar em $\widetilde O(n^3 \log( \|A\| + \|b\|))$ $\widetilde O(\log( \|A\|)$ ), qualquer um dos seus subdeterminantes precisa no máximo de 2b bits (Teorema 3.2). Para tornar a eliminação gaussiana um algoritmo de tempo polinomial, precisamos nos preocupar com os quocientes computados: temos que cancelar fatores comuns de cada fração que computamos em qualquer etapa intermediária e, em seguida, todos os números têm comprimento de codificação linear no comprimento de codificação de A.

Matthias Walter
fonte