Implicações da aproximação do determinante

16

Sabe-se que se pode calcular exatamente o determinante de um matriz em determinstic de log 2 ( n ) espaço. Quais seriam as implicações de complexidade de aproximar o determinante de uma matriz real, da norma, no máximo, 1 ( A 1 ) em randomizado logarítmica espaço,-se dizer, um 1 / poli precisão?n×nregistro2(n)1 1__UMA__1 11 1/poli

A esse respeito, qual seria a aproximação "correta" a ser solicitada - multiplicativa ou aditiva? (veja uma das respostas abaixo).

Lior Eldar
fonte
11
Eles deveriam estar em uma RAM real?
Não sei se entendi corretamente a pergunta, mas se você se referir à precisão da aritmética, presumo que cada número real seja armazenado em bits de log (n).
Lior Eldar

Respostas:

4

Com o risco de não ter entendido os detalhes da pergunta adequadamente: ser capaz de aproximar o determinante de qualquer fator exige ser capaz de decidir se uma matriz quadrada é singular ou não, o que deve ter algumas consequências.

Por um lado, fornece um teste aleatório para determinar se um gráfico geral possui uma correspondência perfeita (via matriz de Tutte e Schwarz-Zippel). Eu não acho que o último seja conhecido no espaço de log aleatório (por exemplo, o Complexity Zoo lista a correspondência perfeita bipartida tão difícil para NL).

Magnus Wahlström
fonte
Obrigado Magnus, embora eu estivesse realmente pensando em um erro de aproximação aditivo; nesse caso, você não precisará distinguir se uma matriz é singular ou não. A aproximação multilipativa também pode ser interessante, então, no momento, não tenho certeza de qual é a melhor definição.
Lior Eldar
11
@LiorEldar, certamente mesmo com erro de aproximação aditivo, se as entradas na matriz forem números inteiros e o erro do aditivo for inferior a 0,5, você tem um teste de singularidade infalível?
Peter Taylor
Olá Peter Taylor, acho que para falar, digamos, 0,5 precisão, primeiro você precisa especificar a maior norma de operador que você suporta. Assim, por exemplo se a sua entrada tem Um 1 , então o seu erro aditivo determinante pode ser 1 / p o l y ( n ) . Portanto, mesmo que sua entrada seja fornecida como números inteiros truncados, cada um de l o g ( n ) bits, a norma máxima pela qual você precisa aproximar o determinante seria n n em termos de números inteiros, o que significa 0,5AA11/poly(n)log(n)nn0.5o erro de aproximação é muito menor que relação a " A " . 1/poly(n)A
Lior Eldar
Eu acho que o problema com o erro aditivo em relação à norma é que ele não é realmente escalável. Digamos que eu tivesse um algoritmo que forneceu um erro de aproximação relação a | | Um | | . Agora seja A ' a matriz diagonal de n 3 × n 3 blocos formada usando n 2 cópias de A como blocos. Então | | Um | | = | | A | |1/poly(n)||A||An3×n3n2A||A||=||A||, mas , então a | | A | | / p o l y ( n ) o erro aditivo para d e t ( A ) escala para um erro aditivo O ( 1 ) para d e t ( A ) . det(A)=det(A)n2||A||/poly(n)det(A)O(1)det(A)
22713 Kevin Costello