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 ...
Christian Clason's user avatar
15 votes

Why are systems with clustered eigenvalues easy to solve?

A good explanation of this phenomena with many examples is given in Iterative Methods for Linear and Nonlinear Equations by Tim Kelley. The crux of it comes down to the fact that each step of a ...
whpowell96's user avatar
  • 2,054
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 ...
Christian Clason's user avatar
11 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 ...
Brian Borchers's user avatar
11 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 $...
Federico Poloni's user avatar
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 ...
Nox's user avatar
  • 341
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 ...
Anton Menshov's user avatar
  • 8,602
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 ...
Richard Zhang's user avatar
8 votes

Why are systems with clustered eigenvalues easy to solve?

At the $k$th iteration, typical Krylov methods for solving $Ax=b$ (such as CG, MINRES, and GMRES) implicitly construct a $k$th order polynomial $Q(x)$ such that: $Q(0) = 1$. $|Q(\lambda_i)|$ is as ...
Nick Alger's user avatar
  • 3,143
7 votes

BiCGSTAB convergence

First of all, size 40 is pretty much microscopic for the sort of purposes that BiCGstab was invented. I assure you, this method is great for matrices of sizes in the millions and beyond. Then: even ...
Victor Eijkhout's user avatar
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-...
Christian Clason's user avatar
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 ...
Federico Poloni's user avatar
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 ...
Wolfgang Bangerth's user avatar
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 ...
Brian Borchers's user avatar
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 ...
Wolfgang Bangerth's user avatar
5 votes

Preconditioned congugate gradaient vs Untransfomed preconditioned conjugate gradient

The two algorithms are designed to solve slightly different problems. Shewchuk's monograph is describing two different approaches to preconditioning the problem $Ax = b$ using a preconditioning matrix ...
Daniel Shapero's user avatar
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$. ...
wyer33's user avatar
  • 757
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 (...
VorKir's user avatar
  • 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 $\...
Wolfgang Bangerth's user avatar
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)$...
Thijs Steel's user avatar
  • 1,386
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 ...
EMP's user avatar
  • 2,069
3 votes
Accepted

Conjugate gradient - ill-conditioning and numerical tolerance

Let $x$ denote the solution of $Ax=b$ and let $\hat{x}$ denote the computed solution. We cannot hope to do better than $$\hat{x} = \text{fl}(x),$$ i.e., the floating point representation of $x$. In ...
Carl Christian's user avatar
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 ...
Wolfgang Bangerth's user avatar
3 votes

Conjugate gradient method to minimize a function

(Disclaimer: I have taken this material from Ref.[1]) For nonlinear CG, three changes are required for the linear algorithm Recursive formula for the stepsize can not be used Time step size $\alpha$ ...
Subodh's user avatar
  • 1,480
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,...
Richard Zhang's user avatar
3 votes

What happens when I use a conjugate gradient solver with a symmetric positive semi-definite matrix?

To at least partially answer the question: You have to make sure the system is solvable in the first place. As mentined in the accepted answer, "the system $Ax=b$ is solvable iff $b \bot Ker(A)$&...
Jakub Homola's user avatar
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 ...
EMP's user avatar
  • 2,069
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 ...
Abdullah Ali Sivas's user avatar
3 votes

When will the Orthomin/CG iteration fails

Your statement is not correct, I believe. The equivalent condition for the real case is that the iteration will fail if there is a vector $x\in{\mathbb R}^n$ so that $x^T A x = 0$, which is equivalent ...
Wolfgang Bangerth's user avatar
3 votes

Reason for why apparent acceleration of algebraic multigrid solve by addition of positive definite diagonal matrix

The computation in your update does most of the work towards a solution. You just need to note that $\frac{\varepsilon_1}{\varepsilon_2} \leq \frac{\max D_{ii}}{\min D_{ii}} = \kappa(D)$, and that $$ ...
Federico Poloni's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible