Implicaciones de aproximar el determinante

16

Se sabe que se puede calcular exactamente el determinante de una matriz en el espacio determinístico log 2 ( n ) . ¿Cuáles serían las implicaciones de complejidad de aproximar el determinante de una matriz real, de la norma como máximo 1 ( A 1 ) en el espacio logarítmico aleatorizado, por decir, una precisión 1 / poli ?n×nlog2(n)1A11/poly

A este respecto, ¿cuál sería la aproximación "correcta" que pedir: multiplicativa o aditiva? (Ver una de las respuestas a continuación).

Lior Eldar
fuente
1
¿Se supone que están en una RAM real?
No estoy seguro de entender bien la pregunta, pero si te refieres a la precisión de la aritmética, supongo que cada número real se almacena en bits de registro (n).
Lior Eldar

Respuestas:

4

Con el riesgo de no haber entendido correctamente los detalles de la pregunta: ser capaz de aproximar el determinante dentro de cualquier factor requiere poder decidir si una matriz cuadrada es singular o no, lo que debería tener algunas consecuencias.

Por un lado, ofrece una prueba aleatoria de si un gráfico general tiene una coincidencia perfecta (a través de la matriz de Tutte y Schwarz-Zippel). No creo que este último se conozca en el espacio de registro aleatorio (por ejemplo, Complexity Zoo enumera la coincidencia perfecta bipartita como difícil para NL).

Magnus Wahlström
fuente
Gracias Magnus, aunque en realidad estaba pensando en un error de aproximación aditiva, en cuyo caso no se te pedirá que distingas si una matriz es singular o no. La aproximación multilipcativa también puede ser de interés, por lo que en este momento no estoy seguro de cuál es la mejor definición.
Lior Eldar
1
@LiorEldar, seguramente incluso con un error de aproximación aditiva, si las entradas en la matriz son enteros y el error aditivo vinculado es menor que 0.5, ¿tiene una prueba de singularidad infalible?
Peter Taylor
Hola Peter Taylor, creo que, para hablar, digamos 0.5 precisión que primero necesitas de alguna manera para especificar la norma de operador más grande que soportas. Entonces, por ejemplo, si su entrada tiene A 1 , entonces su error aditivo determinante puede ser 1 / p o l y ( n ) . Entonces, incluso si su entrada se le da como enteros truncados, cada uno de l o g ( n ) bits, entonces la norma máxima para la cual se le requiere aproximar el determinante sería n n en términos de enteros, lo que significa que 0.5AA11/poly(n)log(n)nn0.5El error de aproximación es mucho menor que relación con A . 1/poly(n)A
Lior Eldar
Creo que el problema con el error aditivo en relación con la norma es que realmente no escala bien. Digamos que tenía un algoritmo que daba un error de aproximación relación con | El | A | El | . Ahora deje que A ' sea ​​la matriz diagonal de bloque n 3 × n 3 formada usando n 2 copias de A como bloques. Entonces | El | A | El | = | El | A | El |1/poly(n)||A||An3×n3n2A||A||=||A||, pero , entonces a | El | A | El | / p o l y ( n ) error aditivo para d e t ( A ' ) escala a un error aditivo O ( 1 ) para d e t ( A ) . det(A)=det(A)n2||A||/poly(n)det(A)O(1)det(A)
Kevin Costello