Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [conjugate-gradient]

A popular krylov subspace method for solving linear systems of equations, particularly those that exhibit symmetric positive definiteness.

Filter by
Sorted by
Tagged with
3
votes
2answers
5k views

What are some reasons that Conjugate Gradient iteration does not converge?

I would greatly appreciate it if you could share some reasons the Conjugate Gradient iteration for Ax = b does not converge? My matrix A is symmetric positive definite. Thank you so much! Edit with ...
5
votes
1answer
879 views

Solving a system of nonlinear PDEs by minimization

I have two coupled nonlinear partial differential equations of the form: $ \begin{align} \dot{u} -f(u,u',u'',v,v',v'')=0 \\ \dot{v} -g(u,u',u'',v,v',v'')=0 \end{align} $ The boundary conditions are ...
4
votes
1answer
303 views

Linear equation system: Direct solver works, iterative solver does not

I have to solve for x in b = A*x, where a is sparse. This works fine with Matlab's mldivide: x = A \ b. Since I will have to use an iterative algorithm for very large A, I'm currently testing Matlab's ...
8
votes
2answers
3k views

What's the difference between conjugate gradient method and biconjugate gradient method

What's the difference between these two methods? Can a problem be solved by one method will be able to solved by the other? Can both/or one of them be parallelized with OpenMP and/or MPI?
5
votes
0answers
180 views

Conjugate residual/gradient convergence checking in practice

Let's say we want to solve $Ax=b$ ($A$ symmetric positive /semi/definite) with the conjugate residual/gradient method. $A$ comes from FEM where the mesh is being refined. The exact solution is $x_*$ ...
25
votes
3answers
19k views

BFGS vs. Conjugate Gradient Method

What considerations should I be making when choosing between BFGS and conjugate gradient for optimization? The function I am trying to fit with these variables are exponential functions; however, the ...
0
votes
2answers
6k views

How to solve this system with conjugate gradient algorithm in matlab

CG Algorithm https://skydrive.live.com/redir?resid=E0ED7271C68BE47C!386&v=3 System of equations, the question and the example https://skydrive.live.com/redir?resid=E0ED7271C68BE47C!387&v=3 <...
2
votes
0answers
74 views

Which non-linear conjugate gradient possess finite termination property

There are many variants of non-linear conjugate gradient method available ( Flatcher-Reeves, Polak-Rebiere, Dai-Yuan). In case of minimization of quadratic function when first search direction is ...
2
votes
1answer
445 views

PETSc Krylov Subspace and nullspace

How is the nullspace correction implemented in the PETSc conjugate gradient solver? I searched the source code and documentation, but could not find references on the actual implementation. For ...
8
votes
2answers
3k views

Genetic algorithm vs conjugate gradient method

I am trying to optimize some force-field parameters in a molecular framework so that the result of simulation comes as close as it can to the experimental structure. In the past, I have written a ...
17
votes
3answers
3k views

Problems where Conjugate gradient works much better than GMRES

I am interested in cases where Conjugate gradient works much better than GMRES method. In general, CG is preferable choice in many cases of SPD (symmetric-positive-definite) because it requires less ...
4
votes
1answer
172 views

Is there a nonlinear solver similar to CGNR evaluating only $A^TAx$?

First of all, I am quite new to this field and I excuse myself in advance for any stupid content in this question. In the field of compressed sensing or deblurring I have a nonlinear optimization ...
1
vote
2answers
314 views

Checking for error in conjugate gradient algorithm

What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction ...
9
votes
2answers
4k views

How to remove Rigid Body Motions in Linear Elasticity?

I want to solve $K u = b$ where $K$ is my stiffness matrix. However some constraints may be missing an therefore some rigid body motion may be still present in the system (due to eigenvalue zero). ...
3
votes
2answers
106 views

How can you explain the following bound on the inner product?

I am reading a paper on stability of CG, and I came across the following statement: \begin{equation} \frac{\|A\|\,\|p\|^2}{\langle p,Ap\rangle} \leq \kappa(A) \end{equation} where $\kappa(\cdot)$ is ...
23
votes
3answers
3k views

What is the principle behind the convergence of Krylov subspace methods for solving linear systems of equations?

As I understand it, there are two major categories of iterative methods for solving linear systems of equations: Stationary Methods (Jacobi, Gauss-Seidel, SOR, Multigrid) Krylov Subspace methods (...
2
votes
2answers
1k views

Usage of DifferentiableMultivariateFunction and NonLinearConjugateGradientOptimizer

I try to use the matlab fminunc functionality in java and found the optimisation functions in commons-math. I have absolutely no clue how to use them right because the example tells nothing about the ...
1
vote
1answer
679 views

Gradient descent to stationary, or accumulation point

I recently came across the notion of an accumulation point as a result of a certain gradient descent variation. The following definition was found: An accumulation point $P$ is such that there are an ...
4
votes
2answers
193 views

Looking for a mathematical proof of stability in floating point arithmetic of CG - any reference?

I am looking for a reference - paper, book, discussion, anything that has a mathematical proof for stability of the conjugate gradient method in floating point arithmetic. Something similar for ...
3
votes
1answer
856 views

Is a checkerboard block decomposition of a matrix useful when solving a linear system with a parallel conjugate gradient method?

According to these lecture notes, a checkerboard block decomposition should exhibit better scalability when applied to parallel matrix-vector multiplication (presumably because of greater cache hit ...
5
votes
2answers
1k views

Sufficient conditions to ensure convergence of the conjugate gradient method

I know that a conjugate gradient method is guaranteed to converge to the solution of a linear system if the matrix is positive definite. I'm working with a family of matrices that have the following ...
4
votes
2answers
328 views

best way to optimize a function with linear/non-linear parameters

I am trying to fit some raw data using a function of the form $f(r) = \sum_{i=1}^{K} d_kS_k(n_k,\alpha_k,r)$ where $S_k(n_k,\alpha_k,r) = \frac{\alpha_k ^{n_k+3}}{(n_k+2)!}r^{n_k}\exp(-\alpha_kr)$ ...