Actualmente estoy trabajando para resolver sistemas simétricos muy grandes (pero no positivos definidos), generados por algunos algoritmos determinados. Estas matrices tienen una buena dispersión de bloques que se puede usar para la resolución paralela. Pero no puedo decidir si debería usar un enfoque directo (como Multi-frontal) o uno iterativo (GMRES o MINRES preacondicionados). Todos mis estudios muestran que los solucionadores iterativos (incluso con una convergencia bastante rápida de 7 iteraciones internas) no pueden vencer al operador directo '\' en MATLAB. Pero en teoría, se supone que los métodos directos son más costosos. ¿Cómo está pasando esto? ¿Hay algún documento o documento actualizado para tal caso? ¿Puedo usar la dispersión de bloques en sistemas paralelos usando métodos directos tan eficientemente como solucionadores iterativos flexibles como GMRES?
fuente
Respuestas:
El solucionador directo disperso MUMPS puede manejar sistemas simétricos indefinidos y está disponible gratuitamente ( http://graal.ens-lyon.fr/MUMPS/ ). Ian Duff fue uno de los autores de MUMPS y MA57, por lo que los algoritmos tienen muchas similitudes.
MUMPS fue diseñado para computadoras paralelas de memoria distribuida, pero también funciona bien en máquinas de un solo procesador. Si lo vincula con una biblioteca BLAS de subprocesos múltiples, puede lograr aceleraciones razonables en procesadores multinúcleo de memoria compartida.
No dijo cuán grande es "muy grande", pero MUMPS también tiene una capacidad fuera de núcleo para manejar problemas donde la matriz factorizada no cabe en la memoria disponible.
fuente
El problema general que sufren los solucionadores directos es el fenómeno de relleno, lo que significa que la inversa de una matriz dispersa puede ser densa. Esto conduce a enormes requisitos de memoria si la estructura de la matriz no es "adecuada".
Hay intentos de solucionar estos problemas, y la función predeterminada de
luMATLAB emplea algunos de ellos. Consulte http://www.mathworks.de/de/help/matlab/ref/lu.html para obtener una descripción general de las permutaciones, la escala diagonal y demás. Lo mismo es cierto, por supuesto, para paquetes más avanzados como MUMPS ( http://graal.ens-lyon.fr/MUMPS/ ).Sin embargo, en general, si su problema es lo suficientemente grande, alcanzará ese límite de memoria y deberá usar métodos iterativos (Krylov).
Si su problema es simétrico e indefinido, MINRES puede ser la opción obvia. Sin embargo, tenga en cuenta que GMRES y MINRES hacen lo mismo en aritmética exacta si el problema es simétrico, pero GMRES tiende a sufrir menos por la pérdida de ortogonalidad. Por lo tanto, algunas personas consideran GMRES como "la mejor implementación de MINRES".
En cualquier caso, probablemente se beneficiará del preacondicionamiento de su sistema. Si no desea perder tiempo en adaptar un preacondicionador, es posible que el preacondicionador de factorización LU (ILU) incompleto ya lo lleve a alguna parte.
fuente
Cualquier solucionador iterativo puede vencer a los métodos directos solo si el problema es lo suficientemente grande (grande, depende de varios factores, como el almacenamiento requerido, la eficiencia de la implementación). Y también cualquier método krylov (por ejemplo, GMRES) es bueno solo si usa un preacondicionamiento apropiado (en la práctica). Si no está utilizando ningún preacondicionamiento, los métodos de krylov no son de utilidad en general. Yo también trabajo con matrices de bloques dispersos (estos provienen de aplicaciones PDE) y observé que el solucionador de krylov precondicionado (superposición de aditivos schwarz) (ya sea GMRES reiniciado o BiCG-Stab) junto con una corrección gruesa de cuadrícula (o una cuadrícula múltiple) son escalables para estos tipo de matrices
fuente
El operador '\' de Matlab es altamente eficiente debido a la programación de primer nivel. Puede ver algo de la idea y cómo usaron todos los atajos posibles en el libro de Timothy Davis.
En matlab puedes usar gmres, que está bien desarrollado y es estable. Probablemente las minas, que en teoría deberían ser ideales para su caso, pueden no ser tan confiables (al menos mi experiencia lo dice). Debería obtener una eficiencia igual o mayor de matlab gmres si
Para sistemas aún más grandes, use una herramienta como PETSc.
fuente
Si su matriz tiene una dimensión de decenas de miles o menos, use un método directo, aunque no hay muchos métodos directos disponibles libremente para sistemas simétricos indefinidos (en realidad, ninguno de los que conozco son de código abierto). Hay MA57 de HSL, pero solo es gratis para uso académico. Ciertamente puede ignorar la simetría y usar UMFPACK .
Alrededor de las decenas de cientos de dimensiones, el uso de memoria de un método directo comienza a exceder lo que una computadora de escritorio típica puede manejar razonablemente, por lo que a menos que tenga una máquina de memoria compartida robusta, deberá pasar a métodos iterativos. Para problemas indefinidos, puede especializarse BiCG (gradiente de biconjugado) para sistemas simétricos, aunque es posible un desglose. Existe un MINRES-QLP recientemente lanzado para sistemas simétricos que proporciona más estabilidad numérica.
Los dos métodos requieren implementaciones bastante diferentes, ya que para los métodos directos realmente necesita formar la matriz, mientras que en el enfoque iterativo, generalmente no formará la matriz explícitamente.
Existen varias razones por las cuales un enfoque puede ser más rápido que el otro, especialmente en función de la dimensión de la matriz. Para sistemas muy mal condicionados, los métodos iterativos pueden estancarse bastante mal. Para las matrices no tan escasas, los métodos directos terminan creando mucho relleno, lo que ralentiza mucho las cosas. Además, los métodos directos en Matlab están altamente optimizados (usa UMFPACK o MA57 internamente), mientras que los métodos iterativos generalmente se codifican directamente en Matlab, y hay menos oportunidades para explotar BLAS de nivel 3 ya que los cuellos de botella son la aplicación de matvecs y productos de punto.
fuente