Prueba si dos matrices de 12x12 tienen el mismo determinante

$12 \times 12$ $Q$

det (Q) = det (12 I - Q - J) (1)

$\det(Q) = \det(12I-Q-J) \; \; (1)$

J

$J$

Actualmente estoy haciendo esto con la biblioteca de armadillo , pero resulta ser demasiado lento. La cuestión es que necesito hacer esto por un billón de matrices y resulta que calcular los dos determinantes es el cuello de botella de mi programa. Por eso tengo dos preguntas

¿Hay algún truco que pueda usar para calcular el determinante más rápido dado que conozco su tamaño? ¿Es quizás una expansión desordenada para $12 \times12$ matrices que podría funcionar en este caso?
¿Hay alguna otra manera eficiente de probar la igualdad $(1)$

Editar. Para responder los comentarios. Necesito calcular todos los gráficos no autocomplementarios conectados $G$ de orden $13$ , modo que $G$ y $\overline{G}$ tengan el mismo número de árboles de expansión. La motivación para esto se puede encontrar en esta publicación de mathoverflow . En cuanto a la máquina, estoy ejecutando esto en una máquina de 8 núcleos 3.4GHh en paralelo.

Editar. Pude reducir el tiempo de ejecución esperado en un 50% al hacer un programa en C para calcular específicamente el determinante de una matriz de $12 \times 12$ . Las sugerencias son bienvenidas.

linear-algebra matrix c++ graph-theory c Jernej
fuente

¿Qué tan lento es demasiado lento? ¿Cuánto tiempo se tarda en qué hardware? ¿Los trillones de estas s son independientes para que pueda calcular muchos de estos determinantes en paralelo? Si es así, ¿qué tamaño de máquina puede ejecutar? ¿Qué llevó a este problema? ¿Estás seguro de que necesitas calcular los determinantes?

Q

$Q$

Bill Barth

¿Con qué frecuencia (para qué fracción de casos) los determinantes son iguales / diferentes? Si son diferentes la mayoría de las veces, puede haber una prueba más barata para determinar que pueden ser diferentes y usted verificará que sean iguales solo si la primera prueba falla. Al revés si son iguales la mayor parte del tiempo.

Wolfgang Bangerth

Como ya se preguntó: ¿podría proporcionar algún detalle sobre el origen de ? Quizás haya un mejor enfoque que calcular determinantes a ciegas.

Q

$\mathbf Q$

La noción de que esta condición tiene que ser probada "para un trillón de matrices" sugiere 1) que se sabe a priori que tiene alguna estructura especial (de lo contrario, la expectativa de que la condición se mantenga al azar es leve), y 2) que un mejor enfoque podría ser caracterizar todas las matrices con esta propiedad (con una formulación eficientemente verificable).

Q

$Q$

Q

$Q$

hardmath

@hardmath Sí, es una matriz entera que tiene entradas diagonales que van del al y como elementos fuera de la diagonal

Q

$Q$

1

$1$

12

$12$

- 1

$-1$

Jernej

Respuestas:

Como ya está usando C ++ y sus matrices son simétricas positivas definidas, realizaría una factorización dividida de y también de . Aquí supongo que también es positivo definido, de lo contrario, el requerirá pivote para la estabilidad numérica (también es posible que, aunque no sea positivo definido, no sea necesario pivotar, pero debe intentarlo). $LDL^T$ $Q$ $12I-Q-J$ $12I-Q-J$ $LDL^T$

Esto es más rápido que una factorización LU, y también más rápido que Cholesky porque se evitan las raíces cuadradas. El determinante es simplemente el producto de los elementos de la matriz diagonal . El código para realizar una factorización LDL es tan simple que puede escribirlo en menos de 50 líneas de C. La página de Wikipedia en él describe el algoritmo, y tengo un código simple para hacer Cholesky aquí . Puede simplificarlo enormemente y modificarlo para evitar la raíz cuadrada para implementar la factorización $D$ $LDL^T$

Como también puede controlar el formato de almacenamiento, puede optimizar aún más la rutina para almacenar solo la mitad de la matriz y empaquetarla en una matriz lineal para maximizar la localidad de la memoria. También escribiría rutinas de actualización simples de productos de puntos personalizados y de rango 1, ya que los tamaños de los problemas son tan pequeños que debe dejar que el compilador incorpore las rutinas para reducir la sobrecarga de llamadas. Como se trata de un bucle de tamaño fijo, el compilador debería poder alinear y desenrollar automáticamente las cosas cuando sea apropiado.

