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
2 votes
0 answers
54 views

Equivalency of lasso problems

In the literature, I've seen the lasso problem phrased as the minimization of: $$\frac12x^tAx-x^tb+\lambda||x||_1$$ or of: $$\frac12||Ax-b||_2^2+\lambda'||x||_1=\frac12x^tA^tAx-x^tA^tb+b^tb+\lambda'||...
GS101's user avatar
  • 21
1 vote
1 answer
85 views

Inner iterations in the preconditioned conjugate gradient method

As shown in Algorithm 2 of this document a linear system $M{\bf z}_k = {\bf r}_k$ is required for every iteration of the preconditioned conjugate gradient (PCG) method. I assume this system is ...
Olumide's user avatar
  • 265
5 votes
0 answers
122 views

Single precision vs double precision conjugate gradients

I tested my conjugate gradients implementation with float and double precision and contrary to my guess the double code was twice faster than the single precision code. The reason is that I need many ...
lightxbulb's user avatar
  • 1,994
12 votes
2 answers
2k views

Why are systems with clustered eigenvalues easy to solve?

I came across the following slide by Theo Diamandis & Zachary Frangella on what makes the linear system $Ax=b$ easy to solve using the conjugate gradient method. Transcription: CG converges ...
Yaroslav Bulatov's user avatar
1 vote
1 answer
266 views

Why does scipy Conjugate Gradient solver fail to converge for non-steady heat equation using Crank-Nicolson method

Could someone please explain why my implementation of the Crank-Nicolson method applied to the non-steady heat equation won't converge? There shouldn't be any nonlinear aspects to my implementation ...
n1ck94's user avatar
  • 13
2 votes
1 answer
79 views

Preconditioned congugate gradaient vs Untransfomed preconditioned conjugate gradient

Page 460 of Numerical Optimization by Nocedal and Wright contains the following algorithm under the name projected conjugate gradient However, Jonathan Richard Shewchuk list what seems to me to be ...
Olumide's user avatar
  • 265
6 votes
1 answer
297 views

Creating a preconditioner for conjugate gradient with a known approximate solution

I am working on solving Poisson's eq. $\Delta u = -f$ using conjugate gradient method. I am using scipy's linalg.cg function. In this problem, the source function $f$ changes slightly in each ...
Omer Paz's user avatar
3 votes
1 answer
90 views

A question related with $p$-Laplacian and conjugate gradient method

I have the following energy functional of $p$-Laplacian equation: $$ E(u) = \frac{1}{p} \int_{\Omega} |\nabla u|^p dx $$ for $2.8 \leq p \leq 5$. My goal is to minimize the energy functional by using ...
User124356's user avatar
3 votes
0 answers
58 views

Adjoint method for imaging with an "analytical" forward model

I am working on tomographic image reconstruction (radar regime) of the dielectric properties of objects. As part of my work, I have programmed a ray tracer. This ray tracer is, in a way, purely "...
DominikR's user avatar
1 vote
0 answers
78 views

Implementations of the Eisenstat-trick for SSOR

Where can I find a source code for the SSOR method with Eisenstat's trick? The original paper includes pseudo code but also seems to have minor typos. For that reason, I would be very happy to see an ...
shuhalo's user avatar
  • 3,620
1 vote
1 answer
73 views

Reason for why apparent acceleration of algebraic multigrid solve by addition of positive definite diagonal matrix

In passing I was told by someone that $K^{\prime}\in\mathbb{R}^{n\times n}$, will be easier to solve by an algebraic multigrid preconditioned conjugate gradient (CG-AMG) solver than $K$, where $K$ is ...
Tucker's user avatar
  • 189
3 votes
1 answer
241 views

BiCGSTAB convergence

So I need a fast converging solver for SysLinEq as a subroutine in fortran, decided to test BiCGStab in Matlab. Thank God I decided to test it out on first before implementing in Fortran as a ...
2Napasa's user avatar
  • 362
3 votes
0 answers
37 views

