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

learn more… | top users | synonyms

3
votes
2answers
58 views

2D Laplace problem with mixed boundary conditions using Conjugate Gradients

I am being asked for one of my classes to solve 2D Laplace equations with mixed boundary conditions using the Conjugate Gradient method. The equations and conditions are given as: $$ \frac{\partial^...
1
vote
1answer
61 views

The linear system in Quasi Newton method

I have implemented a Quasi Newton method for my problem, where I use the Hessian matrix approximation based approach. Hence, there is a linear system solve in every iteration. I solve the linear ...
5
votes
1answer
174 views

Solving a set of linear equations with block structure and weak coupling

I have a standard set of linear equations $Ax=b$ where the Hessian matrix $A$ has the special block structure as shown: $A= \begin{pmatrix} T & U\\ U^T & V \end{pmatrix}$, $x= \begin{...
1
vote
1answer
38 views

Conjugate Gradient, initial direction set to initial residual

In the (iterative) Conjugate Gradient (CG) algorithm: https://en.wikipedia.org/wiki/Conjugate_gradient_method The initial search direction $p_{0}$ is set to the initial residual $r_{0}$. But I can't ...
5
votes
0answers
48 views

Nonlinear conjugate gradient restart threshold 1/10

Nocedal and Wright on Conjugate Gradient Methods, p. 123, describe a restart strategy ... whenever two consecutive gradients are far from orthogonal $\qquad {{| \nabla f_k^T \ \nabla f_{k-1} |} \...
1
vote
1answer
93 views

Can this equation be solved with the conjugate gradient method?

Let $A$ be positive-definite and $C$ diagonal positive-definite, consider the problem of solving the following equation for $\bf x$ $$A{\bf x}+C\begin{bmatrix} e^{x_1} \\ \vdots \\ e^{x_n} \end{...
6
votes
2answers
192 views

What is the worst case complexity of Conjugate Gradient?

Let $A\in \mathbb{R}^{n\times n}$, symmetric and positive definite. Suppose it takes $m$ units of work to multiply a vector by $A$. It is well known that performing the CG algorithm on $A$ with ...
6
votes
0answers
74 views

Why does conjugate gradient work with this nonsymmetric preconditioner?

In this previous thread the following multiplicative way to combine symmetric preconditioners $P_1$ and $P_2$ for the symmetric system $Ax=b$ was suggested: \begin{align} P_\text{combo}^{-1} :=& ...
4
votes
0answers
71 views

Conjugate gradient: the 1-norm of the residual

I am trying to solve $Ax=b$ using the conjugate gradient method. However, it is important to me to obtain a bound not only on the usual residual $||b-Ax_k||_2$ but also on the quantity $||b-Ax_k||_1$. ...
2
votes
1answer
84 views

Solve FEM matrix from coupled system

I'm developing an FEM solver for a coupled system. I have diffusion and potential equations which result in positive definite matrices for each equation, but the coupling makes the overall system ...
3
votes
0answers
60 views

How to implement conjugate gradient method to minimize this nonlinear action?

Given a 2D stochastic differential equation: \begin{align} \dot{x}_{i}=f_{i}(\textbf{x})+g_{ij}\xi_{j}(t), \end{align} where $i=2$, $g_{ij}g_{jk}=2\epsilon\delta_{ik}$ and $f(\textbf{x})=-\nabla\phi(\...
3
votes
1answer
123 views

Trust-region Newton: implementation issue with Conjugate Gradient calculations

UPDATE: The problem turned out to be the step (refer penultimate paragraph below) where I was factoring out a small value from the vectors of the numerator and denominator and then computed dot ...
2
votes
1answer
152 views

Hessian-free and Truncated Newton methods

In this paper on Deep Learning for Machine Learning, the approach is referred to as Hessian-free method. That is because the Hessian is never computed explicitly. Instead, the product of the Hessian ...
5
votes
1answer
172 views

Caveats of Hessian free method

Hessian free iterative optimization techniques like Newton-CG, do not explicitly compute the Hessian but instead approximate the product of the Hessian with a vector through finite difference. The ...
1
vote
0answers
107 views

Search Direction in Conjugate Gradient

Could you help me with a Conjugate Gradient question? In using CG to solve Ax=b, why is the search direction $p_{k+1}$ in CG chosen as a linear combination of the residual $r_k$ and previous direction ...
3
votes
0answers
172 views

Is it possible to predict the null space of a structure from contributing elements null spaces?

I am trying to solve an almost incompressible problem with heterogeneous properties by domain decomposition. Solution with CG converges slowly or divergerces completely. My problem becomes ill-...
3
votes
2answers
531 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 ...
4
votes
1answer
393 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
229 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 ...
1
vote
2answers
156 views

SLATEC rouitne dslucs() and MKL correspondence

I am looking for a routine (or set of routines) in the Intel MKL that that can replace dslucs (Incomplete LU BiConjugate Gradient Squared Ax=b Solver) in ...
7
votes
2answers
1k 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?
4
votes
0answers
149 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_*$ ...
4
votes
2answers
119 views

Would recalculating the residual in the conjugate gradient method help?

The conjugate gradient method suffers from an accumulation of errors as it continues. For this reason it is unwise to use it as a direct solver. My question is, would it help to recalculate the ...
1
vote
2answers
3k 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
68 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 ...
1
vote
1answer
312 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 ...
5
votes
2answers
608 views

Gradient descent and conjugate gradient descent

For a project I have to implement these two methods and compare how they perform on different functions. But when I read about it I see that for example the conjugate gradient method is meant to solve ...
8
votes
2answers
1k 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 ...
13
votes
3answers
2k 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
523 views

nonlinear conjugate gradient for multivariable functions

For the optimization problem $\underset{\mathbf{x}\in \mathbb{R}^n}{\operatorname{argmin}} f(\mathbf{x})$, we can use the following standard nonlinear conjugate gradient method to find the solution: ...
11
votes
4answers
528 views

Calculating determinant while solving $Ax=b$ using CG

I am solving $Ax=b$ for a huge sparse positive definite matrix $A$ using the conjugate gradient (CG) method. It is possible to compute the determinant of $A$ using the information produced during the ...
4
votes
1answer
143 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
236 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 ...
7
votes
2answers
2k 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). ...
5
votes
0answers
298 views

Estimate extreme eigenvalues with CG

CG may be used to estimate the extremal eigenvalues of a SPD matrix (by computing eigenvalues of tridiagonal matrix associated with the Lanczos algorithm). After a few iterations the largest ...
3
votes
2answers
96 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 ...
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
337 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 ...
3
votes
1answer
541 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
688 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 ...
18
votes
3answers
1k 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 ...
3
votes
2answers
178 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 ...
20
votes
3answers
9k 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 ...
4
votes
2answers
298 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)$ ...