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

9

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?

user2196452
fonte

Respostas:

11

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 Krylovk

.Kk(UMA,b)={b,UMAb,UMA2b,,UMAkb}

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

Kk(UMA,b)={b,UMAb,(UMA)2b,,(UMA)kb}

e buscando uma recorrência com propriedades de ortogonalidade semelhantes às do GC, mas sem os problemas de estabilidade da solução de .UMAUMAx=UMAb

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?

Daniel Shapero
fonte
Você conhece alguma biblioteca paralela de código aberto para BiCG?
precisa saber é o seguinte
Fora de interesse puramente teórico: se você aplicar BiCG (ou BiCGStab) a uma matriz positiva simétrica, esse método é formalmente equivalente a algo conhecido?
shuhalo
5

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

UMAx=b

UMA

f(x)=12xTUMAx-bTx

Observe que a derivada é

f(x)=12UMATx+12UMAx-b

UMAUMAT=UMA

f(x)=UMAx-b

f(x)=0 0xUMA

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

UMAx=b

junto com

UMATx=b

UMA

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.

Godric Seer
fonte