La matriz de Moore es similar a la matriz de Vandermonde pero tiene una definición ligeramente modificada. http://en.wikipedia.org/wiki/Moore_matrix
¿Cuál es la complejidad de calcular el determinante de un rango completo de la matriz de Moore módulo algún entero?
¿Se puede reducir el determinante de Moore de usando técnicas FFT a para algunos ?
¿Es la complejidad de Moore det modulo un número entero y Vandermonde det lo mismo? La complejidad del determinante de Vandermonde es (Página 644 en el Manual de Ciencias de la Computación Teórica: Algoritmos y complejidad Por Jan Leeuwen)
Publicación similar a la actual: módulo determinante m
Respuestas:
En general, existe un algoritmo teórico de tiempo para encontrar la descomposición LU de una matriz arbitraria utilizando el algoritmo Coppersmith-Winograd , que obviamente produce el determinante (sumando el tiempo O ( n ) ). Sin embargo, existe el problema de que el algoritmo Coppersmith – Winograd no se considera utilizable en la práctica. Afaik, la gente usa principalmente el algoritmo de Strassen de tiempo O ( n 2.807 ) . ¿No utiliza esto lu_factorize de UBLAS ?O(n2.376) O(n) O(n2.807)
En su caso, la matriz de Moore debería admitir optimizaciones considerables porque básicamente cualquier procedimiento de eliminación gaussiana como la descomposición de LU se puede hacer de manera abstracta. De hecho, encontrará una buena fórmula para calcular el determinante de Moore al que hace referencia Wikipedia , que presumiblemente se prueba simplemente resolviendo la descomposición de LU en general.O(n)
fuente
Es importante que, en la definición que proporcione, la matriz viva en un campo finito, digamos donde m es primo. Esto le permite utilizar el teorema de Euler para calcular los dobles exponenciales que aparecen en la matriz en el tiempo . De lo contrario, parece difícil incluso calcular los coeficientes de la matriz sin factorizar .Zm m O ( log ( m n )aqemodm a q i ≡ a q iO(log(mn)M(logm)) m
Si es primo o puede factorizarse de manera eficiente, la complejidad del peor de los casos está dominada por el número de pasos que necesita para la multiplicación matricial . Por ejemplo, el enfoque de forma normal de Smith que mencioné en la publicación asociada calcularía el determinante en el tiempo si usa "lento" algoritmos de multiplicación . puede ser elegido para ser 2.373.O ( n ω ) O ( n ωm O(nω) ∗ ωO(nωlog2mlog(mn)) ∗ ω
Obtiene una desaceleración en Moore vs Vandermonde, ya que debe doble exponer los coeficientes de la matriz. Cuando puede factorizar esta desaceleración es solo poliligarítmica en . Si no, el algoritmo presentado le ofrece una reducción de Cook a Exponenciación Doble Modular en .m Z mm m Zm
Nota *: los algoritmos más rápidos para la multiplicación de enteros le permiten reemplazar con .M ( log m log log m )log2m M(logmloglogm)
Actualización : sobre la posibilidad de lograr .O(nlogan)
No tengo una respuesta definitiva para esto, pero encontré información que puede apretar su búsqueda.
Los algoritmos para matrices estructuradas que calculan cantidades como determinantes en el tiempo se denominan "superrápidos" en la literatura. Todos los algoritmos "superrápidos" conocidos para matrices estructuradas (Vandermonde, Toeplitz, Hankel) parecen basarse en una propiedad común de estas matrices conocida como bajo "rango de desplazamiento". Conferir la discusión sobre el primer capítulo de este libro (páginas de acceso abierto), o en este artículo [ACM] , [PDF] .O(nlogan)
Por lo que leí, dada una matriz Moore , si pudiste encontrar las matrices , modo que la nueva matriz (o alternativamente ) tiene la siguiente estructuraM A B L ( M ) = A M - M B L ( M ) = M - A M Bm×n M A B L(M)=AM−MB L(M)=M−AMB
, y el rango es pequeño (constante o delimitado por ), entonces puede aplicar las técnicas existentes (consulte el capítulo 5 del libro, abra- páginas de acceso) para triangular y, por lo tanto, calcular , usando . Arriba, , denotan vectores. Si no puede encontrar el libro de arriba para leerlo todo, este artículo también tiene mucha información sobre estos métodos.o ( minr>0 o(min{m,n}) M O ( n log 2 n ) g k h kdetM O(nlog2n) gk hk
Desafortunadamente, no he podido encontrar una estructura de bajo rango de desplazamiento para la matriz de Moore (Vandermonde lo ha hecho). La principal complicación aquí parece surgir de la naturaleza "no lineal" del doble exponencial. Si ayuda, los casos de Vandermonde, Cauchy, Toeplitz, Hankel se resuelven en el libro.
fuente