A popular krylov subspace method for solving linear systems of equations, particularly those that exhibit symmetric positive definiteness.

83 questions
Filter by
Sorted by
Tagged with
21k views

### BFGS vs. Conjugate Gradient Method

What considerations should I be making when choosing between BFGS and conjugate gradient for optimization? The function I am trying to fit with these variables are exponential functions; however, the ...
3k views

### What is the principle behind the convergence of Krylov subspace methods for solving linear systems of equations?

As I understand it, there are two major categories of iterative methods for solving linear systems of equations: Stationary Methods (Jacobi, Gauss-Seidel, SOR, Multigrid) Krylov Subspace methods (...
4k views

### Problems where Conjugate gradient works much better than GMRES

I am interested in cases where Conjugate gradient works much better than GMRES method. In general, CG is preferable choice in many cases of SPD (symmetric-positive-definite) because it requires less ...
8k views

For a project, I have to implement these two methods and compare how they perform on different functions. It looks like the conjugate gradient method is meant to solve systems of linear equations of ...
960 views

### Calculating determinant while solving $Ax=b$ using CG

I am solving $Ax=b$ for a huge sparse positive definite matrix $A$ using the conjugate gradient (CG) method. It is possible to compute the determinant of $A$ using the information produced during the ...
3k views

### What's the difference between conjugate gradient method and biconjugate gradient method

What's the difference between these two methods? Can a problem be solved by one method will be able to solved by the other? Can both/or one of them be parallelized with OpenMP and/or MPI?
1k views

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, ...
274 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-...
194 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_*$ ...
For the optimization problem $\underset{\mathbf{x}\in \mathbb{R}^n}{\operatorname{argmin}} f(\mathbf{x})$, we can use the following standard nonlinear conjugate gradient method to find the solution: $... 2answers 195 views ### Looking for a mathematical proof of stability in floating point arithmetic of CG - any reference? I am looking for a reference - paper, book, discussion, anything that has a mathematical proof for stability of the conjugate gradient method in floating point arithmetic. Something similar for ... 2answers 339 views ### best way to optimize a function with linear/non-linear parameters I am trying to fit some raw data using a function of the form$f(r) = \sum_{i=1}^{K} d_kS_k(n_k,\alpha_k,r)$where$S_k(n_k,\alpha_k,r) = \frac{\alpha_k ^{n_k+3}}{(n_k+2)!}r^{n_k}\exp(-\alpha_kr)$... 1answer 337 views ### Linear equation system: Direct solver works, iterative solver does not I have to solve for x in b = A*x, where a is sparse. This works fine with Matlab's mldivide: x = A \ b. Since I will have to use an iterative algorithm for very large A, I'm currently testing Matlab's ... 1answer 177 views ### Is there a nonlinear solver similar to CGNR evaluating only$A^TAx$? First of all, I am quite new to this field and I excuse myself in advance for any stupid content in this question. In the field of compressed sensing or deblurring I have a nonlinear optimization ... 2answers 1k views ### Conjugate gradient method to minimize a function I am having some serious difficulties trying to understand how to use (apply) CG to minimize a function. In all the textbooks and notes, the step size$\alpha$is give by the following expression $$\... 0answers 132 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 ... 0answers 219 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} |} \... 2answers 6k views ### What are some reasons that Conjugate Gradient iteration does not converge? I would greatly appreciate it if you could share some reasons the Conjugate Gradient iteration for Ax = b does not converge? My matrix A is symmetric positive definite. Thank you so much! Edit with ... 2answers 106 views ### How can you explain the following bound on the inner product? I am reading a paper on stability of CG, and I came across the following statement: $$\frac{\|A\|\,\|p\|^2}{\langle p,Ap\rangle} \leq \kappa(A)$$ where \kappa(\cdot) is ... 1answer 110 views ### What happens when I use a conjugate gradient solver with a symmetric positive semi-definite matrix? I have a symmetric positive semi-definite matrix, i.e., a laplacian and wonder what may happen when I use a CG solver, that is an algorithm for positive definite matrices. What happens when the ... 1answer 158 views ### CG question: is symmetry always necessary? Consider the 1D Poisson equation$$\nabla^2 u = f.$$Using finite difference method on cell corner data and a uniform grid with ghost points, I think we can write the system of equations with Neumann ... 1answer 173 views ### How can a CG solver solve a non positive definite sparse matrix I am using the CUSP CG solver and I ran it on couple of sparse matrices from the University of Florida sparse matrix collection. The solver was able to solve non positive definite sparse matrices. My ... 1answer 899 views ### Is a checkerboard block decomposition of a matrix useful when solving a linear system with a parallel conjugate gradient method? According to these lecture notes, a checkerboard block decomposition should exhibit better scalability when applied to parallel matrix-vector multiplication (presumably because of greater cache hit ... 1answer 68 views ### Why does smoothed aggregation multigrid method used as preconditioner in conjugate gradient slows down the solution time? I'm solving a system of linear equations obtained from the FEM discretization of a simple linear elasticity problem on a cube with zero displacements at one plane and a load on the opposite one. The ... 1answer 101 views ### Conjugate Gradient for singular 2D poisson finite element with Neumann Boundary Conditions Heavily edited question after I realised partly what the problem was I have programmed a simple 2D square finite element solution to the Poisson equation -\Delta u = f The source function ... 1answer 407 views ### Linear constraints for L-BFGS-B I know L-BFGS-B only supports simple box constrains of the form: l_i \leq x_i \leq u_i, where l_i and u_i are constants. For my specific optimization problem, I need to specify some simple ... 2answers 375 views ### 2D Laplace problem with mixed boundary conditions using Conjugate Gradients I am being asked for one of my classes to solve 2D Laplace equations with mixed boundary conditions using the Conjugate Gradient method. The equations and conditions are given as:$$ \frac{\partial^... 1answer 223 views ### Trust-region Newton: implementation issue with Conjugate Gradient calculations UPDATE: The problem turned out to be the step (refer penultimate paragraph below) where I was factoring out a small value from the vectors of the numerator and denominator and then computed dot ... 0answers 62 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 ... 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 ... 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 ... 0answers 111 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. ... 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} wherei=2$,$g_{ij}g_{jk}=2\epsilon\delta_{ik}$and$f(\textbf{x})=-\nabla\phi(\...
Last week, I have learned the details of the robust iterative methods of PCG, MINRES, GMRES, which will converges to the exact solution $x^*$ of nonsingular system within $N$ steps for \$A\in \mathbb{R}...