Conjugate gradient for nonsymmetric problem

ihggin

Hi, I was wondering if it is possible to adapt the conjugate gradient method (or if there's a variation of the method) for nonsymmetrical boundary value problems.

For example, I want to solve something like a 2D square grid, where [itex]f(x)=0[/itex] for all [itex]x[/itex] on the boundary of the square, [itex]f(x_{i0,j0})=1[/itex] and [itex]f(x_{i1, j1})[/itex] for specified interior points, and

[tex]f(x_{i,j})=.1f(x_{i-1,j})+.2f(x_{i+1,j})+.3f(x_{i,j-1})+.4f(x_{i,j+1})[/tex]

for all other interior grid points [itex]x_{i,j}[/itex]. If I change [itex]f_{i,j}[/itex] to a 1D vector [itex]y_{k}[/itex], and then write the system of eqs out, the matrix [itex]A[/itex] in the system I want to solve ([itex]Ay=b[/itex]) is not symmetric.

From what I've read, the conjugate gradient method only works for symmetric [itex]A[/itex], so I was wondering if there is some way to adapt the method, or a different way of setting up the system. If not, what would be the fastest way to solve this problem? (The only reason I'm interested in conjugate gradient is b/c I heard it's fast.) I'm currently using successive over-relaxation (SOR). Is there anything faster?

AlephZero

Google for "biconjugate gradient algorithm".

There are some traps here, because biconjugate gradient can be unstable. A practical stabilized version is the BiCGSTAB algorithm (also in Google!)

Hurkyl

Another way the conjugate gradient method could be used is to solve

[tex]A^T A y = A^T b[/tex]

AlephZero

True, provided it doesn't matter that the condition number of [itex]A^T A[/itex] is the square of the condition number of [itex]A[/itex], which may decrease the numerical precision.

The biconjugate gradient method also involves multiplyng vectors by [itex]A^T[/itex], but it doesn't degrade the condition number.

libertad

Anybody has Conjugate Gradient code snippet in C or C#?