DOC PREVIEW
Berkeley COMPSCI C267 - Solving Linear Systems arising from PDEs - II

This preview shows page 1-2-16-17-18-33-34 out of 34 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 267 Applications of Parallel Computers Lecture 25: Solving Linear Systems arising from PDEs - IIReview of Last Lecture and Outline2D Poisson’s equationAlgorithms for 2D Poisson Equation with N unknownsMultigrid MotivationSlide 6Multigrid OverviewSame Big Idea used beforeMultigrid uses Divide-and-Conquer in 2 WaysMultigrid Sketch (1D and 2D)Multigrid OperatorsMultigrid V-Cycle AlgorithmWhy is this called a V-Cycle?Complexity of a V-CycleFull Multigrid (FMG)Full Multigrid Cost AnalysisComplexity of Solving Poisson’s EquationThe Solution Operator S(i) - DetailsWeighted Jacobi chosen to damp high frequency errorMultigrid as Divide and Conquer AlgorithmThe Restriction Operator R(i) - DetailsInterpolation OperatorConvergence Picture of Multigrid in 1DConvergence Picture of Multigrid in 2DParallel 2D MultigridPerformance Model of parallel 2D MultigridComparison of MethodsPracticalitiesMultigrid on an Adaptive MeshMultiblock ApplicationsAdaptive Mesh RefinementSupport for AMRMultigrid on an Unstructured MeshSlide 34CS267 L25 Solving PDEs II.1Demmel Sp 1999CS 267 Applications of Parallel ComputersLecture 25: Solving Linear Systems arising from PDEs - IIJames Demmelhttp://www.cs.berkeley.edu/~demmel/cs267_Spr99CS267 L25 Solving PDEs II.2Demmel Sp 1999Review of Last Lecture and Outline°Review Poisson equation°Overview of Methods for Poisson Equation°Jacobi’s method°Red-Black SOR method°Conjugate Gradients°FFT°Multigrid°Comparison of methodsReduce to sparse-matrix-vector multiplyNeed them to understand MultigridCS267 L25 Solving PDEs II.3Demmel Sp 19992D Poisson’s equation°Similar to the 1D case, but the matrix T is now°3D 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”CS267 L25 Solving PDEs II.4Demmel Sp 1999Algorithms for 2D Poisson Equation with N unknownsAlgorithm Serial PRAM Memory #Procs°Dense LU N3N N2N2°Band LU N2N N3/2N°Jacobi N2 N N N°Explicit Inv. N log N N N°Conj.Grad. N 3/2N 1/2 *log N N N°RB SOR N 3/2N 1/2N N°Sparse LU N 3/2N 1/2N*log N N°FFT N*log N log N N N°Multigrid N log2 N N N°Lower bound N log N NPRAM is an idealized parallel model with zero cost communication2 22CS267 L25 Solving PDEs II.5Demmel Sp 1999Multigrid Motivation°Recall that Jacobi, SOR, CG, or any other sparse-matrix-vector-multiply-based algorithm can only move information one grid call at a time°Can show that decreasing error by fixed factor c<1 takes (log n) steps°Convergence to fixed error < 1 takes (log n ) steps°Therefore, converging in O(1) steps requires moving information across grid faster than to one neighboring grid cell per stepCS267 L25 Solving PDEs II.6Demmel Sp 1999Multigrid MotivationCS267 L25 Solving PDEs II.7Demmel Sp 1999Multigrid Overview°Basic Algorithm:•Replace problem on fine grid by an approximation on a coarser grid•Solve the coarse grid problem approximately, and use the solution as a starting guess for the fine-grid problem, which is then iteratively updated•Solve 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 gridCS267 L25 Solving PDEs II.8Demmel Sp 1999Same Big Idea used before°Replace fine problem by coarse approximation, recursively°Multilevel Graph Partitioning (METIS): •Replace graph to be partitioned by a coarser graph, obtained via Maximal Independent Set•Given partitioning of coarse grid, refine using Kernighan-Lin°Barnes-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 children•Force in any particular node approximated by combining expansions of a small set of other nodes°All examples depend on coarse approximation being accurate enough (at least if we are far enough away)CS267 L25 Solving PDEs II.9Demmel Sp 1999Multigrid uses Divide-and-Conquer in 2 Ways°First way:•Solve problem on a given grid by calling Multigrid on a coarse approximation to get a good guess to refine°Second way:•Think of error as a sum of sine curves of different frequencies•Same idea as FFT solution, but not explicit in algorithm•Each call to Multgrid responsible for suppressing coefficients of sine curves of the lower half of the frequencies in the error (pictures later)CS267 L25 Solving PDEs II.10Demmel Sp 1999Multigrid Sketch (1D and 2D)°Consider a 2m+1 grid in 1D (2m+1 by 2m+1 grid in 2D) for simplicity°Let P(i) be the problem of solving the discrete Poisson equation on a 2i+1 grid in 1D (2i+1 by 2i+1 grid in 2D)•Write linear system as T(i) * x(i) = b(i)°P(m) , P(m-1) , … , P(1) is sequence of problems from finest to coarsestCS267 L25 Solving PDEs II.11Demmel Sp 1999Multigrid Operators°For problem P(i) :•b(i) is the RHS and •x(i) is the current estimated solution •(T(i) is implicit in the operators below.)°All the following operators just average values on neighboring grid points•Neighboring grid points on coarse problems are far away in fine problems, so information moves quickly on coarse problems°The restriction operator R(i) maps P(i) to P(i-1)•Restricts problem on fine grid P(i) to coarse grid P(i-1) by sampling or averaging•b(i-1)= R(i) (b(i))°The interpolation operator In(i-1) maps an approximate solution x(i-1) to an x(i)•Interpolates solution on coarse grid P(i-1) to fine grid P(i)•x(i) = In(i-1)(x(i-1))°The solution operator S(i) takes P(i) and computes an improved solution x(i) on same grid•Uses “weighted” Jacobi or SOR•x improved (i) = S(i) (b(i), x(i))°Details of these operators after describing overall algorithmboth live on grids of size 2i-1CS267 L25 Solving PDEs II.12Demmel Sp 1999Multigrid V-Cycle AlgorithmFunction MGV ( b(i), x(i) ) … Solve T(i)*x(i) = b(i) given b(i) and an initial guess for x(i) … return an improved x(i) if (i = 1) compute exact solution x(1) of P(1) only 1 unknown return x(1) else x(i) = S(i) (b(i), x(i)) improve solution by damping high


View Full Document

Berkeley COMPSCI C267 - Solving Linear Systems arising from PDEs - II

Documents in this Course
Lecture 4

Lecture 4

52 pages

Split-C

Split-C

5 pages

Lecture 5

Lecture 5

40 pages

Load more
Download Solving Linear Systems arising from PDEs - II
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Solving Linear Systems arising from PDEs - II and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Solving Linear Systems arising from PDEs - II 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?