Questions tagged [conjugate-gradient]
A popular krylov subspace method for solving linear systems of equations, particularly those that exhibit symmetric positive definiteness.
15
questions with no upvoted or accepted answers
8
votes
0answers
155 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, ...
6
votes
0answers
61 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
182 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
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, ...
4
votes
0answers
208 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} |}
\...
4
votes
0answers
243 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
0answers
42 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
2k 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
109 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
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(\...
2
votes
0answers
86 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:...
2
votes
0answers
99 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
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 ...
1
vote
0answers
155 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
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 ...
