资源描述：
《全区校园安全生产大检查活动开展情》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、CS267:ApplicationsofParallelComputers Lecture23: SolvingthePoissonEquationKathyYelickhttp://www-inst.eecs.berkeley.edu/~cs2679/20/20211CS267,YelickLectureSchedule11/19:SolvingthePoissonEquation11/21:SolvingthePoissonEquation11/26:Tree-basedcomputation(PoissonAgain)11/28:VisittoNERSCVisualizat
2、iongroupneedtopickup“pass”forthebus12/3:TBD12/5:TheFutureofParallelComputing12/12:CS267PosterSession(1-3pm,Woz)12/14:FinalPapersdue9/20/20212CS267,YelickOutlineReviewPoissonequationOverviewofMethodsforPoissonEquationJacobi’smethodRed-BlackSORmethodConjugateGradientsFFTMultigridComparisonofmetho
3、dsParticlemethods(nextweek)2DPoisson’sequationConsiderthecontinuous2DPoissonequation,againd2u/dx2+d2u/dy2=bThediscreteversionis:T*x=b4-1-1-1-14-1-1-14-1-1-14-1-14-1-1-1-14-1-1-1-14-1-14-1-1-14-1-1-14T=Graphand“stencil”9/20/20214CS267,YelickDetailsofDiscretizationApproximated2u/dx2bydifferencesu
4、’’(x,y)~=u’(x+1/2,y)–u’(x-1/2,y)~=u(x+1,y)-u(x,y)–(u(x,y)–u(x-1,y))=-2u(x,y)+u(x-1,y)+u(x+1,y)Similarlyford2u/dy2SodiscretePoissonfor2Dmeshis:4u(x,y)–u(x-1,y)–u(x+1,y)–u(x,y-1)–u(x,y+1)(withsignchange)9/20/20215CS267,YelickAlgorithmsfor2DPoissonwithNUnknownsAlgorithmSerialPRAMMemory#ProcsDenseL
5、UN3NN2N2BandLUN2NN3/2NJacobiN2NNNExplicitInv.NlogNNNConj.Grad.N3/2N1/2*logNNNRBSORN3/2N1/2NNSparseLUN3/2N1/2N*logNNFFTN*logNlogNNNMultigridNlog2NNNLowerboundNlogNNPRAMisanidealizedparallelmodelwithzerocostcommunication2229/20/20216CS267,YelickMultigridMotivationRecallthatJacobi,SOR,CG,oranyothe
6、rsparse-matrix-vector-multiply-basedalgorithmcanonlymoveinformationonegridcallatatimeCanshowthatdecreasingerrorbyfixedfactorc<1takesW(logn)stepsConvergencetofixederror<1takesW(logn)stepsTherefore,converginginO(1)stepsrequiresmovinginformationacrossgridfasterthantooneneighboringgridcellperstep9/
7、20/20217CS267,YelickMultigridMotivation9/20/20218CS267,YelickMultigridOverviewBasicAlgorithm:ReplaceproblemonfinegridbyanapproximationonacoarsergridSolvethecoarsegridproblemapproximately,andusethesolutionasastartingguessforthefine
