CS 267 Applications of Parallel Computers Solving Linear Systems Arising from PDEs Using MultigridWhere Was I Last Week?Review of Earlier Lecture on Solving PDEs2D Poisson’s equation: 2u/x2 + 2u/y2 = f(x,y)Algorithms for 2D Poisson with N UnknownsMultigrid MotivationSlide 7Multigrid OverviewSame Big Idea Used in Other ProblemsMultigrid uses Divide-and-Conquer in 2 WaysMultigrid Sketch on a Regular 1D MeshMultigrid Sketch on a Regular 2D MeshMultigrid OperatorsSlide 14Multigrid V-Cycle AlgorithmWhy is this called a V-Cycle?Complexity of a V-Cycle on a 2D GridFull Multigrid (FMG)Full Multigrid Cost AnalysisComplexity of Solving Poisson’s EquationDetails of Multigrid OperatorsThe Solution Operator S(i) - DetailsWeighted Jacobi Damps High Frequency ErrorMultigrid as Divide and Conquer AlgorithmThe Restriction Operator R(i) - DetailsInterpolation OperatorConvergence Picture of Multigrid in 1DConvergence Picture of Multigrid in 2DConvergence Rate of Multigrid VariationsParallel 2D MultigridPerformance Model of parallel 2D MultigridComparison of MethodsPracticalitiesMultigrid on an Adaptive MeshMultiblock ApplicationsAdaptive Mesh RefinementSupport for AMRMultigrid on an Unstructured MeshSlide 39Summary01/14/19 CS267 Lectures 19 1CS 267 Applications of Parallel ComputersSolving Linear Systems Arising from PDEsUsing MultigridKatherine Yelickwww.cs.berkeley.edu/~yelick/cs26701/14/19 CS267 Lectures 19 2Where Was I Last Week?Whirlwind tour of Japanese SupercomputingComputer facilitiesThe Earth Simulator (40 Tflops)A Supercluster of PCs (11 Tflops)Three government agenciesMEXT, CSTP, METIUniversities and Research LabsUniversity of TokyoUniversity to TsukubaRIST, AISTVendorsNEC, Hitachi, Fujitsu, Sony01/14/19 CS267 Lectures 19 3Review of Earlier Lecture on Solving PDEs•Review Poisson equation•Overview of Methods for Poisson Equation•Jacobi’s method•Red-Black SOR method•Conjugate Gradients•FFTToday:•MultigridReduce to sparse-matrix-vector multiplyNeed them to understand Multigrid01/14/19 CS267 Lectures 19 42D Poisson’s equation: 2u/x2 + 2u/y2 = f(x,y)The the matrix T for a regular mesh is3D is analogous4 -1 -1-1 4 -1 -1 -1 4 -1 -1 4 -1 -1 -1 -1 4 -1 -1 -1 -1 4 -1 -1 4 -1 -1 -1 4 -1 -1 -1 4T =4-1-1-1-1Graph and “stencil”01/14/19 CS267 Lectures 19 5Algorithms for 2D Poisson with N UnknownsAlgorithm Serial PRAM Memory #ProcsDense LU N3N N2N2Band LU N2N N3/2NJacobi N2 N N NExplicit Inv. N2 log N N2 N2Conj.Grad. N 3/2N 1/2 *log N N NRB SOR N 3/2N 1/2N NSparse LU N 3/2N 1/2N*log N NFFT N*log N log N N NMultigrid N log2 N N NLower bound N log N NPRAM is an idealized parallel model with zero cost communication01/14/19 CS267 Lectures 19 6Multigrid MotivationThe FFT is O(log N), but has an O(N) transpose that prevents scalingRecall that Jacobi, SOR, CG, or any other sparse-matrix-vector-multiply-based algorithm can only move information one grid call at a timeTakes N1/2 steps to get information across gridCan show that decreasing error by fixed factor c<1 takes (log n) steps Convergence to fixed error < 1 takes (log n ) stepsSOR and CG take N1/2 stepsTherefore, converging in O(1) steps requires moving information across grid faster than to one neighboring grid cell per step01/14/19 CS267 Lectures 19 7Multigrid Motivation01/14/19 CS267 Lectures 19 8Multigrid OverviewBasic Algorithm:Replace problem on fine grid by an approximation on a coarser gridSolve the coarse grid problem approximately, and use the solution as a starting guess for the fine-grid problem, which is then be iteratively updatedSolve the coarse grid problem recursively, i.e. by using a still coarser grid approximation, etc.Success depends on coarse grid solution being a good approximation to the fine grid01/14/19 CS267 Lectures 19 9Same Big Idea Used in Other ProblemsReplace fine problem by coarse approximation, recursivelyMultilevel Graph Partitioning (METIS): Replace graph to be partitioned by a coarser graph, obtained via Maximal Independent SetGiven partitioning of coarse grid, refine using Kernighan-LinBarnes-Hut (and Fast Multipole Method):Approximate leaf node of QuadTree containing many particles by Center-of-Mass and Total-Mass (or multipole expansion)Approximate internal nodes of QuadTree by combining expansions of childrenForce in any particular node approximated by combining expansions of a small set of other nodesAll examples depend on coarse approximation being accurate enough (at least if we are far enough away)01/14/19 CS267 Lectures 19 10Multigrid uses Divide-and-Conquer in 2 WaysFirst way:Solve problem on a given grid by calling Multigrid on a coarse approximation to get a good guess to refineSecond way:Think of error as a sum of sine curves of different frequenciesSame idea as FFT solution, but not explicit in algorithmEach call to Multigrid responsible for suppressing coefficients of sine curves of the lower half of the frequencies in the errordifferent grid levels will damp different frequency errors01/14/19 CS267 Lectures 19 11Multigrid Sketch on a Regular 1D MeshConsider a 2m+1 grid in 1D for simplicityLet P(i) be the problem of solving the discrete Poisson equation on a 2i+1 grid in 1D Write linear system as T(i) * x(i) = b(i)P(m) , P(m-1) , … , P(1) is a sequence of problems from finest to coarsest01/14/19 CS267 Lectures 19 12Multigrid Sketch on a Regular 2D MeshConsider a 2m+1 by 2m+1 gridLet P(i) be the problem of solving the discrete Poisson equation on a 2i+1 by 2i+1 grid in 2DWrite linear system as T(i) * x(i) = b(i)P(m) , P(m-1) , … , P(1) is a sequence of problems from finest to coarsest01/14/19 CS267 Lectures 19 13Multigrid OperatorsFor problem P(i) :b(i) is the RHS and x(i) is the current estimated solution (T(i) is implicit in the operators below.)Multigrid will be defined by a repeated sequence of operatorsThe multigrid operators average values on neighboring grid pointsNeighboring grid points on coarse problems are far away in fine problems, so information moves quickly on
View Full Document
Unlocking...