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
1answer
38 views

Conjugate Gradient for singular 2D poisson finite element with Neumann Boundary Conditions

Heavily edited question after I realised partly what the problem was I have programmed a simple 2D square finite element solution to the Poisson equation $-\Delta u = f$ The source function ...
6
votes
0answers
60 views

Why not use the preconditioned residual as termination criterion for preconditioned CG?

I have a Poisson equation with wildly varying material parameters (1 .. 1000), wildly varying element sizes (5 nm .. 100 um) and some quite anisotropic (tetrahedral) elements (100 nm x 100 um). I use (...
2
votes
1answer
49 views

Blowup of error in Conjugate Gradient method with periodic Dirichlet Poisson matrix

My problem is that the L2-Norm of the residual for the periodic Poisson matrix $P$ is initially decreasing but starts to blow up after a certain number of iterations. The blowup happens earlier the ...
2
votes
1answer
69 views

Nonlinear conjugate gradient with orthogonality constraint

I have to solve a set of nonlinear optimization problems in the subspace defined as the orthogonal space to a given vector. More precisely, $$ \arg\min f(\vec x) \qquad \text{with} \qquad \vec x \...
2
votes
0answers
74 views

Richardson's Iteration, Gradient Method and Spectral Radius

Richardson's iteration introduce a scalar $\alpha$ to the update formula: $$ \textbf{x}^{(k+1)} = \textbf{x}^{(k)} + \alpha \textbf{r}^{(k)} $$ And compute $\alpha$ by minimizing the spectral radius:...
1
vote
1answer
86 views

Conjugate gradient - ill-conditioning and numerical tolerance

I would like to solve system $Ax=b$, where $A$ is SPD, but very ill-conditioned ($\text{cond}(A)>10^{11}$). I am interested in using UNpreconditioned version of the conjugate gradient method. Is ...
1
vote
1answer
103 views

Relation between conjugate gradient method and finite elements method

What is difference beetwen this two method? Are these methods far from each other or are these methods complement each other? Could you take an example?
3
votes
1answer
842 views

Which C++ linear algebra library is probably the fastest on solving huge sparse [square matrix] linear system?

I am developing a 2D CFD solver for fluid-particle interaction. To solve Navier-Stokes equations on a grid of size $10000\times 10000$ cells (or >1 million cells), a large linear system $Ax=b$ with $A$...
8
votes
0answers
138 views

How to find a good preconditioner to the system $(A^T A + \lambda I) x = A^T b$?

The system in the title has a damper factor $\lambda > 0$ and the matrix $A$ is sparse and rectangular, with a structure I can exploit to solve matrix vector products very fast. My current solver, ...
4
votes
0answers
34 views

Stochastic conjugate directions to improve convergence in narrow valleys

My question concerns a specific statement in this paper: N. N. Schraudolph and T. Graepel, "Conjugate Directions for Stochastic Gradient Descent," in Int. Conf. Artificial Neural Networks, Berlin, ...
3
votes
1answer
120 views

How can a CG solver solve a non positive definite sparse matrix

I am using the CUSP CG solver and I ran it on couple of sparse matrices from the University of Florida sparse matrix collection. The solver was able to solve non positive definite sparse matrices. My ...
6
votes
1answer
238 views

What is required of the objective function in order to use Gauss Newton method?

From what I understand, the Gauss-Newton method is used to find a search direction, then the step size, etc., can be determined by some other method. In addition to that, are the following ...
3
votes
1answer
302 views

Linear constraints for L-BFGS-B

I know L-BFGS-B only supports simple box constrains of the form: $l_i \leq x_i \leq u_i$, where $l_i$ and $u_i$ are constants. For my specific optimization problem, I need to specify some simple ...
0
votes
1answer
63 views

Adaptive gradient descent

I want to minimize some multivariable function $\Delta(\alpha, \beta)$. I know that this function has a zero point, $\Delta(5, 5) = 0$. Starting from some $(\alpha, \beta)$ close to $(5,5)$ (e.g. (4....
0
votes
1answer
143 views

How to verify solution to pre-conditioned linear systems solver?

I am solving Ax=b. A has a very large condition number (> O(10^10)) I am using the conjugate gradients method with point jacobi pre-conditioning. I obtained a solution 'x' that "looks" reasonable. ...
7
votes
1answer
3k views

What are the differences between the different gradient-based numerical optimization methods?

I am interested in the specific differences of the following methods: The conjugate gradient method (CGM) is an algorithm for the numerical solution of particular systems of linear equations. The ...
1
vote
1answer
159 views

Computing preconditioner for a non-linear conjugate gradient implementation

Consider the following steps for the $i$-th non-linear conjugate gradient iteration, in the context of 3D electromagnetic inversion, and as discussed in (Newman and Boggs, 2004): (1) set $i = 1$, ...
1
vote
0answers
149 views

Search direction for CG method

I am studying optimization methods and I was able to understand and derive the search direction $$ p_k = r_{k-1} + \beta p_{k-1} $$ for Conjugate Gradient Method, with $$ \beta = -\frac{p_{k-1}^...
4
votes
2answers
923 views

Conjugate gradient method to minimize a function

I am having some serious difficulties trying to understand how to use (apply) CG to minimize a function. In all the textbooks and notes, the step size $\alpha$ is give by the following expression $$ \...
2
votes
0answers
95 views

Optimization based integration for MPM

I'm considering implementing (just for simplicity) the unconstrained implicit optimization based integration for Material Point Method as described in Chenfanfu Jiang's thesis on MPM (the minimization ...
3
votes
0answers
1k views

Understanding MATLAB's `fmincg` optimization function

I'm researching numerical optimization. Recently I've come across a variant of a conjugate gradient method named fmincg. The function is written in MATLAB and is ...
1
vote
1answer
1k views

Solving the Poisson equation with Neumann Boundary Conditions - Finite Difference, BiCGSTAB

I am trying to solve the Poisson equation in a rectangular domain using a finite difference scheme with a rectangular mesh. I have happily generated the matrix system of equations Ax = b which is ...
3
votes
1answer
136 views

CG question: is symmetry always necessary?

Consider the 1D Poisson equation $$\nabla^2 u = f.$$ Using finite difference method on cell corner data and a uniform grid with ghost points, I think we can write the system of equations with Neumann ...
1
vote
2answers
695 views

Boundary conditions in conjugate gradient method for poisson's equation

I want to use the conjugate gradient method to solve poisson's equation in an electrostatic setup: \begin{align} \rho=-\nabla^2\phi \end{align} I am however a little confused when it comes to the ...
9
votes
1answer
1k views

Adaptive gradient descent step size when you can't do a line search

I have an objective function $E$ dependent on a value $\phi(x, t = 1.0)$, where $\phi(x, t)$ is the solution to a PDE. I am optimizing $E$ by gradient descent on the initial condition of the PDE: $\...
3
votes
2answers
292 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
97 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
308 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
68 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 ...
4
votes
0answers
199 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
109 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{...
9
votes
2answers
1k 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 ...
8
votes
2answers
267 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} :=& ...
3
votes
0answers
107 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
128 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
89 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
204 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
433 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 ...
6
votes
1answer
334 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
152 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 ...
4
votes
0answers
238 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
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
861 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
300 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
239 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 ...
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_*$ ...
5
votes
2answers
164 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
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 ...