1 Laboratorio de cómputo científicoPRECONDICIONAMIENTO Teoría y Aplicaciones Dr. Pablo Barrera Sánchez Mat. Luis Alberto Vázquez Maison Facultad de Ciencias, UNAM Laboratorio de cómputo científico

2 La solución de sistemas linealesAparece en diversos campos del computo científico Solución de Ecuaciones Diferenciales Parciales (EDP) Métodos clásicos: Tipo SOR (Jacobi, Gauss-Sidel) Elim. Gaussiana (Fact. LU, Choleski) Métodos de Krylov (no tan clásicos): GMRES, GC, BiGCStab

3 Sistemas sparse de dimensión grandeMétodos clásicos: Costo computacional alto Métodos de Krylov: Convergencia lenta

4 Un precondicionador para el sistemaEs un operador M tal que uno de los siguientes sistemas es “fácil” de resolver:

5 Problema General: Determinar un operador M tal que:1) 2) La construcción y almacenaje de M son económicos 3) El sistema es mas fácil que

6 Posibles formas para M Diagonales de A Factorización de A

7 Algunos ejemplos

8

9

10 EDP

11

12 El efecto “visible” de un precondicionador es el de disminuir el número de iteraciones necesarias para que un método de solución converja El efecto “oculto” es el de cambiar las propiedades de los eigenvalores de A para disminuir su condición

13

14 Error relativo sin precondicionamiento 10e+0Error relativo con precondicionamiento 10e-7

15 ¿Cómo elegir un buen precondicionador?¡¡ Buena pregunta !! Analizar el sistema: Propiedades de A Estructura de A ¿Que representa?

16 Factorizaciones incompletasIdea básica Definir un conjunto de índices bajo una condición particular Aplicar factorización LU considerando : Formas comunes para

17 Llenado de una matriz

18 GRADIENTE CONJUGADO Calcular Calcular Para j=1,… Para j=1,… Fin Fin 1)2) 2) 3) 3) (3-a) 4) 4) 5) 5) Fin Fin

19 No necesariamente es una matrizUn precondicionador puede darse como una rutina que resuelve el sistema Existen problemas donde el sistema de ecuaciones correspondiente no es construido explícitamente

20 Discretizacion por diferencias finitas sobre una malla de dimensión NLa estructura de la matriz es conocida El sistema no es construido explícitamente, es decir, no se tiene la matriz A

21 La ecuación que se desea resolver es de tipo ElípticoLa ecuación elíptica mas simple es la ecuación de Poisson Los sistemas lineales de ambas ecuaciones tienen estructuras similares Se conocen técnicas muy eficientes para resolver la ecuación de poisson sobre un rectángulo, basadas principalmente en el uso de la transformada rápida de Fourier (Fast Poisson Solvers) Una rutina de solución rápida de Poisson es un buen precondicionador para resolver el sistema correspondiente a una ecuación elíptica

22 N=60 (3600 variables)

23 GRADIENTE CONJUGADO Calcular 0) Para j=1,… 1) 2) 3) (3-a) 4) 5) Fin

24 Rutina de solución para un sistema particular :Donde la matriz puede no ser conocida explícitamente Posibles rutinas: Solución de sistemas tridiagonales Sistemas triangulares (Substitución) Cualquier solución implícita Que sea “Fácil” toma otro significado

25 ¿Posibles rutinas?: SOR (Métodos tradicionales) Multigrid Métodos de Krylov La solución es solo aproximada, cada vez que se llama a la rutina se obtiene una aproximación con diferente precisión Mas de un precondicionador?

26 GRACIAS