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

This preview shows page 1-2-3-18-19-36-37-38 out of 38 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 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 38 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 38 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 38 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 38 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 38 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 38 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 38 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 267: Applications of Parallel Computers Solving Linear Systems arising from PDEs - IIReview of Last Lecture and OutlinePoisson’s equation in 1D: 2u/x2 = f(x)2D Poisson’s equationAlgorithms for 2D (3D) Poisson Equation (N vars)Multigrid MotivationSlide 7Multigrid OverviewSame Big Idea used elsewhereMultigrid uses Divide-and-Conquer in 2 WaysMultigrid Sketch in 1DMultigrid 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 Operator In(i-1): detailsConvergence Picture of Multigrid in 1DConvergence Picture of Multigrid in 2DParallel 2D MultigridPerformance Model of parallel 2D Multigrid (V-cycle)Comparison of Methods (in O(.) sense)PracticalitiesMultigrid on an Adaptive MeshMultiblock ApplicationsAdaptive Mesh RefinementSupport for AMRMultigrid on an Unstructured MeshSlide 36Source of Unstructured Finite Element Mesh: VertebraMultigrid for nonlinear elastic analysis of bone03/14/05 CS267 Lecture 15CS 267: Applications of Parallel ComputersSolving Linear Systems arising from PDEs - IIJames Demmelwww.cs.berkeley.edu/~demmel/cs267_Spr0503/14/05 CS267 Lecture 15Review 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 Multigrid03/14/05 CS267 Lecture 15Poisson’s equation in 1D: 2u/x2 = f(x)2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1 2T =2-1 -1Graph and “stencil”03/14/05 CS267 Lecture 152D 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”03/14/05 CS267 Lecture 15Algorithms for 2D (3D) Poisson Equation (N vars)Algorithm Serial PRAM Memory #Procs°Dense LU N3N N2N2°Band LU N2 (N7/3) N N3/2 (N5/3) N°Jacobi N2 N N N°Explicit Inv. N2 log N N2N2°Conj.Gradients N3/2N1/2 *log N N N°Red/Black SOR N3/2N1/2N N°Sparse LU N3/2 (N2) N1/2N*log N (N4/3) 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 communicationReference: James Demmel, Applied Numerical Linear Algebra, SIAM, 1997.03/14/05 CS267 Lecture 15Multigrid 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•Take at least n steps to move information across n x n grid°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 step03/14/05 CS267 Lecture 15Multigrid Motivation03/14/05 CS267 Lecture 15Multigrid 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 grid03/14/05 CS267 Lecture 15Same Big Idea used elsewhere°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) for computing gravitational forces on n particles in O(n log n) time:•Approximate particles in box by total mass, center of gravity•Good enough for distant particles; for close ones, divide box recursively°All examples depend on coarse approximation being accurate enough (at least if we are far enough away)03/14/05 CS267 Lecture 15Multigrid 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)03/14/05 CS267 Lecture 15Multigrid Sketch in 1D°Consider a 2m+1 grid in 1D for simplicity°Let 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 sequence of problems from finest to coarsest03/14/05 CS267 Lecture 15Multigrid 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 coarsest03/14/05 CS267 Lecture 15Multigrid Operators°For problem P(i) :•b(i) is the RHS and •x(i) is the current estimated solution °All the following operators just average values on neighboring grid points (so information moves fast on coarse grids)°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) •Uses sampling or averaging•b(i-1)= R(i) (b(i))°The interpolation operator In(i-1) maps approx. solution x(i-1) to 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 improves solution x(i) •Uses “weighted” Jacobi or SOR on single level of grid•x improved (i) = S(i) (b(i), x(i))°Overall algorithm, then details of


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?