Transcription of Conjugate Gradient Method - Stanford University
{{id}} {{{paragraph}}}
Example: biology
Conjugate Gradient Method - Stanford University
Conjugate Gradient Method direct and indirect methods positive definite linear systems Krylov sequence derivation of the Conjugate Gradient Method spectral analysis of Krylov sequence preconditioningEE364b, Stanford UniversityProf. Mert Pilanciupdated: May 5, 2022 Three classes of methods for linear equationsmethods to solve linear systemAx=b,A Rn n dense direct(factor-solve methods) runtime depends only on size; independent of data, structure, orsparsity work well fornup to a few thousand sparse direct(factor-solve methods) runtime depends on size, sparsity pattern; (almost) independent ofdata can work well fornup to104or105(or more) requires good heuristic for orderingEE364b, Stanford University1 indirect(iterative methods) runtime depends on data, size, sparsity, required accuracy requires tuning, preconditioning.
Preconditioned conjugate gradient algorithm • idea: apply CG after linear change of coordinates x = Ty, detT 6= 0 • use CG to solve TTATy = TTb; then set x⋆ = T−1y⋆ • T or M = TTT is called preconditioner • in naive implementation, each iteration requires multiplies by T and TT (and A); also need to compute x⋆ = T−1y⋆ at end • can re-arrange computation so each iteration ...
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: