iii. algoritmo solver: resoluciÓn del...
TRANSCRIPT
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
89
III. ALGORITMO SOLVER: RESOLUCIÓN DEL SISTEMA A*X=B
Tras el análisis del código de partida se observó que uno de los bloques
que se debían adaptar a tecnología CUDA para su aceleración era el
bloque encargado de la resolución de la ecuación propiamente dicha.
Sin embargo, este bloque poseía una complejidad que hizo necesario un
estudio previo y detallado de los algoritmos numéricos disponibles para
encontrar la opción más adecuada. En concreto se deseaba aprovechar la
particularidad de que el sistema es un sistema disperso.
La selección del método para implementar el Solver debe tener en
consideración ciertos factores:
- Velocidad de convergencia: Se prefieren aquellos métodos que
convergen rápidamente (en tiempo y no necesariamente en iteraciones).
- Memoria: Cuando se manejan matrices muy grandes, se deben evitar
algoritmos que manejan matrices en los pasos intermedios.
- Paralelismo: En principio CUBLAS se encarga de la paralelización de
modo óptimo.
- Sencillez: A la hora de implementar y codificar para evitar “bugs” y
un desarrollo rápido.
Tras un análisis de la literatura acerca de este caso se encontraron dos
alternativas que pasamos a describir:
1. MÉTODOS DIRECTOS
Los métodos directos tienen como objetivo resolver el problema en un
número finito de pasos y, aparte de errores por redondeo, encontrar una
solución exacta.
Generalmente estos métodos exigen más memoria que los métodos
iterativos. Por tanto se deben usar con reservas. De hecho éste factor
fue fundamental para descartarlos en nuestra implementación. En la
bibliografía consultada se indican para casos de matrices densas. Sin
embargo como ejemplo de método directo estudiamos el llamado de
Factorización o Descomposición QR.
a. DESCOMPOSICIÓN QR:
Es uno de los métodos que permiten una resolución fácil de un problema
Ax=b. La descomposición QR es la base del algoritmo QR utilizado para el
cálculo de los vectores y valores propios de una matriz.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
90
La idea se basa en descomponer la matriz A en dos matrices Q y R tal que
A=QR donde Q es una matriz ortogonal (QT
=Q-1
) y R es una matriz
triangular superior. A partir de ahí se puede resolver fácilmente X, ya
que:
Ax=B-> QRx=B-> Rx= Q-1
B= QT
B.
Como R es triangular la resolución de RX= QT
B se realiza usando las
bibliotecas apropiadas de BLAS. Sin embargo se observa a simple vista
que hay que almacenar dos matrices lo cual consume bastante memoria.
Para el cálculo de Q y R existen fundamentalmente tres métodos:
Mediante el método de ortogonalización de Gram-Schmidt Sensible a los
errores de redondeo ;
Recurriendo al método de ortogonalización de Gram-Schmidt, con las
columnas de A como los vectores a procesar.
. Entonces
Naturalmente, utilizamos los ai de A para obtener:
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
91
Ahora estas ecuaciones pueden ser escritas en forma matricial de esta
manera:
:::::::::
El producto de cada fila con cada columna de las matrices de arriba, da
la columna correspondiente de A con la que se comienza y, por tanto,
dada la matriz A, ha sido factorizada en una matriz ortogonal Q (la
matriz de ek), aplicando el proceso de Gram-Schmidt, y en una matriz
triangular superior R.
Alternativamente, la matriz puede calcularse de la siguiente manera:
Recordemos que: Entonces, tenemos
Nótese que <ej,a
j>=||u
j||, <e
j,a
k>=0 para j>k y QQ
T
= I, por tanto QT
= Q −
1
.
Mediante rotaciones de Givens: fácilmente paralelizable, pero requiere
muchos productos de matrices, accesos de memoria y cálculos
trigonométricos poco precisos.
Las descomposiciones QR también pueden calcularse utilizando una serie
de rotaciones de Givens. Cada rotación anula un elemento en la
subdiagonal de la matriz, formando de este modo la matriz R. La
concatenación de todas las rotaciones de Givens realizadas, forma la
matriz ortogonal Q.
En la práctica, las rotaciones de Givens no se utilizan en la actualidad
para construir una matriz completa y realizar un producto de matrices.
En su lugar, se utiliza un procedimiento de rotación de Givens, que es
equivalente a la multiplicación reducida de matrices de Givens, sin el
trabajo extra de manejar los elementos reducidos. El procedimiento de
rotación de Givens es útil en situaciones donde sólo algunos elementos
fuera de la diagonal necesitan ser anulados y es más fácil de
paralelizar que las transformaciones de Householder.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
92
Mediante el uso de reflexiones de Householder: es el más estable
numéricamente.
Una transformación de Householder o reflexión de Householder es una
transformación que refleja el espacio con respecto a un plano
determinado. Esta propiedad se puede utilizar para realizar la
transformación QR de una matriz si tenemos en cuenta que es posible
elegir la matriz de Householder de manera que un vector seleccionado
quede con una única componente no nula tras ser transformado (es decir,
premultiplicando por la matriz de Householder).
Gráficamente, esto significa que es posible reflejar el vector elegido
respecto de un plano de forma que el reflejado quede sobre uno de los
ejes de la base cartesiana.
La manera de elegir el plano de reflexión y formar la matriz de
Householder asociada es el siguiente:
Sea un vector columna arbitrario m-dimensional tal que ||X||=|α|,
donde α es un escalar; (si el algoritmo se implementa utilizando
aritmética de coma flotante, entonces α debe adoptar el signo contrario
que x1 para evitar pérdida de precisión).
Entonces, siendo el vector (1,0,...,0)T
, y ||·|| la Norma Euclídea,
se define:
v es un vector unitario perpendicular al plano de reflexión elegido. Q
es una matriz de Householder asociada a dicho plano.
Esta propiedad se puede usar para transformar gradualmente los vectores
columna de una matriz A de dimensiones m por n en una matriz triangular
superior. En primer lugar se multiplica A por la matriz de Householder Q1
que obtenemos al elegir como vector la primera columna de la matriz.
Esto proporciona una matriz QA con ceros en la primera columna (excepto
el elemento de la primera fila).
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
93
El procedimiento se puede repetir para A′ (que se obtiene de A
eliminando la primera fila y la primera columna), obteniendo así una
matriz de Householder Q′2. Hay que tener en cuenta que Q′
2 es menor que
Q1. Para conseguir que esta matriz opere con Q
1A en lugar de A′ es
necesario expandirla hacia arriba a la izquierda, completando con un uno
en la diagonal, o en general:
Tras repetir el proceso t veces, donde t = min(m − 1,n),
es una matriz triangular superior. De forma que tomando
A = QR es una descomposición QR de la matriz A.
Este método tiene una estabilidad numérica mayor que la del método de
Gram-Schmidt descrito arriba.
Una pequeña variación de este método se utiliza para obtener matrices
semejantes con forma de Hessenberg, muy útiles en el cálculo de
autovalores por acelerar la convergencia del algoritmo QR reduciendo así
enormemente su coste computacional.
En general, este método es el más usado. Tiene una complejidad del orden
O(n3
), pero es el que ofrece mejores resultados. Sin embargo no aprovecha
las particularidades de las matrices dispersas y en especial su modo de
almacenamiento.
b. CONCLUSIÓN
Desde el punto de vista de la programación, el desarrollo de un Solver
basado sobre alguno de los métodos directos descritos resultaría en la
adaptación a CUDA de algunas de las rutinas de la biblioteca LAPACK como
por ejemplo SGEQRF, SORGQR, SORMQR y STRTRS (en la versión de precisión
simple), incluyendo todas sus dependencias en LAPACK y las dependencias
de éstas con las rutinas BLAS.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
94
Como se ha expuesto anteriormente, CUBLAS, al ser la versión BLAS
adaptada a CUDA, proporciona los bloques necesarios para la construcción
de las rutinas de LAPACK. Sin embargo, hay que recordar que las rutinas
LAPACK están escritas en FORTRAN.
La labor en ese sentido consistiría en identificar hacia atrás todas las
rutinas LAPACK necesarias para el método directo y sus dependencias. Y
a partir de ahí codificar hacia delante a partir de CUBLAS las rutinas
necesarias en C CUDA.
Este trabajo no se consideró apropiado para los fines del proyecto.
Especialmente porque aparte de la enorme y exigente tarea de adaptación,
se obtendría un SOLVER indicado para sistemas Densos y no para Dispersos
como es nuestro caso.
2. MÉTODOS ITERATIVOS
Un método iterativo trata de resolver un problema (como una ecuación o
un sistema de ecuaciones) mediante aproximaciones sucesivas a la
solución, empezando desde una estimación inicial. Esta aproximación
contrasta con los métodos directos, que tratan de resolver el problema
de una sola vez (como resolver un sistema de ecuaciones Ax=b encontrando
la inversa de la matriz A). Los métodos iterativos son útiles para
resolver problemas que involucran un número grande de variables (a veces
del orden de millones), donde los métodos directos tendrían un coste
prohibitivo incluso con la potencia del mejor computador disponible.
Estos métodos se caracterizan por fundamentarse en la existencia de
Puntos fijos atractivos, tal que si una ecuación puede ponerse en la
forma f(x) = x, y una solución x es un punto fijo atractivo de la
función f, entonces se puede empezar con un punto x1 en la base de
atracción de x, y haciendo xn+1=f(x
n) para n ≥ 1, entonces la secuencia
{xn} para n ≥ 1 convergerá a la solución x.
En el caso de un sistema lineal de ecuaciones, las dos clases
principales de métodos iterativos son los métodos iterativos
estacionarios y los más generales métodos del subespacio de Krylov.
Los métodos iterativos estacionarios resuelven un sistema lineal con un
operador que se aproxima al original; y basándose en la medida de error
(el residuo), desde una ecuación de corrección para la que se repite
este proceso. Mientras que estos métodos son sencillos de derivar,
implementar y analizar, la convergencia normalmente sólo está
garantizada para una clase limitada de matrices.
Los métodos del subespacio de Krylov forman una base ortogonal de la
secuencia de potencias de la matriz por el residuo inicial (la secuencia
de Krylov). Las aproximaciones a la solución se forman minimizando el
residuo en el subespacio formado. El método más representativo de esta
clase es el método de gradiente conjugado. Otros métodos son el método
del residuo mínimo generalizado (GMRES) y el método del gradiente bi-
conjugado.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
95
Dado que estos métodos forman una base, el método converge en N
iteraciones, donde N es el tamaño del sistema. Sin embargo, en la
presencia de errores de redondeo esta afirmación no se sostiene; además,
en la práctica N puede ser muy grande, y el proceso iterativo alcanza
una precisión suficiente mucho antes. El análisis de estos métodos es
difícil, dependiendo de lo complicada que sea la función del espectro
del operador.
Para acelerar dicha convergencia se puede recurrir al uso de
precondicionadores. De hecho el operador aproximativo que aparece en los
métodos iterativos estacionarios puede incorporarse también en los
métodos del subespacio de Krylov, donde pasan de ser transformaciones
del operador original a un operador mejor condicionado. La construcción
de precondicionadores es un área de investigación muy extensa.
Un precondicionador P de una matriz A es una matriz tal que P − 1A tiene
un número de condicionamiento bajo. Los precondicionadores son útiles
cuando se utiliza un método iterativo para resolver un sistema lineal
grande de matriz dispersa (sparse) del tipo:
En lugar de resolver el sistema lineal anterior se puede resolver el
sistema precondicionado por la izquierda
A través de la solución de estos dos
o precondicionando el sistema por la derecha
A través de la solución de estos dos
Estos son equivalentes al sistema original siempre que la matriz P sea
no singular.
Básicamente todos los métodos se basan en el mismo principio: se
construye un sistema de vectores xk que convergen hacia x. Se calculan
sucesivamente los términos de la sucesión a partir de una solución de
partida x0, usando una función x
k+1=f(x
k,A,B) y paramos cuando el error
||B-Axk|| es suficientemente pequeño , cuando se llega a un número límite
de iteraciones, o bien cuando el error alcanza un límite y deja de
disminuir.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
96
a. MÉTODOS ITERATIVOS ESTACIONARIOS
Existen varios métodos de los cuales describimos los siguientes, por ser
los más apropiados para el proyecto:
- Método de Gauss- Seidel
En análisis numérico el método de Gauss-Seidel es un método iterativo
utilizado para resolver sistemas de ecuaciones lineales. El método se
llama así en honor a los matemáticos alemanes Carl Friedrich Gauss y
Philipp Ludwig von Seidel y es similar al método de Jacobi.
Es un método iterativo, lo que significa es que para encontrar la
solución a un sistema de ecuaciones lineales, en notación matricial:
, se parte de una aproximación inicial y se repite el proceso
hasta llegar a una solución con un margen de error tan pequeño como se
desee.
De hecho el método de iteración Gauss-Seidel parte de:
donde
para i=j, o para .
Y
Si definimos:
, y .
Considerando el sistema Ax=b, con la condición de que , i= 1, ...,
n. Entonces podemos escribir la fórmula de iteración del método
, para
i=1,...,n(*)
La diferencia entre este método y el de Jacobi es que, en este último,
las mejoras a las aproximaciones no se utilizan hasta completar las
iteraciones.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
97
Convergencia
Teorema: Supongamos que es una matriz no singular que
cumple la condición de
ó .
Entonces el método de Gauss-Seidel converge a una solución del sistema de
ecuaciones Ax=b, y la convergencia es por lo menos tan rápida como la
convergencia del método de Jacobi.
Para ver los casos en que converge el método, primero mostraremos que se
puede escribir de la siguiente forma:
(**)
(El término es la aproximación obtenida después de la k-ésima
iteración) este modo de escribir la iteración es la forma general de un
método iterativo estacionario.
Ante todo debemos demostrar que el problema lineal que queremos resolver
se puede representar en la forma (**), por este motivo debemos tratar de
escribir la matriz A como la suma de una matriz triangular inferior, una
diagonal y una triangular superior A=D(L+I+U), D=diag( ). Haciendo las
operaciones necesarias escribimos el método de esta forma
por lo tanto B=-(L+I)-1
U.
Ahora podemos ver que la relación entre los errores, que se pueden
calcular al restar x=Bx+c de (**) es:
Supongamos ahora que , i= 1, ..., n, son los valores propios que
corresponden a los vectores propios ui, i= 1,..., n, los cuales son
linealmente independientes, entonces podemos escribir el error inicial
(***)
Por lo tanto la iteración converge si y sólo si | λi|<1, para i= 1, ...,
n. De este hecho se desprende el siguiente teorema:
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
98
Teorema: Una condición suficiente y necesaria para que un método
iterativo estacionario converja para una
aproximación arbitraria x(0)
es que
donde ρ(B) es el radio espectral de B.
Explicación
Se elige una aproximación inicial para .y se calculan las matrices M y
el vector C con las fórmulas mencionadas. El proceso se repite hasta que
xk
sea lo suficientemente cercano a xk − 1
, donde k representa el número de
pasos en la iteración.
Algoritmo
El método de Gauss-Seidel se puede escribir en forma de algoritmo de la
siguiente manera:
Algoritmo Método de Gauss-Seidel
función Gauss-Seidel (A, x0
)
//x0
es una aproximación inicial a la solución//
para hasta convergencia hacer
para hasta hacer
para hasta hacer
si entonces
σ = σ + aijxj
fin para
fin para
comprobar si se alcanza convergencia
fin para
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
99
- Método de Jacobi
En análisis numérico el método de Jacobi es un método iterativo, usado
para resolver sistemas de ecuaciones lineales del tipo Ax = b. El
algoritmo toma su nombre del matemático alemán Carl Gustav Jakob Jacobi.
Descripción
La base del método consiste en construir una sucesión convergente
definida iterativamente. El límite de esta sucesión es precisamente la
solución del sistema. A efectos prácticos si el algoritmo se detiene
después de un número finito de pasos se llega a una aproximación al
valor de x de la solución del sistema.
La sucesión se construye descomponiendo la matriz del sistema en la
forma siguiente:
donde
, es una matriz diagonal.
, es una matriz triangular inferior.
, es una matriz triangular superior.
Partiendo de , podemos reescribir dicha ecuación como:
Luego,
Si aii ≠ 0 para cada i. Por la regla iterativa, la definición del Método
de Jacobi puede ser expresado de la forma:
donde k es el contador de iteración, Finalmente tenemos:
Cabe destacar que al calcular xi
(k+1)
se necesitan todos los elementos en
x(k)
, excepto el que tenga el mismo i. Por eso, al contrario que en el
método Gauss-Seidel, no se puede sobreescribir xi
(k)
con xi
(k+1)
, ya que su
valor será necesario para el resto de los cálculos. Esta es la
diferencia más significativa entre los métodos de Jacobi y Gauss-Seidel.
La cantidad mínima de almacenamiento es de dos vectores de dimensión n,
y será necesario realizar una copia explícita.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
100
Convergencia
El método de Jacobi siempre converge si la matriz A es estrictamente
diagonal dominante y puede converger incluso si esta condición no se
satisface. Es necesario, sin embargo, que los elementos de la diagonal
en la matriz sean mayores (en magnitud) que los otros elementos.
Algoritmo
El método de Jacobi se puede escribir en forma de algoritmo de la
siguiente manera:
Algoritmo Método de Jacobi
función Jacobi (A, x0
)
//x0
es una aproximación inicial a la solución//
para hasta convergencia hacer
para hasta hacer
para hasta hacer
si entonces
fin para
fin para
comprobar si se alcanza convergencia
fin para
b. MÉTODOS DEL SUBESPACIO DE KRYLOV
Por su importancia describiremos los más importantes. Partiendo del
método del gradiente conjugado que es el método básico, y concluiremos
con su evolución en el método del gradiente bi-conjugado estabilizado.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
101
Método del gradiente conjugado
El método del gradiente conjugado es un algoritmo para resolver
numéricamente los sistemas de ecuaciones lineales cuyas matrices son
simétricas y definidas positivas. Es un método iterativo, así que se
puede aplicar a los sistemas dispersos que son demasiado grandes para
ser tratados por métodos directos como la descomposición de Cholesky.
Tales sistemas surgen frecuentemente cuando se resuelve numéricamente
las ecuaciones en derivadas parciales.
El método del gradiente conjugado se puede utilizar también para
resolver los problemas de optimización sin restricciones como la
minimización de la energía.
El método del gradiente bi-conjugado proporciona una generalización para
matrices no simétricas. Varios métodos del gradiente conjugado no
lineales buscan los mínimos de las ecuaciones no lineales.
Descripción del método
Supongamos que queremos resolver el siguiente sistema de ecuaciones
lineales:
Ax = b
donde la matriz A, de dimensiones NxN, es simétrica (es decir, AT
= A),
definida positiva (es decir, xT
Ax > 0 para todos los vectores no nulo x
en Rn
), y real.
Denotamos la única solución de este sistema por x*.
Decimos que dos vectores no nulos u y v son conjugados (con respecto a
A) si
Ya que A es simétrica y definida positiva, el lado izquierdo define un
producto interior
Así, dos vectores son conjugados si son ortogonales con respecto a este
producto interior. La conjugación es una relación simétrica: si u es
conjugado a v, entonces v es conjugado a u. (Esta noción de conjugación
no se relaciona con la de conjugación compleja.)
Supongamos que {pk} es una secuencia de n direcciones mutuamente
conjugadas. Entonces los pk forman una base de R
n
, por lo tanto podemos
extender la solución x* de Ax = b en esta base:
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
102
Los coeficientes se obtienen mediante:
Este resultado es quizás más obvio si se considera el producto interior
definido anteriormente.
Esto da el siguiente método para resolver la ecuación Ax=b. Primero
encontramos una secuencia de n direcciones conjugadas y luego calculamos
los coeficientes αk.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
103
Para acelerar la convergencia del método se usa el llamado Método del
Gradiente Conjugado Precondicionado que Tiene la siguiente forma:
Algoritmo Método del Gradiente Conjugado Precondicionado
repetir
if rk+1 es suficientemente pequeño entonces salir del bucle end if
end repetir
El resultado es xk+1
En el algoritmo anterior, M es el precondicionador y debe ser una matriz
simétrica y definida positiva. Sería similar a aplicar el método de
gradiente conjugado al sistema:
Donde y .
Para la versión no precondicionada, basta reemplazar M por la matriz
Identidad e identificar los vectores z y r. De hecho se eliminan los
pasos donde aparece la instrucción z=M-1
r.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
104
Método del gradiente biconjugado:
A diferencia del método del gradiente conjugado no necesita que la
matriz A sea adjunta, sin embargo se deben realizar multiplicaciones
por la matriz conjugada transpuesta.
Algoritmo gradiente biconjugado:
1. Se elige una solución de partida , dos vectores adicionales y y
un precondicionador M.
2.
3.
4.
5.
6. para realizar {
a.
b.
c.
d.
e.
f.
g.
h. }
En el algoritmo los vectores y deben cumplir
y
y por tanto son los residuos correspondientes a y , que son las
soluciones aproximadas del sistema: Ax=b y x*
A=b*
.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
105
Método del gradiente bi-conjugado estabilizado
El método del gradiente bi-conjugado estabilizado, generalmente
abreviado como BiCGSTAB (del inglés «biconjugate gradient stabilized
method»), es un método iterativo propuesto por H. A. van der Vorst para
la resolución numérica de los sistemas de ecuaciones lineales no
simétricos. Es una variante del método del gradiente bi-conjugado (BiCG)
y ofrece convergencia más rápida y suave que el original BiCG así como
otras variantes como el método del gradiente conjugado cuadrado (CGS).
Es un método del subespacio de Krylov.
Algoritmo BiCGSTAB sin precondicionamiento
Para resolver el sistema , el BiCGSTAB comienza con una
aproximación inicial y procede como sigue:
1.
2. Se elige un vector arbitrario tal que , por
ejemplo,
3.
4.
a. Para {
b.
c.
d.
e.
f.
g.
h.
i.
j.
k. Termina si es lo suficientemente preciso
l. }
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
106
También existe la versión de BiCGSTAB precondicionado
Generalmente se utilizan los precondicionadores para acelerar la
convergencia de los métodos iterativos. Para resolver el sistema
con un precondicionador , el BiCGSTAB
precondicionado comienza con una aproximación inicial y procede como
sigue:
1.
2. Elige un vector arbitrario tal que , por ejemplo,
3.
4.
5. Para
a.
b.
c.
d.
e.
f.
g.
h.
i.
j.
k.
l. Termina si es lo suficientemente preciso
m.
PROGRAMACIÓN EN EL ENTORNO CUDA EN APLICACIONES DE MECÁNICA COMPUTACIONAL
CÓDIGO DEL PROYECTO
107
Esta formulación es equivalente a aplicar el BiCGSTAB sin
precondicionamiento al sistema explícitamente precondicionado:
.
con , , . En otras palabras; el
precondicionamiento a ambos lados, tanto a la izquierda como a la
derecha es posible en esta formulación.
3. CONCLUSIÓN:
Atendiendo a los criterios de selección enunciados al principio de éste
apartado y en especial al hecho de que desarrollamos un SOLVER para
matrices dispersas se optó por realizar un desarrollo basado en los
métodos basados en los subespacios de Krylov, en concreto en los métodos
del Gradiente Conjugado (CG) y el Gradiente Bi-Conjugado Estabilizado
ambos no precondicionados. Aunque para las etapas de desarrollo y
pruebas también se probaron alternativas con precondicionador.
Esta opción está indicada en los casos de matrices dispersas aunque su
exactitud es menor que la de los métodos directos.