Reference for preconditioning nonlinear conjugate gradient with LU decomposition of jacobian

When solving non-linear systems of equations, @Arnold Neumaier suggested in How can I precondition a non-linear problem before linearization? to use an approximate LU decomposition of an approximate ...
NaHenn's user avatar
  • 31
1 vote
0 answers
85 views

Poisson equation fast solver on large grids

Below is kind of a broad question. Was given Poisson equation with BC, on meshgrid of NxM. Rewrote as system of N*M linear equations, Converted to sparse format (CSR/CRS/Yale), solved using Conj Grad ...
2Napasa's user avatar
  • 362
2 votes
1 answer
78 views

ICCG negative residual products $r^TM^{-1}r$

I have a linear system $Ax=b$ resulting from a finite element discretization of the Poisson equation. I am applying an IC0 (incomplete Cholesky ($LDL^T$) with the same sparsity as the original matrix) ...
lightxbulb's user avatar
  • 1,994
0 votes
2 answers
317 views

Why minimizing with respect to A-norm?

Assume solving the linear system $A \textbf x = \textbf b$, with an $A$ so large that nothing but iterative methods may be employed. Assuming $A$ induces a norm, I realized that it is often desired to ...
arash's user avatar
  • 21
0 votes
3 answers
732 views

How to apply the boundary condition when global stiffness matrix is stored in csr format? [duplicate]

I am solving the poisson equation and I constructed the global stiffness matrix in compressed row storage format. Then I wrote the preconditioned conjugate gradient solver for solving the system of ...
Resa's user avatar
  • 29
2 votes
1 answer
60 views

When will the Orthomin/CG iteration fails

I know that the the Conjugate Gradient iteration fails when $0\in \mathcal {W}(A^{H})$, which means there's a complex vector $x+iy$ such that $(x+iy)^{T}A^{H}(x+iy)=0$. I wonder how to derive a real ...
Analyst_311419's user avatar
1 vote
0 answers
99 views

Convergence of Conjugate Gradient Algorithm

I am trying to solve a linear elasticity model using finite element discretization in a rectangle domain [0,1]x[0,1]. For the solution of the the linear system $Ku=F$ I am using the CG algorithm. ...
spyros's user avatar
  • 481
1 vote
1 answer
150 views

CG without division by 0 in a solution

In the standard formulation of Krylov subspace methods, you always have to divide by 0 somewhere in a solution, e.g., in CG, $$ x_{k+1} = x_k + \frac{r_k^T r_k}{p_k^T A p_k} p_k\\ p_{k+1} = r_{k+1} + \...
Nico Schlömer's user avatar
1 vote
0 answers
87 views

2-norm of solution update suddenly becomes zero after a few iterations

I am trying to solve the Poisson equation in 2D for heterostructure devices. I have linearized the equation and discretized it using FDM. I am using BiCGStab to iteratively solve for the solution as ...
prananna's user avatar
4 votes
1 answer
182 views

Why does smoothed aggregation multigrid method used as preconditioner in conjugate gradient slows down the solution time?

I'm solving a system of linear equations obtained from the FEM discretization of a simple linear elasticity problem on a cube with zero displacements at one plane and a load on the opposite one. The ...
Alexander's user avatar
8 votes
2 answers
2k views

What happens when I use a conjugate gradient solver with a symmetric positive semi-definite matrix?

I have a symmetric positive semi-definite matrix, i.e., a laplacian and wonder what may happen when I use a CG solver, that is an algorithm for positive definite matrices. What happens when the ...
allo's user avatar
  • 607
3 votes
0 answers
88 views

Conjugate Gradient for nonlinear equation system

Is it possible to apply adaptions of the conjugate gradient algorithm i.e. Fletcher-Reeves, Polak-Ribere or others to systems of nonlinear equations? How should the equation system be adjusted so one ...
RockedSalad121's user avatar
0 votes
0 answers
187 views

Arnoldi Decomposition Algorithm

