¿Qué pautas debo usar al buscar buenos métodos de preacondicionamiento para un problema específico?

Para la solución de grandes sistemas lineales utilizando métodos iterativos, a menudo es interesante introducir el preacondicionamiento, por ejemplo, resolver , donde se usa aquí para el preacondicionamiento a la izquierda del sistema. Por lo general, deberíamos tener ese y proporcionar la base para (mucho más) solución eficiente o reducción de recursos computacionales (por ejemplo, almacenamiento de memoria) en comparación con la solución del sistema original (es decir, cuando $Ax=b$ $M^{-1}(Ax=b)$ $M$ $M^{-1}\approx A^{-1}$ $M=A$ ) Sin embargo, ¿qué pautas debemos utilizar para elegir el preacondicionador? ¿Cómo hacen esto los practicantes para su problema específico?

linear-algebra iterative-method preconditioning Allan P. Engsig-Karup
fuente

Incluso para una clase particular de ecuaciones, esto requeriría una respuesta muy larga y detallada ...

Jack Poulson

Debería ser posible sugerir estrategias heurísticas sobre cómo se pueden elegir los preacondicionadores. Por ejemplo, dado un problema, ¿qué hacen los practicantes en la práctica para tratar de encontrar un buen preacondicionador? ¿Simplemente comienza con un preacondicionador diagonal básico basado en extraer la diagonal de

? ¿o?

A

$A$

Allan P. Engsig-Karup

Voy a canalizar a @MattKnepley y decir que la acción apropiada es hacer una búsqueda de literatura. Si eso falla, pruebe todas las opciones fácilmente disponibles en un problema razonablemente grande. Si eso falla, piense profundamente en la física y cómo puede encontrar una solución aproximada al problema a bajo costo, y úsela como preacondicionador.

Jack Poulson

@JackPoulson: Dado que esta pregunta está en una línea similar a ¿Qué escaso solucionador de sistemas lineales usar? y Cómo elegir un solucionador lineal escalable , me parece un tema (aunque amplio). Dado que su comentario es básicamente una respuesta, ¿podría convertirlo en una respuesta?

Geoff Oxberry

He comenzado una recompensa por esta pregunta, pero también estoy interesado en ver más preguntas en este sentido que podrían estar mejor planteadas o restringidas a una clase específica de problemas.

Aron Ahmadia

Respuestas:

Originalmente no quería dar una respuesta porque esto merece un tratamiento muy largo, y espero que alguien más lo siga dando. Sin embargo, ciertamente puedo dar una breve descripción del enfoque recomendado:

Realizar una búsqueda bibliográfica exhaustiva .
Si eso falla, pruebe con todos los preacondicionadores que tengan sentido para poder tenerlos en sus manos. MATLAB, PETSc y Trilinos son buenos entornos para esto.
Si eso falla, debe pensar cuidadosamente sobre la física de su problema y ver si es posible encontrar una solución aproximada barata, tal vez incluso una versión ligeramente modificada de su problema.

Ejemplos de 3 son versiones laplacianas desplazadas de Helmholtz y el trabajo reciente de Jinchao Xu sobre el preacondicionamiento del operador biharmónico con laplacianos.

Jack Poulson
fuente

¡Gracias! El resto de este comentario cumple con el límite mínimo de caracteres.

Geoff Oxberry

Otros ya han comentado sobre el tema del preacondicionamiento de lo que llamaré matrices "monolíticas", es decir, por ejemplo, la forma discretizada de una ecuación escalar como la ecuación de Laplace, la ecuación de Helmholtz o, si desea generalizarla, el valor vectorial ecuación de elasticidad. Para estas cosas, está claro que el multigrid (ya sea algebraico o geométrico) es el ganador si la ecuación es elíptica, y para otras ecuaciones no es tan clara, pero algo como SSOR a menudo funciona razonablemente bien (por algún significado de "razonable").

