Preacondicionamiento

El preacondicionamiento transforma un sistema lineal en uno equivalente con un espectro más favorable, de modo que un solucionador iterativo converge en muchos menos pasos; a menudo es el factor más importante en el rendimiento de los solucionadores dispersos grandes.

Definition

Un preacondicionador es una matriz, aplicada implícita o explícitamente a un sistema lineal, que aproxima la matriz de coeficientes o su inversa para que el sistema preacondicionado tenga propiedades espectrales que conduzcan a una convergencia mucho más rápida de un método iterativo.

Scope

Este tema abarca la idea de una inversa aproximada que agrupa los valores propios o reduce el número de condición, las principales familias de preacondicionadores —diagonal y diagonal por bloques, factorizaciones LU y Cholesky incompletas, inversas aproximadas dispersas, y preacondicionadores de descomposición de dominio y multigrid— y la compensación entre la eficacia de un preacondicionador y su costo de construcción y aplicación.

Core questions

• ¿Cómo cambia un preacondicionador el espectro de un sistema para acelerar la convergencia iterativa?
• ¿Qué hace que un preacondicionador sea bueno, equilibrando la calidad de la aproximación con el costo de construcción y aplicación?
• ¿Cómo se construyen las factorizaciones incompletas y las inversas aproximadas dispersas?
• ¿Cuándo se utilizan los métodos multigrid o de descomposición de dominio como preacondicionadores en lugar de solucionadores independientes?

Key theories

Transformación espectral

La aplicación de un preacondicionador que aproxima la inversa de la matriz produce un operador preacondicionado cuyos valores propios están agrupados o cuyo número de condición se reduce; dado que la convergencia de Krylov depende del espectro, esto puede reducir el número de iteraciones en órdenes de magnitud.

Preacondicionadores de factorización incompleta

Las factorizaciones LU incompleta y Cholesky incompleta calculan factores triangulares aproximados mientras descartan el relleno más allá de un patrón de dispersión o umbral elegido, produciendo un preacondicionador económico que captura gran parte de la acción de la matriz.

Mechanisms

Se elige un preacondicionador M de modo que la resolución de sistemas con M sea económica y el operador preacondicionado esté cerca de la identidad, agrupando sus valores propios. El preacondicionamiento diagonal (Jacobi) simplemente reescala; las factorizaciones LU o Cholesky incompletas construyen factores triangulares dispersos aproximados al eliminar entradas pequeñas o fuera de patrón durante la eliminación; las inversas aproximadas dispersas construyen directamente una M dispersa que aproxima la inversa de modo que solo se necesitan productos matriz-vector. Los preacondicionadores más potentes aplican un ciclo multigrid o una resolución de descomposición de dominio por iteración. En cada caso, el preacondicionador se aplica dentro de cada paso de un método de Krylov, y su diseño equilibra qué tan bien aproxima la inversa con cuánto cuesta formarlo y aplicarlo.

Clinical relevance

El preacondicionamiento es decisivo para resolver los enormes sistemas mal condicionados de las discretizaciones de EDP y la optimización a gran escala; el preacondicionador adecuado puede convertir una iteración que se estanca en una que converge en un puñado de pasos, y la elección y el ajuste de los preacondicionadores es una preocupación práctica central en el software de ciencia e ingeniería computacional.

History

El preacondicionamiento creció junto con los métodos de Krylov a partir de la década de 1970, con factorizaciones incompletas introducidas por Meijerink y van der Vorst en 1977 y una amplia gama de preacondicionadores algebraicos y multinivel desarrollados desde entonces; ahora se reconoce que a menudo es más importante para el rendimiento del solucionador que la elección del propio método de Krylov.

Key figures

• Yousef Saad
• Michele Benzi
• Henk van der Vorst
• Olof Widlund

Seminal works

• saad2003
• benzi2002

Frequently asked questions

¿Qué hace que un preacondicionador sea bueno?

Un buen preacondicionador aproxima de cerca la inversa de la matriz para que el sistema preacondicionado sea fácil para el método iterativo, pero es económico de construir y aplicar. El arte consiste en equilibrar estos objetivos contrapuestos: un preacondicionador más preciso cuesta más por paso, pero necesita menos pasos.

¿Se puede usar un solucionador como preacondicionador?

Sí. Un solo ciclo de multigrid o una resolución de descomposición de dominio se usa con frecuencia como preacondicionador dentro de un método de Krylov, combinando la robustez de la iteración de Krylov con la rápida reducción de errores del solucionador interno.