intentar jugar trucos para aprovechar el hecho de que contiene dentro de la expresión. Es probable que para problemas de tamaño tan pequeño, estos trucos terminen siendo más lentos que simplemente realizar dos cálculos determinantes por separado. Por supuesto, la única forma de verificar estas afirmaciones es probarlo. $12I-Q-J$ $Q$

Victor Liu
fuente

Respaldo la recomendación de implementar , también conocido como Cholesky sin raíz, ya que Armadillo no parece tener una forma de aprovechar la definición positiva / dominancia diagonal.

L D L^{T}

$LDL^T$

hardmath

Sin alguna información sobre la construcción de estas matrices simétricas reales definidas positivas, las sugerencias a realizar son necesariamente limitadas. $12\times 12$

Descargué el paquete Armadillo de Sourceforge y eché un vistazo a la documentación. Tratar de mejorar el rendimiento de cómputo separado y , donde es la matriz de rango de todos los, estableciendo por ejemplo . La documentación señala que este es el valor predeterminado para matrices de hasta , por lo que, por omisión, supongo que la opción es predeterminada para el caso . $\det(Q)$ $\det(12I - Q - J)$ $J$ det(Q,slow=false) $4\times 4$ slow=true $12\times 12$

Lo que slow=true presumiblemente hace es un giro parcial o total para obtener una forma escalonada de fila, desde la cual se puede encontrar fácilmente el determinante. Sin embargo, sabe de antemano que la matriz es positiva definida, por lo que pivotar es innecesario para la estabilidad (al menos presuntamente para la mayor parte de sus cálculos. No está claro si el paquete Armadillo arroja una excepción si los pivotes se vuelven demasiado pequeños, pero esto debería ser un característica de un paquete razonable de álgebra lineal numérica. EDITAR: Encontré el código Armadillo que se implementa en el archivo de encabezado , usando plantillas C ++ para una funcionalidad sustancial. La configuración no parece afectar cómo $Q$ detinclude\armadillo_bits\auxlib_meat.hppslow=false $12\times 12$ el determinante se realizará porque el cálculo se "arroja sobre una pared" a LAPACK (o ATLAS) en ese punto sin ninguna indicación de que no se requiere pivotar; ver det_lapacky sus invocaciones en ese archivo.

El otro punto sería seguir su recomendación de construir el paquete Armadillo que se vincule a los reemplazos de alta velocidad para BLAS y LAPACK, si realmente los está utilizando; ver Sec. 5 del archivo README.TXT de Armadillo para más detalles. [El uso de una versión dedicada de 64 bits de BLAS o LAPACK también se recomienda para la velocidad en las máquinas actuales de 64 bits.]

La reducción de filas a la forma escalonada es esencialmente una eliminación gaussiana y tiene una complejidad aritmética . Para ambas matrices, esto equivale al doble de ese trabajo, o . Estas operaciones pueden ser el "cuello de botella" en su procesamiento, pero hay pocas esperanzas de que sin una estructura especial en (o algunas relaciones conocidas entre los billones de casos de prueba que permiten la amortización) el trabajo podría reducirse a . $\frac{2}{3} n^3 + O(n^2)$ $\frac{4}{3} n^3 + O(n^2)$ $Q$ $O(n^2)$

En comparación, la expansión por cofactores de una matriz general involucraoperaciones de multiplicación (y aproximadamente tantas sumas / restas), por lo que para la comparación ( vs. ) favorece claramente la eliminación sobre los cofactores. $n\times n$ $n!$ $n=12$ $12! = 479001600$ $\frac{2}{3} n^3 = 1152$

Otro enfoque que requiere sería reducir a la forma tridiagonal con transformaciones de Householder, lo que también pone en forma tridiagonal. La computación y pueden realizarse posteriormente en operaciones . [El efecto de la actualización de rango uno en el segundo determinante puede expresarse como un factor escalar dado al resolver un sistema tridiagonal.] $\frac{4}{3} n^3 + O(n^2)$ $Q$ $12I - Q$ $\det(Q)$ $\det(12I - Q - J)$ $O(n)$ $-J$

La implementación de un cálculo tan independiente podría valer la pena como una verificación de los resultados de llamadas exitosas (o fallidas) a la detfunción de Armadillo .

Caso especial: Como lo sugiere un comentario de Jernej, suponga que donde como antes es la matriz (rango 1) de todos y es un matriz diagonal no singular (positiva). De hecho, para la aplicación propuesta en la teoría de grafos, estas serían matrices enteras. Entonces una fórmula explícita para es: $Q = D - J$ $J$ $D=\text{diag}(d_1,\ldots,d_n)$ $\det(Q)$

det (Q) = (\prod_{i = 1}^{n} d_{i}) (1 - \sum_{i = 1}^{n} d_{i}^{- 1})

$\det(Q) = \left(\prod_{i=1}^n d_i \right)\left(1 - \sum_{i=1}^n d_i^{-1} \right)$

Un bosquejo de su prueba brinda la oportunidad de ilustrar una aplicabilidad más amplia, es decir, cuando tiene un determinante conocido y el sistema se resuelve rápidamente. Comience factorizando: $D$ $Dv = (1\ldots 1)^T$

det (D - J) = det (D) \cdot det (I - D^{- 1} J)

$\det(D - J) = \det(D) \cdot \det(I - D^{-1}J)$

Ahora vuelve a ser el rango 1, es decir . Tenga en cuenta que el segundo determinante es simplemente: $D^{-1}J$ $(d_1^{-1}\ldots d_n^{-1})^T(1\ldots 1)$

f (1) = det (I - D^{- 1} J)

$f(1) = \det(I- D^{-1}J)$

donde es el polinomio característico de . Como matriz de rango 1, debe tener (al menos) factores de para tener en cuenta su espacio nulo. El valor propio "faltante" es , como se puede ver en el cálculo: $f(x)$ $D^{-1}J$ $f(x)$ $n-1$ $x$ $\sum d_i^{-1}$

D^{- 1} J (d_{1}^{- 1} \dots d_{n}^{- 1})^{T} = (\sum d_{i}^{- 1}) (d_{1}^{- 1} \dots d_{n}^{- 1})^{T}

$D^{-1}J\; (d_1^{-1}\ldots d_n^{-1})^T = \left(\sum d_i^{-1} \right) (d_1^{-1}\ldots d_n^{-1})^T$

Se deduce que el polinomio característico , es como se muestra arriba para , . $f(x) = x^{n-1} (x - \sum d_i^{-1})$ $f(1)$ $\det(I - D^{-1}J)$ $1 - \sum d_i^{-1}$

También tenga en cuenta que si , entonces , una matriz diagonal cuyo determinante es simplemente el producto de sus entradas diagonales. $Q = D-J$ $12I - Q - J = 12I - D + J - J = 12I - D$

hardmath
fuente

Hm .. es de hecho donde es la matriz de adyacencia de así que creo que este resultado puede no ser correcto. En particular, implicaría que el número de árboles de expansión de un gráfico está determinado por su secuencia de grados que no se cumple.

Q

$Q$

D - A

$D-A$

A

$A$

G

$G$

G

$G$

Jernej

Las entradas fuera de la diagonal de generalmente contendrán 0 y -1. La descomposición sugerida por Victor aprovecha la simetría y reduce el término principal en el conteo de operaciones de a . Existe un enfoque entero exacto, pero probablemente no sea necesario para su matriz de tamaño modesto y sus entradas. Si entiendo la construcción, es positivo definido por la misma razón que es.

Q

$Q$

L D L^{T}

$LDL^T$

\frac{2}{3} n^{3}

$\frac{2}{3}n^3$

\frac{1}{3} n^{3}

$\frac{1}{3}n^3$

12 I - Q - J

$12I-Q-J$

Q

$Q$

hardmath

@Jernej: Si crees que algo que dije es incorrecto, he creado una sala de chat basada en esta pregunta donde la discusión se puede enhebrar sin comentarios innecesarios aquí.

Hardmath

Si tiene una forma estructurada de enumerar los gráficos de los que desea calcular los determinantes, tal vez podría encontrar actualizaciones de bajo rango que lo transfieran de un gráfico a otro.

Si es así, podría usar el lema determinante de la matriz para calcular de manera económica el determinante del gráfico posterior que se enumerará utilizando su conocimiento del determinante del gráfico actual.

Es decir, para una matriz y los vectores : Esto puede generalizarse si U y V son matrices y es : $A$ $u,v$

det (A + u v^{T}) = (1 + v^{T} A^{- 1} u) det (A)

$\det(A+uv^T)=(1+v^T A^{-1} u)\det(A)$

n \times m

$n \times m$

A

$A$

n \times n

$n \times n$

det (A + U V^{T}) = det (I_{m} + V^{T} A^{- 1} U) det (A)

$\det(A+UV^T)=\det(I_m + V^TA^{-1}U)\det(A)$

Para calcular eficientemente el inverso, puede usar la fórmula de Sherman-Morrison para obtener el inverso de la matriz posterior de la actual:

(A + u v^{T})^{- 1} = A^{- 1} - \frac{A^{- 1} u v^{T} A^{- 1}}{1 + v^{T} A^{- 1} u}

$(A+uv^T)^{-1}=A^{-1}-\frac{A^{-1} uv^T A^{-1}}{1+v^T A^{-1} u}$

Ricardo
fuente