Conjugate gradient for nonsymmetric problem

In summary, the conjugate gradient method can be used to solve problems where the condition number of the matrix A is not symmetric, but it may be unstable. There is a practical stabilized version of the method called the BiCGSTAB algorithm, and it doesn't degrade the condition number.
  • #1
ihggin
14
0
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?
 
Technology news on Phys.org
  • #2
ihggin said:
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.

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!)
 
  • #3
Another way the conjugate gradient method could be used is to solve
[tex]A^T A y = A^T b[/tex]​
 
  • #4
Hurkyl said:
Another way the conjugate gradient method could be used is to solve
[tex]A^T A y = A^T b[/tex]​

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.
 
  • #5
Anybody has Conjugate Gradient code snippet in C or C#?
 

Related to Conjugate gradient for nonsymmetric problem

1. What is the conjugate gradient method?

The conjugate gradient method is a popular iterative algorithm used to solve systems of linear equations. It is particularly useful for large, sparse, and nonsymmetric matrices. It uses an efficient approach to find the minimum of a quadratic function by minimizing the residual of the matrix equation.

2. How does the conjugate gradient method work for nonsymmetric problems?

The conjugate gradient method for nonsymmetric problems is a modified version of the classic conjugate gradient method. It uses a new search direction that is a combination of the residual and a preconditioned residual. This allows for efficient convergence even for nonsymmetric matrices.

3. What are the advantages of using the conjugate gradient method for nonsymmetric problems?

The conjugate gradient method has several advantages for solving nonsymmetric problems. These include faster convergence rates, better stability, and lower memory requirements compared to other methods. It also has the flexibility to handle a wide range of problem sizes and types.

4. Are there any limitations to using the conjugate gradient method for nonsymmetric problems?

While the conjugate gradient method is a powerful and efficient algorithm, it does have some limitations. It may not be suitable for very large or highly ill-conditioned matrices. Additionally, it may not converge if the matrix is not positive definite.

5. How can I implement the conjugate gradient method for nonsymmetric problems in my research?

There are many resources available for implementing the conjugate gradient method for nonsymmetric problems. Some popular options include using the built-in functions in programming languages like MATLAB or Python, or using open-source libraries like PETSc or Trilinos. It is important to carefully choose the implementation that best suits your specific problem and research goals.

Similar threads

  • Programming and Computer Science
Replies
5
Views
969
Replies
1
Views
859
  • Programming and Computer Science
Replies
2
Views
2K
  • Programming and Computer Science
Replies
2
Views
1K
  • Advanced Physics Homework Help
Replies
5
Views
928
  • Programming and Computer Science
Replies
1
Views
1K
Replies
36
Views
6K
  • Introductory Physics Homework Help
Replies
3
Views
394
Replies
6
Views
1K
  • Topology and Analysis
Replies
3
Views
1K
Back
Top