Questions tagged [conjugate-gradient]
A popular krylov subspace method for solving linear systems of equations, particularly those that exhibit symmetric positive definiteness.
90
questions
3
votes
0
answers
24
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 ...
- 31
1
vote
0
answers
67
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 ...
- 326
2
votes
1
answer
66
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) ...
- 359
0
votes
0
answers
45
views
Normalizing the right-hand side in Jacobi-preconditioned conjugate gradients
I have been reading the following paper: CG versus MINRES: An empirical comparison.
In it a conjugate gradient solver is applied to a system matrix $A$ Jacobi-preconditioned on both sides. ...
- 359
0
votes
2
answers
186
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 ...
- 21
0
votes
3
answers
344
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 ...
- 29
2
votes
1
answer
53
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 ...
- 121
1
vote
0
answers
76
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. ...
- 471
1
vote
1
answer
100
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} + \...
- 3,058
1
vote
0
answers
85
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 ...
- 23
4
votes
1
answer
142
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 ...
- 41
6
votes
2
answers
724
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 ...
- 587
3
votes
0
answers
78
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 ...
0
votes
0
answers
115
views
Arnoldi Decomposition Algorithm
I try to get into GMRES via Arnoldi-Decomposition. For my understanding, I Implemented the Arnoldi-Decomposition in python.
...
- 295
1
vote
1
answer
99
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 ...
- 51
5
votes
0
answers
140
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 ...
- 161
2
votes
1
answer
400
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}...
- 961
3
votes
0
answers
45
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 ...
- 171
1
vote
2
answers
56
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 ...
- 961
1
vote
1
answer
52
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 ...
- 877
1
vote
1
answer
47
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$ ...
- 961
3
votes
1
answer
245
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 ...
- 117
8
votes
0
answers
126
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,121
2
votes
1
answer
215
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 ...
- 23
2
votes
1
answer
104
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 \...
- 151
2
votes
0
answers
255
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
1
answer
399
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
1
answer
132
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?
- 85
8
votes
1
answer
7k
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$...
- 223
8
votes
1
answer
320
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, ...
- 181
5
votes
0
answers
42
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, ...
- 51
6
votes
2
answers
343
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. ...
- 241
6
votes
1
answer
662
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 ...
- 141
3
votes
1
answer
731
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 ...
- 1,300
0
votes
1
answer
73
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....
- 1
1
vote
2
answers
203
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. ...
- 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 ...
- 265
1
vote
1
answer
169
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$, ...
- 265
1
vote
0
answers
175
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}^...
- 394
4
votes
2
answers
2k
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
$$ \...
- 394
2
votes
0
answers
108
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 ...
- 185
3
votes
0
answers
3k
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 ...
- 81
3
votes
1
answer
3k
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 ...
- 31
3
votes
1
answer
228
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 ...
- 599
1
vote
2
answers
1k
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 ...
- 95
9
votes
1
answer
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: $\...
- 223
4
votes
2
answers
516
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^...
- 43
1
vote
1
answer
127
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 ...
- 656
5
votes
1
answer
810
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{...
- 153
1
vote
1
answer
86
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 ...
- 87