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

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?

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.

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.

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..

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.