15
votes
Accepted
Adaptive gradient descent step size when you can't do a line search
I'll begin with a general remark: first-order information (i.e., using only gradients, which encode slope) can only give you directional information: It can tell you that the function value decreases ...
- 11.9k
14
votes
Accepted
What are the differences between the different gradient-based numerical optimization methods?
First, you should forget about solving linear equations for the moment -- that's a different context from optimization, and trying to consider both on equal footing will only lead to confusion. Why ...
- 11.9k
14
votes
Accepted
What's the difference between conjugate gradient method and biconjugate gradient method
The conjugate gradient method is the provably fastest iterative solver, but only for symmetric, positive-definite systems. What would be awfully convenient is if there was an iterative method with ...
- 8,087
12
votes
What is required of the objective function in order to use Gauss Newton method?
Just to clarify notation, I'll be discussing the Gauss-Newton method for the problem
$\min \phi(x)=(1/2) \| F(x) \|_{2}^{2}$
with the search direction $p$ computed as the solution to the linear ...
- 17.6k
10
votes
Accepted
How can a CG solver solve a non positive definite sparse matrix
I highly recommend the following read:
J.R. Shewchuk, "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain"
In short, if the matrix is non-positive definite, there is no ...
- 8,287
10
votes
Which C++ linear algebra library is probably the fastest on solving huge sparse [square matrix] linear system?
Eigen 3 is a nice C++ template library some of whose routines are parallelized.
c.f. Eigen documentation
The parallelization is OMP only, so if you intend to parallelise using MPI (and OMP) it is ...
- 341
9
votes
What is the worst case complexity of Conjugate Gradient?
The answer is a resounding yes. The convergence rate bound of $(\sqrt{\kappa}-1) / (\sqrt{\kappa}+1)$ is sharp over the set of symmetric positive definite matrices with condition number $\kappa$. In ...
- 2,375
8
votes
Accepted
What happens when I use a conjugate gradient solver with a symmetric positive semi-definite matrix?
You first have to make sure that your system is solvable: this happens iff the right-hand side $b$ is orthogonal to the kernel of $A$. If $A$ has a dimension-1 kernel spanned by $v$, you need to have $...
- 8,553
7
votes
What are some reasons that Conjugate Gradient iteration does not converge?
If your matrix is symmetric, positive definite, the CG method may converge slowly, but it converges for $n\to\infty$. The only reason it does not converge on a computer are round-off errors, in ...
- 1,104
6
votes
Accepted
Caveats of Hessian free method
The approximation error is $\mathcal{O}(\varepsilon)$, where $\varepsilon$ is the parameter in the finite difference calculation. It will be good to know how this approximation affects the number of ...
- 29.8k
6
votes
What's the difference between conjugate gradient method and biconjugate gradient method
The conjugate gradient method only works to solve the system
$ A x = b $
if $A$ is symmetric and positive-definite (also works for negative definite). The reason it must be symmetric is that ...
- 4,567
6
votes
Accepted
Solving a system of nonlinear PDEs by minimization
1) If you're just looking to solve the PDEs without any other optimization, then my answer would be "none of them". Algorithms that discretize partial differential equations and then solve them as ...
- 29.8k
6
votes
Accepted
CG question: is symmetry always necessary?
The CG method works by producing in every iteration a vector $x^k\in\mathbb{R}^n$ that solves the minimization problem (assuming $x^0=0$ for simplicity)
$$\min_{x\in \mathcal{K}_k} \frac12(x-x^*)^TA(x-...
- 11.9k
6
votes
Why minimizing with respect to A-norm?
Wolfgang Bangerth's answer already says almost everything, but another subtle detail is that GMRES/MINRES minimize the norm of the residual, i.e., $\|Ax_k-b\|$, while CG minimizes the (A-)norm of the ...
- 8,553
5
votes
Accepted
How to verify solution to pre-conditioned linear systems solver?
You've started with a singular linear system of equations $Ax=b$. As a practical matter, it's unlikely that $b$ lies exactly in the range of $A$, so at best you can find a least squares solution that ...
- 17.6k
5
votes
Accepted
Relation between conjugate gradient method and finite elements method
The methods are unrelated. The finite element method is a way to convert a partial differential equation into a finite dimensional problem ("discretization") so it can be solved on a computer. The ...
- 50.2k
5
votes
Accepted
Why minimizing with respect to A-norm?
In some sense it doesn't matter: In finite dimensions, all norms are equivalent, so if an algorithm conveniently has the property that proving convergence in one norm is easy, then that's what people ...
- 50.2k
4
votes
Accepted
Linear equation system: Direct solver works, iterative solver does not
The problem was in the underlying coupled PDE FEM model. This model includes a potential which is not fixed in any point, so any result potential = phi + C would be a solution, where C is an ...
- 1,443
4
votes
Why does conjugate gradient work with this nonsymmetric preconditioner?
In short, orthogonalization of the Krylov vectors occurs with respect to the operator, but not with respect to the preconditioner.
Alright, so say we want to solve $Ax=b$ with preconditioner $B$. ...
- 677
4
votes
Accepted
Hessian-free and Truncated Newton methods
It looks like this paper is combining Hessian-free with truncated Newton method.
Yes, it is.
...the approach is referred to as Hessian-free method. That is because the Hessian is never computed ...
- 29.8k
4
votes
Solving the Poisson equation with Neumann Boundary Conditions - Finite Difference, BiCGSTAB
One of the standard ways to handle singular problems like Poisson with Neumann boundary conditions which lead to a sinuglar problem $Ax=b$ is to make the obtained solution orthogonal to the kernel (...
- 254
4
votes
Accepted
Why the iteration steps become twice if the step size reduces half for CG methods?
Let's say the condition number of the original matrix is $k_1$, and the one after refining the mesh is $k_2=4k_1$. You then want to compare the number of iterations necessary to reach a tolerance $\...
- 50.2k
4
votes
Accepted
What's wrong with the **PCG and MINRES** in matlab?
While very similar, each method is slightly different and you should definitely take this into account.
The GMRES method is the simplest, it will construct an orthogonal basis for $\mathcal{K}_k(A,b)$...
- 1,169
4
votes
In which cases does the nonlinear conjugate gradient method take more than $n$ steps?
The nonlinear conjugate gradient method will converge for a quadratic function in $N$ steps at most. You do not have a quadratic function, and have no guarantees on convergence. It can be helpful to ...
- 1,862
3
votes
Accepted
The linear system in Quasi Newton method
It is a well-known theorem that conjugate gradients is guaranteed to converge (in exact arithmetic) within $r+1$ steps for an identity-plus-rank-$r$ matrix, regardless of its size. In finite precision,...
- 2,375
3
votes
Boundary conditions in conjugate gradient method for poisson's equation
Neumann boundary conditions will show up in the right hand side of your problem, and so you can just start your iteration with any vector you want -- it doesn't have to satisfy any particular boundary ...
- 50.2k
3
votes
What are some reasons that Conjugate Gradient iteration does not converge?
Probabily the CG fails to converge because your problem is ill conditioned, the condition number of your matrix is too large. For SPD matrix A you can get the condition number calculating the ...
- 31
3
votes
Would recalculating the residual in the conjugate gradient method help?
This tutorial talks about recalculating the residual every 50 iterations to mitigate round-off errors.
- 656
3
votes
Why does smoothed aggregation multigrid method used as preconditioner in conjugate gradient slows down the solution time?
If I understand your question correctly you're solving a linear elasticity problem using conjugate gradient and it's preconditioned with a preconditioned AMG solver? It seems to me that this may be ...
- 1,862
3
votes
CG without division by 0 in a solution
Either of $p_k$ or $r_k$ being zero implies exact convergence in exact arithmetic, so that is never a problem. Conjugate gradient was used as a direct solver for linear systems of equations much ...
- 2,291
Only top scored, non community-wiki answers of a minimum length are eligible