¿Cuál es la diferencia entre el método de gradiente conjugado y el método de gradiente biconjugado?

¿Cuál es la diferencia entre estos dos métodos? ¿Se puede resolver un problema con un método que se pueda resolver con el otro? ¿Pueden ambos / o uno de ellos estar en paralelo con OpenMP y / o MPI?

El método de gradiente conjugado es el solucionador iterativo demostrablemente más rápido, pero solo para sistemas simétricos, definidos positivamente. Lo que sería terriblemente conveniente es si hubiera un método iterativo con propiedades similares para matrices indefinidas o no simétricas.

El método CG busca soluciones aproximadas en cada paso dentro del subespacio Krylov$k$

$K_k(A,b) = \{b, Ab, A^2b,\ldots,A^kb\}$ .

La idea esencial del método de gradiente biconjugado es mantener un segundo subespacio de Krylov

$K_k^*(A,b) = \{b, A^*b, (A^*)^2b,\ldots,(A^*)^kb\}$

y buscando una recurrencia con propiedades de ortogonalidad similares a las de CG, pero sin los problemas de estabilidad de resolver .$A^*Ax = A^*b$

Desafortunadamente, eso falla si lo aplicas ingenuamente. Sin embargo, al realizar un paso del algoritmo residual mínimo generalizado (GMRES) después de cada paso de BiCG, la iteración resultante es estable; esto generalmente se conoce como BiCG-Stab.

Por lo tanto, BiCG-Stab es (en principio) un solucionador más general que el CG, pero sufre una peor eficiencia cuando se aplica a los problemas para los que estaba destinado el CG. BiCG o BiCG-stab requieren más multiplicaciones de vectores de matriz y más productos de puntos, por lo que si los paraleliza a través del multiprocesamiento de memoria distribuida incurrirá en más sobrecarga de comunicación, pero de todos modos se pueden ampliar tanto como desee.

Hay dos cosas que vale la pena señalar aquí que son más importantes que todas esas otras cosas que acabo de decir:

1. Para cada método iterativo (BiCG, GMRES, QMR ...), hay una matriz que hará que no converja en aritmética de precisión finita.

2. Por lo tanto, encontrar un buen preacondicionador para su matriz específica es probablemente más importante que usar el solucionador iterativo óptimo de nivel externo.

EDITAR: Para las bibliotecas de código abierto, las dos más populares son PETSc y Trilinos . Le recomiendo que también obtenga los enlaces de Python, respectivamente petsc4py y PyTrilinos. También puedes probar Eigen . Por un lado, no tiene muchas características, pero por otro lado, tiene justo lo que necesita y nada más; Si tiene la intención de leer el código en lugar de simplemente usarlo, Eigen podría ser el más fácil.

${}$

Ver también: Yousef Saad, Métodos iterativos para sistemas lineales dispersos ; Nachtigal et al, ¿Qué tan rápido son las iteraciones de la matriz no simétrica?

El método de gradiente conjugado solo funciona para resolver el sistema

$A x = b$

$A$

$f(x) = \frac{1}{2} x^T A x - b^T x$

Tenga en cuenta que la derivada es

$f'(x) = \frac{1}{2} A^T x + \frac{1}{2} A x - b$

$A$$A^T = A$

$f'(x) = A x - b$

$f'(x) = 0$$x$$A$

El método de gradiente de biconjugado funcionará para cualquier sistema. Lo hace resolviendo ambos

$A x = b$

junto con

$A^T x = b$

$A$

En cuanto a paralelismo, si sus sistemas son grandes, puede obtener mucho paralelismo en el álgebra lineal involucrado en las iteraciones del solucionador, por lo que no debería haber ninguna razón para que una biblioteca de álgebra lineal paralela no conduzca a ganancias de rendimiento.