Berkeley COMPSCI C267 - Solving Linear Systems Arising from PDEs Using Multigrid (40 pages)

Previewing pages 1, 2, 3, 19, 20, 38, 39, 40 of 40 page document View the full content.
View Full Document

Solving Linear Systems Arising from PDEs Using Multigrid



Previewing pages 1, 2, 3, 19, 20, 38, 39, 40 of actual document.

View the full content.
View Full Document
View Full Document

Solving Linear Systems Arising from PDEs Using Multigrid

87 views

Lecture Notes


Pages:
40
School:
University of California, Berkeley
Course:
Compsci C267 - Applications of Parallel Computers
Applications of Parallel Computers Documents

Unformatted text preview:

CS 267 Applications of Parallel Computers Solving Linear Systems Arising from PDEs Using Multigrid Katherine Yelick www cs berkeley edu yelick cs267 4 12 2004 CS267 Lectures 19 1 Where Was I Last Week Whirlwind tour of Japanese Supercomputing Computer facilities The Earth Simulator 40 Tflops A Supercluster of PCs 11 Tflops Three government agencies MEXT CSTP METI Universities and Research Labs University of Tokyo University to Tsukuba RIST AIST Vendors NEC Hitachi Fujitsu Sony 4 12 2004 CS267 Lectures 19 2 Review of Earlier Lecture on Solving PDEs Review Poisson equation Overview of Methods for Poisson Equation Jacobi s method Red Black SOR method Reduce to sparse matrix vector multiply Need them to understand Multigrid Conjugate Gradients FFT Today Multigrid 4 12 2004 CS267 Lectures 19 3 2D Poisson s equation 2u x2 2u y2 f x y The the matrix T for a regular mesh is 4 1 1 4 1 1 4 1 T Graph and stencil 1 1 1 1 1 4 1 1 4 1 1 4 1 1 1 1 1 1 1 1 1 4 1 4 1 1 4 1 1 4 3D is analogous 4 12 2004 CS267 Lectures 19 4 Algorithms for 2D Poisson with N Unknowns Algorithm Serial PRAM Memory Procs Dense LU N3 N N2 N2 Band LU N2 N N3 2 N Jacobi N2 N N N Explicit Inv N2 log N N2 N2 Conj Grad N 3 2 N 1 2 log N N N RB SOR N 3 2 N 1 2 N N Sparse LU N 3 2 N 1 2 N log N N FFT N log N log N N N Multigrid N log2 N N N log N N Lower bound N PRAM is an idealized parallel model with zero cost communication 4 12 2004 CS267 Lectures 19 5 Multigrid Motivation The FFT is O log N but has an O N transpose that prevents scaling Recall that Jacobi SOR CG or any other sparsematrix vector multiply based algorithm can only move information one grid call at a time Takes N1 2 steps to get information across grid Can show that decreasing error by fixed factor c 1 takes log n steps Convergence to fixed error 1 takes log n steps SOR and CG take N1 2 steps Therefore converging in O 1 steps requires moving information across grid faster than to one neighboring grid cell per step 4 12 2004 CS267 Lectures 19 6



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Solving Linear Systems Arising from PDEs Using Multigrid 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 Using Multigrid 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?