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 $f(x)=0$ for all $x$ on the boundary of the square, $f(x_{i0,j0})=1$ and $f(x_{i1, j1})$ for specified interior points, and

$$f(x_{i,j})=.1f(x_{i-1,j})+.2f(x_{i+1,j})+.3f(x_{i,j-1})+.4f(x_{i,j+1})$$

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

From what I've read, the conjugate gradient method only works for symmetric $A$, 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]

From what I've read, the conjugate gradient method only works for symmetric $A$, so I was wondering if there is some way to adapt the method, or a different way of setting up the system.

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

$$A^T A y = A^T b$$​

 

[AlephZero]

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

$$A^T A y = A^T b$$​

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

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

 

[libertad]

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