Questions tagged [conjugate-gradient]
A popular krylov subspace method for solving linear systems of equations, particularly those that exhibit symmetric positive definiteness.
19
questions with no upvoted or accepted answers
7
votes
0answers
72 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 (...
5
votes
0answers
136 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 ...
5
votes
0answers
35 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, ...
5
votes
0answers
279 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-...
5
votes
0answers
201 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
0answers
221 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} |}
\...
3
votes
0answers
63 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 ...
3
votes
0answers
44 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 ...
3
votes
0answers
152 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:...
3
votes
0answers
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 ...
3
votes
0answers
112 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$. ...
3
votes
0answers
90 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(\...
2
votes
0answers
104 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 ...
2
votes
0answers
76 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
0answers
63 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. ...
1
vote
0answers
53 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 ...
1
vote
0answers
161 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}^...
1
vote
0answers
153 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 ...
0
votes
0answers
65 views
Arnoldi Decomposition Algorithm
I try to get into GMRES via Arnoldi-Decomposition. For my understanding, I Implemented the Arnoldi-Decomposition in python.
...