¿Es el algoritmo de Thomas la forma más rápida de resolver un sistema lineal tridiagonal disperso diagonalmente dominante simétrico

Me pregunto si el algoritmo de Thomas es la forma más rápida (¿probablemente?) De resolver un sistema tridiagonal disperso simétrico que domina diagonalmente en términos de complejidad algorítmica (no busca paquetes de implementación como LAPACK, etc.). Sé que tanto el algoritmo de Thomas como la multigrid son complejidad, pero ¿tal vez el factor constante para multigrid sea menor? No me parece que la multigrid pueda ser más rápida, pero no soy positivo. $O(n)$

Nota: Estoy considerando el caso donde las matrices son muy grandes. Se aceptan métodos directos o iterativos.

linear-solver sparse-matrix complexity multigrid James
fuente

Respuestas:

Creo que comparar un método iterativo (multigrid) con un método directo / exacto (Thomas) en términos de recuento exacto de la operación no es realmente significativo. IIRC, el recuento de operaciones de Thomas es de para cualquier sistema tridiagonal. La única vez que puedo imaginar una paliza multirredes que es concebible para un caso trivial de tener una solución lineal, e incluso entonces el costo de evaluar el residual en cada nivel sería comparable al costo de Thomas. $8N$

La utilidad de la multigrid radica en el hecho de que es general para matrices dispersas y no se limita a los sistemas tridiagonales. $O(N)$

Aurelio
fuente

Gracias. Me doy cuenta de que los métodos iterativos no son exactos. Debería haber especificado una tolerancia muy pequeña (digamos 10 ^ -15) y solo tratarla como "exacta" para fines de comparación.

James

@ user2697246 bueno, preguntaste sobre "probablemente" más rápido. La tasa de convergencia exacta para multigrid (o cualquier esquema iterativo) siempre dependerá de la solución en sí misma y de la suposición inicial: una solución lineal se resolverá de manera efectiva exactamente en un solo paso, mientras que algo más oscilatorio requerirá más operaciones. Thomas tiene un recuento de operaciones exacto y fijo para todos los casos. Hablando prácticamente, nunca vas a vencer a Thomas por resolver (en serie) un sistema tridiagonal para un caso no trivial.

Aurelius

@Aurelius ¿Se puede paralelizar el algoritmo de Thomas? Si no, ¡esa es una de las principales ventajas de multirredes!

Nick Alger

@NickAlger No, el algoritmo de Thomas es estrictamente serial, y sí, la paralelización es una gran ventaja para multirredes (aunque para el caso específico de un sistema tridiagonal sospecho que la latencia de comunicación lo mataría). Existe una técnica específica para sistemas tridiagonales llamada cíclico paralelo reducción (PCR) que es

, paralelizable por

, que he utilizado con éxito en las GPU.

O (N l o g N)

$O(N log N)$

N

$N$

Aurelius

Una corrección, el algoritmo de Thomas requiere operaciones 8N, no 9N. Además, ¿qué quiere decir con "multigrid ... teniendo una solución lineal"? Todos los sistemas considerados aquí son lineales.

Doug Lipinski

La respuesta corta es que el algoritmo de Thomas será más rápido que cualquier esquema iterativo para casi todos los casos. La excepción quizás sería aplicar una única iteración de un esquema iterativo muy simple como Gauss-Seidel, pero es muy poco probable que esto dé una solución aceptable. Además, esto está ignorando las preocupaciones de procesamiento paralelo.

$\mathcal O(n)$ $\mathcal O(n)$

$5N$ $3N$ $3N-2$ $2N-2$

Doug Lipinski
fuente

"Multigrid es una elección especialmente pobre en el caso de una matriz tri-diagonal porque aunque multigrid es O (n), la constante es bastante grande". Creo que esto también, pero googlear apareció una línea en el libro Multigrid de Trottenburg reclamando una constante de 0.1-0.2, declarada sin pruebas. No creo creer eso.

Aurelius

@Aurelius Interesante. Eso es claramente imposible en el caso general ya que hay entradas 3N en una matriz tridiagonal. Si el costo es ~ 0.1 * N, eso significa que nunca opera en la mayoría de las entradas.

Doug Lipinski

Sí, estamos en la misma página; simplemente evaluar una plantilla de 3 puntos requiere operaciones 3N. Solo estaba hojeando, así que tal vez malinterpreté totalmente la declaración, pero puedes verla por ti mismo en el extracto de Google Books.

Aurelius

La cita completa (pág. 21) es "Eficiencia en el sentido práctico significa que las constantes de proporcionalidad en esta declaración O (N) son pequeñas o moderadas. Este es, de hecho, el caso para multirredes: si se diseñan bien, los factores de convergencia independientes de h pueden hacerse muy pequeño (en el rango de 0.1-0.2 o incluso menos) y el recuento de operaciones por desconocido por paso de iteración también es pequeño ". El 0.1-0.2 se refiere a la reducción residual para cada ciclo de multigrid. La constante en el O (N) estaría en el orden de 1.5-2.0x, la matriz se multiplica por ciclo (con un total de una docena o dos ciclos).

Godric Seer

Ah, gracias @GodricSeer, eso tiene más sentido.

Aurelius

El optimizador puede vectorizar bucles de múltiples cuadrículas incluso en un solo núcleo. Por lo tanto, aunque el recuento de operaciones puede ayudar, no debemos olvidar que incluso en el mundo en serie, los procesadores tienen paralelismo vectorial y, por lo tanto, el tiempo de solución puede no ser exactamente lo que predecimos del análisis de costos.

Hasbestein
fuente