I try to get into GMRES via Arnoldi-Decomposition. For my understanding, I Implemented the Arnoldi-Decomposition in python. ...
dba's user avatar
  • 295
1 vote
1 answer
125 views

In which cases does the nonlinear conjugate gradient method take more than $n$ steps?

I have programmed a couple of Matlab implementations of nonlinear Conjugate Gradient methods (Fletcher Reeves and Polak Ribeire). However, I am concerned with how many steps it's taking to optimise ...
foobar's user avatar
  • 51
5 votes
0 answers
144 views

Explanation of subspace strategy regarding CG described in Golub's book

I was wondering about the last paragraph in Matrix Computations (4th edition) by Golub, Chapter 11 (11.3.3), specifically his explanation of subspace strategy for Conjugate Gradient. Note that in ...
ec2604's user avatar
  • 161
2 votes
1 answer
529 views

What's wrong with the **PCG and MINRES** in matlab?

Last week, I have learned the details of the robust iterative methods of PCG, MINRES, GMRES, which will converges to the exact solution $x^*$ of nonsingular system within $N$ steps for $A\in \mathbb{R}...
Happy's user avatar
  • 961
3 votes
0 answers
47 views

Subspaces for Iterative methods

In the original paper of Conjugate Gradients, the authors mention that if we pick the canonical basis $\{e_1,e_2,\ldots,e_n\}$, to obtain A-orthonormal vectors, we end up with the Gaussian elimination ...
Adhvaitha's user avatar
  • 171
1 vote
2 answers
60 views

What's the difference between the 2 ways of definitions of function handle? which is robust and better?

Recently, I have been studying Krylov subspace iterative methods. I find the matlab robust command pcg and the new concept of the function handle to return a matrix-vector product. Then I use help pcg ...
Happy's user avatar
  • 961
1 vote
1 answer
65 views

Accelerating Conjugate Gradients fitting for small localized kernel (like cubic B-spline)

Question: Is there some pre-conditioner for Conjugate-Gradient (CG) cheap enough, that it is worth using even if my operator is very local (i.e. already has a low number of non-zero elements), as it ...
Prokop Hapala's user avatar
1 vote
1 answer
55 views

Why the iteration steps become twice if the step size reduces half for CG methods?

For CG method for SPD matrices, (Ax = b arising from Poisson equation with homogeneous boundary condition) we know that the convergence theorem: After m steps of iteration, the error $e^{(m)}=x-x_m$ ...
Happy's user avatar
  • 961
3 votes
1 answer
372 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 ...
Not a chance's user avatar
8 votes
0 answers
209 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 (...
Thomas Klimpel's user avatar
2 votes
1 answer
362 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 ...
CoppaMan's user avatar
3 votes
1 answer
135 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 \...
skdys's user avatar
  • 171
2 votes
0 answers
345 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:...
S. G. Rinaldo's user avatar
1 vote
1 answer
726 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 ...
computational_scientist's user avatar
1 vote
1 answer
169 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?
Konrad's user avatar
  • 95
10 votes
1 answer
11k 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$...
KOF's user avatar
  • 243
8 votes
1 answer
450 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, ...
Integral's user avatar
  • 181
5 votes
0 answers
43 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, ...
Peter's user avatar
  • 51
6 votes
2 answers
483 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 a couple of sparse matrices from the University of Florida sparse matrix collection. The solver was able to solve non positive definite sparse matrices. ...
The Hiary's user avatar
  • 251
6 votes
1 answer
998 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 ...
Candic3's user avatar
  • 141
3 votes
1 answer
1k 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 ...
Costis's user avatar
  • 1,320
1 vote
1 answer
81 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....
James's user avatar
  • 11
1 vote
2 answers
215 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. ...
David's user avatar
  • 251
8 votes
1 answer
7k 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 ...
Eduardo J. Sanchez's user avatar
1 vote
1 answer
171 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$, ...
Eduardo J. Sanchez's user avatar
1 vote
0 answers
186 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}^...
wrong_path's user avatar