An Introduction to the Conjugate Gradient Method Without the Agonizing Pain

By Jonathan Richard Shewchuk. 1994

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Optimization

Citations in the corpus

Revisiting Natural Gradient for Deep Networks (2013, background): “Natural conjugate gradient, the manifold version of nonlinear conjugate gradient, is defined following the same intuitions (Shewchuck, 1994).”
Shallow Parsing with Conditional Random Fields (2003, methodology): “Our work shows that preconditioned conjugate-gradient (CG) (Shewchuk, 1994) or limited-memory quasi-Newton (L-BFGS) (Nocedal and Wright, 1999) perform comparably on very large problems (around 3.8 million features).”
Primordial Non-Gaussianity and Bispectrum Measurements in the Cosmic Microwave Background and Large-Scale Structure (2010, methodology): “, [80]) algorithm based on earlier results from the study of Smith et al.”
Surface corrections for peridynamic models in elasticity and fracture (2017, methodology): “Energy minimization using the nonlinear conjugate gradient method (see [35]) is used in this paper to find the equilibrium solutions.”
Relational Stacked Denoising Autoencoder for Tag Recommendation (2015, unknown): “Similar to (Li and Yeung 2009), the steepest descent method (Shewchuk 1994) is used to iteratively update Sk∗: Sk∗(t+ 1)← Sk∗(t) + δ(t)r(t) r(t)← λrXL 2 ,∗k − (λlLa + λrIJ)Sk∗(t) δ(t)← r(t) T r(t) r(t)T (λlLa + λrIJ)r(t) .”
Empirical evaluation of the improved Rprop learning algorithms (2003, methodology): “Fahlman's Quickprop (cf. [2] [15]), the BFGS (cf. [14]) algorithm, a quasi-Newton method, which iteratively estimates the inverse of the Hessian, and the conjugate gradient method (cf. [14] [20]).”
MISO Wireless Communication Systems via Intelligent Reflecting Surfaces : (Invited Paper) (2019, unknown): “5 [16]. in In contrast, the state-of-the-art SDR approach [7], [8] entails a computational complexity of O ( M + 1) 6 , which is prohibitively high compared to the proposed algorithms 3 .”
Sub-Sampled Newton Methods I: Globally Convergent Algorithms (2016, methodology): “s, i.e. a \mini-batch", and the size of such mini-batch grows as the optimization progresses. The resulting matrix is then damped in a Levenberg-Marquardt style, [25,30], and conjugate gradient, [46], is used to approximately solve the resulting linear system. The work in [38] is the rst to use”
A Survey on Bayesian Deep Learning (2016, methodology): “Similar to [67], the steepest descent method [101] is used to iteratively update S k ∗ : .”
Inexact Coordinate Descent: Complexity and Preconditioning (2013, methodology): “Because Bi is positive definite, a natural choice in the inexact case is to solve the system (54) using conjugate gradients [12, 35], and this is the method we adopt in what follows.”
First-person hyper-lapse videos (2014, methodology): “28 in a reduced domain using multi-splines with a spacing of 32 pixels [Szeliski et al. 2011] using a standard conjugate gradients solver [Shewchuk 1994].”
Numerical Methods for Electronic Structure Calculations of Materials (2010, methodology): “5 Conjugate gradient methods Nonlinear conjugate gradient (NLCG) algorithms [66,165] fo rm another important class of methods used in electronic structure packages ( .”
Regularized Distance Metric Learning: Theory and Algorithm (2009, methodology): “whose optimal value can be computed efficiently using the conjugate gradient method [11].”
ECO: Efficient Convolution Operators for Tracking (2016, methodology): “This is obtained by substituting the standard Fletcher-Reeves formula to the Polak-Ribière formula [34] for finding the momentum factor, since it has shown improved convergence rates for inexact and flexible preconditioning [18], which have similarities to our scenario.”
Efficient algorithms for ranking with SVMs (2010, methodology): “Since (2) is an unconstrained and differentiable objective function, the two following standard optimization methods can be used: Non-linear conjugate gradient This is one of the most popular gradient based methods (Shewchuk, 1994).”