Para mí, la gran revelación ha sido qué hacer con los problemas que no son monolíticos, por ejemplo, para el operador de Stokes Cuando comencé con el análisis numérico hace unos 15 años, creo que la gente tenía la esperanza de que se pudieran aplicar las mismas técnicas a las matrices anteriores, y la dirección de la investigación era probar directamente multirredes o utilizar generalizaciones de SSOR (usando " puntos suaves "como Vanka) y métodos similares. Pero esto se ha desvanecido ya que no funciona muy bien.

(\begin{matrix} UN & si \\ {si}^{T} & 0 0 \end{matrix}) .

$\begin{pmatrix} A & B \\ B^T & 0 \end{pmatrix}.$

Lo que vino a reemplazar esto fue lo que inicialmente se denominó "preacondicionadores basados en la física" y luego simplemente (y tal vez con mayor precisión) "preacondicionadores de bloque" como el de Silvester y Wathen. Estos a menudo se basan en eliminaciones de bloques o complementos de Schur y la idea es construir un preacondicionador de tal manera que uno pueda reutilizar preacondicionadores para bloques individuales que funcionan bien. En el caso de la ecuación de Stokes, por ejemplo, el preacondicionador Silvester / Wathen usa que la matriz

{(\begin{matrix} UN & si \\ 0 0 & {si}^{T} {UN}^{- 1} si \end{matrix})}^{- 1}

$\begin{pmatrix} A & B \\ 0 & B^T A^{-1} B \end{pmatrix}^{-1}$ cuando se usa como preacondicionador con GMRES daría lugar a la convergencia en exactamente dos iteraciones. Como es triangular, la inversión también es mucho más simple, pero aún tenemos el problema de qué hacer con los bloques diagonales, y allí se usan aproximaciones:

donde la tilde significa reemplazar el inverso exacto por una aproximación. Esto es a menudo mucho más simple: como el bloque

es un operador elíptico,

(\begin{matrix} \tilde{{UN}^{- 1}} & si \\ 0 0 & \tilde{({si}^{T} {UN}^{- 1} si)^{- 1}} \end{matrix})

$\begin{pmatrix} \widetilde{A^{-1}} & B \\ 0 & \widetilde{(B^T A^{-1} B)^{-1}} \end{pmatrix}$

A

$A$

\tilde{A^{- 1}}

$\widetilde{A^{-1}}$ está bien aproximado por un ciclo V multirredes, por ejemplo, y resulta que aquí,

está bien aproximado por una ILU de una matriz de masa.

\tilde{(B^{T} A^{- 1} B)^{- 1}}

$\widetilde{(B^T A^{-1} B)^{-1}}$

Esta idea de trabajar con los bloques individuales que comprenden la matriz y reutilizar los preacondicionadores en los individuales ha demostrado ser enormemente poderosa y ha cambiado por completo la forma en que pensamos hoy en preacondicionamiento de los sistemas de ecuaciones. Por supuesto, esto es relevante porque la mayoría de los problemas reales son, de hecho, sistemas de ecuaciones.

Wolfgang Bangerth
fuente

Hombre, sí, ¡quería la recompensa! ;-)

Wolfgang Bangerth

En su segundo párrafo: "Pero esto se ha desvanecido ya que no funciona muy bien". ¿Puedes darme una idea de por qué no funciona muy bien? ¿Hay circunstancias bajo las cuales puede funcionar?

Andrew T. Barker

La razón por la cual la multirrejilla directa aplicada a sistemas completos no ha demostrado ser tan exitosa es que la más suave necesita conservar las propiedades estructurales de la ecuación, y eso no es trivial de lograr. Por ejemplo, si desea aplicar la cuadrícula múltiple a las ecuaciones de Stokes, debe tener un suavizador que, dado un vector libre de divergencia, le proporcione un vector libre de divergencia. Hay tales suavizadores para Stokes, pero su construcción no es trivial y generalmente le quita la calidad como suavizador / solucionador. Se vuelve mucho más difícil preservar propiedades en casos más generales.

