Qual é a diferença entre o método do gradiente conjugado e o método do gradiente biconjugado

Qual a diferença entre esses dois métodos? Um problema pode ser resolvido por um método capaz de ser resolvido pelo outro? Ambos / ou um deles podem ser paralelos ao OpenMP e / ou MPI?

O método do gradiente conjugado é o solucionador iterativo comprovadamente mais rápido, mas apenas para sistemas simétricos e com definição positiva. O que seria terrivelmente conveniente é se houvesse um método iterativo com propriedades semelhantes para matrizes indefinidas ou não simétricas.

O método CG busca soluções aproximadas em cada etapa dentro do subespaço Krylov$k$

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

A idéia essencial do método do gradiente biconjugado é manter um segundo subespaço de Krylov

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

e buscando uma recorrência com propriedades de ortogonalidade semelhantes às do GC, mas sem os problemas de estabilidade da solução de .$A^*Ax = A^*b$

Infelizmente, isso falha se você aplicá-lo ingenuamente. No entanto, executando uma etapa do algoritmo residual mínimo generalizado (GMRES) após cada etapa do BiCG, a iteração resultante é estável; isso geralmente é chamado de BiCG-Stab.

Portanto, o BiCG-Stab é (em princípio) um solucionador mais geral que o GC, mas sofre pior eficiência quando aplicado aos problemas para os quais o CG foi destinado. O BiCG ou o BiCG-stab exigem mais multiplicações de vetores matriciais e mais produtos de ponto; portanto, se você os paralelizar por meio do multiprocessamento de memória distribuída, haverá mais sobrecarga de comunicação, mas, mesmo assim, eles podem ser ampliados conforme você desejar.

Há duas coisas dignas de nota aqui que são mais importantes do que todas as outras porcarias que acabei de dizer:

1. Para todo método iterativo (BiCG, GMRES, QMR ...), existe uma matriz que fará com que ele não converja na aritmética de precisão finita.

2. Portanto, criar um bom pré-condicionador para sua matriz específica é provavelmente mais importante do que usar o solucionador iterativo ideal de nível externo.

EDIT: Para bibliotecas de código aberto, os dois mais populares são o PETSc e o Trilinos . Eu recomendo que você também obtenha as ligações do Python, respectivamente petsc4py e PyTrilinos. Você também pode tentar Eigen . Por um lado, ele não possui muitos recursos, mas, por outro lado, possui exatamente o que você precisa e não precisa mais; se você pretende ler o código em vez de apenas usá-lo, o Eigen pode ser o mais fácil.

${}$

Veja também: Yousef Saad, métodos iterativos para sistemas lineares esparsos ; Nachtigal et al, Quão rápido são as iterações da matriz não simétrica?

O método do gradiente conjugado funciona apenas para resolver o sistema

$A x = b$

$A$

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

Observe que a derivada é

$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$

O método gradiente biconjugado funcionará para qualquer sistema. Fá-lo resolvendo ambos

$A x = b$

junto com

$A^T x = b$

$A$

Quanto ao paralelismo, se os sistemas são grandes, você pode obter muito paralelismo na álgebra linear envolvida nas iterações do solucionador, portanto não deve haver razão para que uma biblioteca de álgebra linear paralela não leve a ganhos de desempenho.