Iterative Methods in Linear Algebra part 2 Stan Tomov Innovative Computing Laboratory Computer Science Department The University of Tennessee Wednesday April 15 2009 CS 594 0004 04 15 2009 CS 594 0004 04 15 2009 Outline Part I Krylov iterative solvers Part II Convergence and preconditioning Part III Iterative eigen solvers CS 594 0004 04 15 2009 Part I Krylov iterative solvers CS 594 0004 04 15 2009 Krylov iterative solvers Building blocks for Krylov iterative solvers covered so far Projection minimization in a subspace Petrov Galerkin conditions Least squares minimization etc Orthogonalization CGS and MGS Cholesky or Householder based QR CS 594 0004 04 15 2009 Krylov iterative solvers We also covered abstract formulations for iterative solvers and eigen solvers What are the goals of this lecture Give specific examples of Krylov solvers Show how examples relate to the abstract formulation Show how examples relate to the building blocks covered so far specidicly to Projection and Orthogonalization But we are not going into the details CS 594 0004 04 15 2009 Krylov iterative solvers How are these techniques related to Krylov iterative solvers Remember projection slides 26 27 Lecture 7 left Projection in a subspace is the basis for an iterative method Here projection is in V In Krylov methods V is the Krylov subspace 2 Km A r0 span r0 Ar0 A r0 A m 1 r0 where r0 b Ax0 and x0 is an initial guess Often V or W are orthonormalized The projection is easier to find when we work with an orthonormal basis e g problem 4 from homework 5 projection in general vs orthonormal basis The orthonormalization can be CGS MGS Cholesky or Householder based etc CS 594 0004 04 15 2009 Krylov Iterative Methods To summarize Krylov iterative methods in general expend the Krylov subspace by a matrix vector product and do a projection in it Various methods result by specific choices of the expansion and projection CS 594 0004 04 15 2009 Krylov Iterative Methods A specific example with the Conjugate Gradient Method CG CS 594 0004 04 15 2009 Conjugate Gradient Method The method is for SPD matrices Both V and W are the Krylov subspaces i e at iteration i V W Ki A r0 span r0 Ar0 Ai 1 r0 The projection xi Ki A r0 satisfies the Petrov Galerkin conditions Axi b for Ki A r0 CS 594 0004 04 15 2009 Conjugate Gradient Method continued At every iteration there is a way to be shown later to construct a new search direction pi such that span p0 p1 pi Ki 1 A r0 and Api pj 0 for i 6 j Note A is SPD Api pj pi pj A can be used as an inner product i e p0 pi is an A orthogonal basis for Ki 1 A r0 we can easily find xi 1 x as xi 1 x0 0 p0 i pi Axi 1 pj b pj s t for j 0 i Namely because of the A orthogonality of p0 pi at iteration i 1 we have to find only i Axi 1 pj A xi i pi pi b pi Note xi above actually can be replaced by any x0 v v Ki A r0 i ri pi Api pi Why CS 594 0004 04 15 2009 Conjugate Gradient Method continued Conjugate Gradient Method Note One matrix vector product iteration at line 9 1 Compute r0 b Ax0 for some initial guess x0 2 for i 0 to do 3 i riT ri 4 if i 0 then 5 p0 r0 6 else 7 pi ri i pi 1 i 1 8 end if 9 qi Api 10 i p Ti q i i 11 xi 1 xi i pi 12 ri 1 ri i qi 13 check convergence continue if necessary 14 end for Two inner products iteration lines 3 and 10 In exact arithmetic ri 1 b Axi 1 Apply A to both sides of 11 and subtract from b to get line 12 Update for xi 1 is as pointed out before i e with i ri ri Api pi ri pi Api pi since ri pi 1 0 exercise Other relations to be proved exercise pi s span the Krylov space pi s are A orthogonal etc CS 594 0004 04 15 2009 Conjugate Gradient Method continued To sum it up In exact arithmetic we get the exact solution in at most n steps i e x x0 0 p0 i pi i 1 pi 1 n 1 pn 1 At every iteration one more term j pj is added to the current approximation xi x0 0 p0 i 1 pi 1 xi 1 x0 0 p0 i 1 pi 1 i pi xi i pi Note we do not have to solve linear system at every iteration because of the A orthogonal basis that we manage to maintain and expend at every iteration It can be proved that the error ei x xi satisfies i p k A 1 ei A 2 p e0 A k A 1 CS 594 0004 04 15 2009 Building orthogonal basis for a Krylov subspace Building orthogonal basis for a Krylov subspace We have seen the importance in Defining projections not just for linear solvers Abstract linear solvers and eigen solver formulations A specific example in CG where the basis for the Krylov subspaces is A orthogonal A is SPD We have seen how to build it CGS MGS Cholesky or Householder based etc These techniques can be used in a method specifically designed for Krylov subspaces general non Hermitian matrix namely in the Arnoldi s Method CS 594 0004 04 15 2009 Arnoldi s Method Note This orthogonalization is based on CGS line 4 Arnoldi s method Build an orthogonal basis for Km A r0 A can be general non Hermitian wj Avj Avj v1 v1 Avj vj vj up to iteration j vectors 1 2 3 4 5 6 7 8 v1 r0 for j 1 to m do hij Avj vi for i 1 j wj Avj h1j v1 hjj vj hj 1 j wj 2 if hj 1 j 0 Stop w vj 1 h j j 1 j end for v1 vj are orthogonal The space of this orthogonal basis grows by taking the next vector to be Avj If we do not exit at step 6 we will have Km A r0 span v1 v2 vm exercise CS 594 0004 04 15 2009 Arnoldi s Method continued Arnoldi s method in matrix notation Denote Vm v1 vm Hm 1 hij m 1 m and by Hm the matrix Hm 1 without the last row Note that Hm is upper Hessenberg 0s below the lower second sub diagonal and T AVm Vm Hm wm em VmT AVm Hm exercise CS 594 0004 04 15 2009 Arnoldi s Method continued Variations Explained using CGS Can be implemented with MGS Householder etc How to use it in linear solvers Example with the Full Orthogonalization Method FOM CS 594 0004 04 15 2009 FOM Look for solution in the form xm x0 ym 1 v1 ym m vm …
View Full Document
Unlocking...