¿Hay alguna heurística para optimizar el método de relajación excesiva sucesiva (SOR)?

10

Según tengo entendido, la relajación sucesiva funciona eligiendo un parámetro y utilizando una combinación lineal de una iteración (cuasi) de Gauss-Seidel y el valor en el paso de tiempo anterior ... eso es 0≤ω≤2

uk+1=(ω)ugsk+1+(1−ω)uk

'cuasi' porque incluye la información más reciente actualizada de acuerdo con esta regla, en cualquier momento. (tenga en cuenta que en , esto es exactamente gauss-seidel). ω=1ugsk+1ω=1

En cualquier caso, he leído que en la elección óptima para (de modo que la iteración converja más rápido que cualquier otro) se aproxima a 2 para el problema de Poisson a medida que la resolución espacial se acerca a cero. ¿Existe una tendencia similar para otros problemas simétricos, diagonalmente dominantes? Es decir, ¿hay alguna manera de elegir omega de manera óptima sin incluirlo en un esquema de optimización adaptativa? ¿Existen otras heurísticas para otros tipos de problemas? ¿Qué tipo de problemas sería la sub-relajación ( ) óptima?ω < 1ωω<1

linear-algebra optimization iterative-method Paul
fuente
No es exactamente su pregunta, pero vea Salakhutdinov y Roweis, Adaptive Overrelaxed Bound Optimization Methods 2003, 8p. ( Las aceleraciones adaptativas tienen un alto rendimiento por dólar, pero son imposibles de analizar, por lo que aquí no se trata).
denis

Respuestas:

12

Jacobi amortiguado

Supongamos que la matriz tiene diagonal . Si el espectro de encuentra en el intervalo del eje real positivo, entonces la matriz de iteración de Jacobi con factor de amortiguamiento tiene espectro en el rango , por lo que minimizar el radio espectral con da un factor de convergencia de Si , entonces este factor de convergencia es muy pobre, como se esperaba. Tenga en cuenta que es relativamente fácil estimarD D - 1 A [ a , b ] ω B Jacobi = I - ω D - 1 A [ 1 - ω b , 1 - ω a ] ω opt = 2ADD−1A[a,b]ω

BJacobi=I−ωD−1A
[1−ωb,1−ωa] ρopt=1-2a
ωopt=2a+b
a≪bba
ρopt=1−2aa+b=b−aa+b.
a≪bbutilizando un método de Krylov, pero es bastante caro para estimar .a

Sucesiva sobre-relajación (SOR)

Young (1950) demostró un resultado óptimo para SOR aplicarse a matrices con la llamada de la propiedad A , de pedido consistente , y valores propios reales positivos de . Dado un valor propio máximo de la matriz de iteración de Jacobi no amortiguada ( está garantizada por los supuestos en este caso), el factor de amortiguación óptimo para SOR es que da como resultado una tasa de convergencia de Tenga en cuenta que acerca a 2 cuando .μ max I - D - 1 A μ max < 1 ω opt = 1 + ( μ maxD−1AμmaxI−D−1Aμmax<1ρopt=ωopt-1.ωoptμmax→1

ωopt=1+(μmax1+1−μmax2)2
ρopt=ωopt−1.
ωoptμmax→1

Comentarios

Ya no es 1950 y realmente no tiene sentido usar métodos iterativos estacionarios como solucionadores. En cambio, los usamos como suavizadores para multirredes. En este contexto, solo nos interesa apuntar al extremo superior del espectro. La optimización del factor de relajación en SOR hace que SOR produzca muy poca amortiguación de altas frecuencias (a cambio de una mejor convergencia en frecuencias más bajas), por lo que generalmente es mejor usar Gauss-Seidel estándar, correspondiente a en SOR. Para problemas no simétricos y problemas con coeficientes altamente variables, el SOR poco relajado ( ) puede tener mejores propiedades de amortiguación.ω < 1ω=1ω<1

Estimar ambos valores propios de es costoso, pero el valor propio más grande se puede estimar rápidamente usando algunas iteraciones de Krylov. Los suavizadores polinómicos (preacondicionados con Jacobi) son más efectivos que las iteraciones múltiples de Jacobi amortiguado y son más fáciles de configurar, por lo que deberían preferirse. Consulte esta respuesta para obtener más información sobre los suavizadores polinómicos.D−1A

A veces se afirma que SOR no debe usarse como preacondicionador para métodos de Krylov como GMRES. Esto proviene de la observación de que el parámetro de relajación óptimo debe colocar todos los valores propios de la matriz de iteración en un círculo centrado en el origen. El espectro del operador preacondicionado(1

BSOR=1−(1ωD+L)−1A
(1ωD+L)−1Atiene valores propios en un círculo del mismo radio, pero centrado en 1. Para operadores mal condicionados, el radio del círculo es bastante cercano a 1, por lo que GMRES ve valores propios cercanos al origen en un rango de ángulos, lo que generalmente no es bueno para la convergencia En la práctica, GMRES puede converger razonablemente cuando se preacondiciona con SOR, especialmente para problemas que ya están bastante bien condicionados, pero otros preacondicionadores a menudo son más efectivos.
Jed Brown
fuente
44
Estoy de acuerdo en que ya no es 1950: o), sin embargo, no estoy de acuerdo con que ya no tenga sentido usar solucionadores iterativos de papelería. Podemos lograr la eficiencia de los libros de texto de múltiples cuadrículas utilizando un solucionador iterativo estacionario para un solucionador de aplicaciones de ingeniería basado en solucionadores de superficie libre no lineales de alto orden (tanto ecuaciones de flujo potencial como de ecuaciones de Euler). La eficiencia fue tan buena como un método de subespacio GMRES krylov preacondicionado con precisión alcanzable (nuestro pub reciente se encuentra aquí enlinelibrary.wiley.com/doi/10.1002/fld.2675/abstract que sirve como prueba de concepto).
Allan P. Engsig-Karup
1
Está utilizando Gauss-Seidel como un suavizador para multirredes (que es donde pertenecen métodos como SOR). Si el multigrid funciona bien, tampoco es necesario un método externo de Krylov (aunque su trabajo no muestra esas comparaciones). Tan pronto como la multigrid comience a perder eficiencia (por ejemplo, más de 5 iteraciones para alcanzar el error de discretización), generalmente vale la pena ajustar un método de Krylov alrededor del ciclo de multigrid.
Jed Brown
Todo el método es una cuadrícula p con suavizado de tipo GS, sin embargo, el método completo se puede escribir como un método iterativo estacionario ya que todos los operadores son constantes. Puede verlo como un método de Richardson preacondicionado con M un preacondicionador construido a partir del método multirredes. Se han realizado análisis pero aún no se han publicado. En realidad, este trabajo fue en la otra dirección que propones. El método krylov en este trabajo (un GMRES) se descartó y luego se convirtió en un método de cuadrícula de alto orden, ya que descubrimos que era igual de eficiente (y con requisitos de memoria reducidos).
Allan P. Engsig-Karup
El uso de - y -multigrid es, por supuesto, independiente de si se usa un método de Krylov en el exterior. Los costos relativos de varias operaciones son, por supuesto, diferentes para las GPU en comparación con las CPU, y existe una variabilidad entre las implementaciones. Richardson preacondicionado es solo un método de corrección de defectos. También lo son los métodos no lineales de Newton y Picard (si están escritos como tales). Otros métodos no lineales (NGMRES, BFGS, etc.) también usan el historial y pueden ser mejores dependiendo de la fuerza relativa de la no linealidad. h pphp
Jed Brown
Tenga en cuenta que en los suavizadores de cuadrículas múltiples, a veces es preferible (si la arquitectura lo permite), hacer que el acoplamiento de orden alto / orden bajo sea multiplicativo. Esto también extiende la formulación de "Richardson precondicionado". (Tuve una discusión en una conferencia la semana pasada con un tipo que quería ver esencialmente todos los métodos como Richardson precondicionado con iteración anidada, lo que no creo que sea un beneficio particular sobre otras declaraciones de composición de solucionador. No sé si es relevante para usted, pero sus puntos me recordaron la discusión.)
Jed Brown