# Tag Info

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
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
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

### 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
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

### 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

### 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
Accepted

• 50.2k
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

### 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
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

### 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

### 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 ...

### 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
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 ...