Wolfgang Bangerth

En cuanto a generalizar cosas como Jacobi / SSOR / etc. a los sistemas: la mayoría de estos métodos requieren que las entradas diagonales de la matriz sean distintas de cero. Obviamente, ese no es el caso de Stokes. Entonces, el siguiente método más simple es no mirar las filas individuales de la matriz sino los bloques de filas, por ejemplo, todas las filas para los DoF asociados con un solo vértice. Estos se denominan "suavizadores de puntos" (punto como en el vértice) y funcionan hasta cierto punto, pero sufren la misma degradación del rendimiento que Jacobi / SSOR una vez que los problemas se vuelven grandes. Para evitar eso, un preacondicionador necesita intercambiar información globalmente como multigrid.

Wolfgang Bangerth

Multigrid es famoso por su ineficacia para resolver Helmholtz porque, principalmente porque los modos oscilatorios de baja energía son difíciles de suavizar o representar en un espacio grueso. Se han realizado algunos trabajos en multirredes de rayos de onda, pero la formulación es muy técnica y no es una metodología madura en este momento. Tenga en cuenta que los sistemas no simétricos también se pueden resolver utilizando este tipo de descomposición de bloques. Dependiendo de la elección de las variables, (por ejemplo, primitivo versus conservador), puede ser necesario un cambio de base dentro del preacondicionador para exponer la estructura bloqueada.

Jed Brown

Jack ha dado un buen procedimiento para encontrar un preacondicionador. Intentaré responder una pregunta: "¿Qué hace que un buen preacondicionador?". La definición operacional es:

Un preacondicionador M acelera la solución iterativa de $A x = b$ $M^{-1}$ $A^{-1}$

Sin embargo, esto no nos da ninguna idea sobre el diseño de un preacondicionador. La mayoría de los preacondicionadores se basan en la manipulación del espectro del operador. Genéricamente, los métodos de Krylov convergen más rápido cuando los valores propios están agrupados, ver Iteraciones matriciales o Funciones meromórficas y Álgebra lineal . A veces podemos probar que los resultados de un preacondicionador son solo unos pocos valores propios únicos, por ejemplo, una nota sobre preacondicionamiento para sistemas lineales indefinidos .

Una estrategia común es ejemplificada por Multigrid. Los preacondicionadores relajantes (aquí suavizadores) como SOR eliminan los componentes de alta frecuencia en el error. Cuando el residual se proyecta en una grilla gruesa, los componentes de error de frecuencia más baja se vuelven de frecuencia más alta y pueden ser atacados nuevamente por SOR. Esta estrategia básica subyace en versiones más complicadas de MG, como AMG. Tenga en cuenta que en la parte inferior, el solucionador debe resolver con precisión las frecuencias más bajas del error.

Otra estrategia consiste en resolver la ecuación en pequeños subespacios, que es exactamente lo que están haciendo los solucionadores de Krylov. En la forma más simple, este es el método Kaczmarz o el Método Aditivo Schwarz . La tensión teórica avanzada aquí, la descomposición del dominio , se concentra en la aproximación espectral del error en la interfaz, ya que se supone que los dominios se resuelven con bastante precisión.

$A$

Matt Knepley
fuente

Gracias por su respuesta. Cualquier experiencia con respecto a cuán lejos deberíamos llegar para demostrar que el preacondicionamiento funciona para sistemas grandes, y posiblemente cómo esto puede o debe hacerse en la práctica. Según mi experiencia, para muchos sistemas tenemos que confiar en la intuición, la heurística, etc.

Allan P. Engsig-Karup

Creo que la intuición está yendo demasiado lejos. Lo que veo en la práctica es una prueba de un sistema simple. Luego, un argumento de que alguna modificación debería ser insensible a un parámetro, o un cierto tipo de variación. Luego, los experimentos numéricos que muestran que funciona incluso fuera de este modelo de variación.

Matt Knepley