¿Qué pautas debo seguir al elegir un solucionador de sistema lineal disperso?

49

Los sistemas lineales dispersos aparecen con frecuencia creciente en las aplicaciones. Uno tiene muchas rutinas para elegir para resolver estos sistemas. En el nivel más alto, existe una línea divisoria entre los métodos directos (p. Ej., Eliminación gaussiana escasa o descomposición de Cholesky, con algoritmos de ordenamiento especiales y métodos multifrontales) e iterativos (p. Ej., GMRES, gradiente (bi-) gradiente conjugado).

¿Cómo se determina si se usa un método directo o iterativo? Habiendo hecho esa elección, ¿cómo se elige un algoritmo particular? Ya sé sobre la explotación de la simetría (p. Ej., Usar gradiente conjugado para un sistema definido positivo simétrico disperso), pero ¿hay otras consideraciones como esta para considerar al elegir un método?

JM
fuente

Respuestas:

33

Lo importante al elegir solucionadores iterativos es el espectro del operador, consulte este documento . Sin embargo, hay tantos resultados negativos, vea este documento donde ningún solucionador iterativo gana para todos los problemas y este documento en el que demuestran que pueden obtener cualquier curva de convergencia para GMRES para cualquier espectro. Por lo tanto, parece imposible predecir el comportamiento de los solucionadores iterativos, excepto en algunos casos aislados. Por lo tanto, su mejor opción es probarlos todos, utilizando un sistema como PETSc , que también tiene solucionadores directos.

Matt Knepley
fuente
2
"Tira todo lo que puedas" fue el consejo al que estaba acostumbrado. :) El tercer artículo al que enlazan es algo que no he visto antes; ¡gracias por eso!
JM
2
Matt tiene una gran respuesta, pero debe tomarla dentro del contexto de la comunidad de la que proviene (computación científica a gran escala). Encontrará que para problemas pequeños (digamos, menos de cien mil incógnitas), los solucionadores directos superan ampliamente a los métodos iterativos si el problema no es muy elíptico. No he visto ningún buen trabajo general en la literatura que lo guíe hacia una estrategia inicial, lo cual es un poco vergonzoso para mí.
Aron Ahmadia
55
La estimación de Aron es buena pero depende en gran medida del relleno, ya que los métodos directos dispersos generalmente agotan la memoria antes de agotar la paciencia.
Matt Knepley
18

La elección entre métodos directos e iterativos depende de los objetivos y el problema en cuestión.

Para los métodos directos, podemos notar:

  • La matriz de coeficientes del sistema lineal cambia en el transcurso del cálculo y puede que, para sistemas dispersos, agote los requisitos de memoria y aumente el esfuerzo de trabajo debido al relleno
  • Debe completarse para dar resultados útiles
  • La factorización se puede reutilizar en los pasos posteriores si hay varios lados derechos
  • Solo se puede usar para resolver sistemas lineales.
  • Raramente falla.

Para los métodos iterativos, podemos notar:

  • El objetivo es dar un resultado parcial solo después de un pequeño número de iteraciones.
  • El esfuerzo de la solución debe ser menor que los métodos directos para el mismo problema.
  • Económico con respecto al almacenamiento (sin relleno)
  • A menudo fácil de programar.
  • Una solución aproximada conocida puede ser explotada.
  • Algunas veces son rápidas y otras no (algunas veces incluso divergentes).
  • Para problemas complejos, los métodos iterativos son considerablemente menos robustos en comparación con los métodos directos.

¿Directrices para cuándo usar métodos directos o iterativos?

  • Métodos iterativos cuando la matriz de coeficientes es escasa y los métodos directos no pueden explotar la dispersión de manera eficiente (evite crear relleno).
  • Métodos directos para múltiples lados derechos.
  • Los métodos iterativos pueden ser más eficientes si la precisión es menos preocupante
  • Métodos iterativos para sistemas no lineales de ecuaciones.
Allan P. Engsig-Karup
fuente
8
Creo que es importante tener en cuenta que los métodos directos no siempre son mejores para múltiples lados derechos. Quizás sean mejores para derecha, pero si el método iterativo es mientras que el método directo es , sigue siendo ventajoso usar el solucionador iterativo para lados a la derecha. O ( n ) O ( n 2 ) O ( 1 )O(n)O(n)O(n2)O(1)
Jack Poulson
8

Estoy completamente de acuerdo con las respuestas ya dadas. Quería agregar que todos los métodos iterativos requieren algún tipo de conjetura inicial. La calidad de esta suposición inicial a menudo puede afectar la tasa de convergencia del método que elija. Métodos como Jacobi, Gauss Seidel y Successive Over Relaxation funcionan para "suavizar" iterativamente el mayor error posible en cada paso ( consulte este documento para obtener más detalles) Los primeros pasos reducen el error de alta frecuencia bastante rápido, pero el error de baja frecuencia requiere muchas más iteraciones para suavizarlo. Esto es lo que hace que la convergencia sea lenta para estos métodos. En casos como este, podemos acelerar la convergencia resolviendo primero el error de baja frecuencia (por ejemplo, resolviendo el mismo problema en una malla más gruesa) y luego resolviendo el error de frecuencia más alta (por ejemplo, en una malla más fina). Si aplicamos este concepto recursivamente dividiendo y conquistando, obtenemos lo que se llama un método de cuadrícula múltiple. Incluso si el sistema lineal no es simétrico, existen implementaciones alternativas del método de cuadrícula múltiple para cualquier sistema de matriz dispersa no singular (por ejemplo, método de cuadrícula algebraica) que puede acelerar la convergencia del solucionador. Sin embargo, su escalabilidad en sistemas paralelos es objeto de mucha investigación..

Paul
fuente
55
Esta respuesta parece dar la impresión de que la efectividad de la multigrid proviene de encontrar una buena suposición inicial. En realidad, la suposición inicial es una preocupación menor por problemas lineales y realmente solo una preocupación por Multigrid completo. Multigrid funciona debido a la separación espectral. Tenga en cuenta que hacer que la cuadrícula funcione bien para problemas difíciles es un desafío importante. Multigrid funciona bastante bien en paralelo, ha sido el ingrediente clave en varios premios Gordon Bell y algunos paquetes de código abierto se ejecutan con alta eficiencia en las máquinas más grandes de la actualidad. Para implementaciones de GPU, mire la biblioteca CUSP.
Jed Brown
La mayoría de las veces una suposición inicial aleatoria es lo suficientemente buena. Al extraer valores propios utilizando el algoritmo de Lanczos, un vector aleatorio de inicio / reinicio sí ayuda. Los reinicios ocurren a veces en el algoritmo de Lanczos.
AnilJ
3

Falta una pieza importante de información en su pregunta: de dónde se originó la matriz. La estructura del problema que intentaba resolver tiene un gran potencial para sugerir un método de solución.

Si su matriz se originó a partir de una ecuación diferencial parcial con coeficientes suaves, será difícil superar un método de cuadrícula geométrica, en particular en tres dimensiones. Si su problema es menos regular, la multigrid algebraica es un buen método. Ambos generalmente combinados con los métodos de Krylov-space. Se pueden derivar otros solucionadores eficientes a partir de métodos multipolares rápidos o transformada rápida de Fourier.

Guido Kanschat
fuente