### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Topics in Applied Mathematics APPM 7400

GPA 3.76

### View Full Document

## 34

## 0

## Popular in Course

## Popular in Applied Math

This 15 page Class Notes was uploaded by Dr. Filomena Hegmann on Thursday October 29, 2015. The Class Notes belongs to APPM 7400 at University of Colorado at Boulder taught by Staff in Fall. Since its upload, it has received 34 views. For similar materials see /class/231872/appm-7400-university-of-colorado-at-boulder in Applied Math at University of Colorado at Boulder.

## Reviews for Topics in Applied Mathematics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

APPM 7400 Topics in Applied MaTh SecTion 001 MulTigrid MeThods ScoTT MacLachlan Grandview 100 303 735 3752 maclachlcoloradoedu hTTpamaTlIcoloradoedufacuITymaclachl Office hours TBA CUrBuulder lumz APPM 7400001 Syllabus Coursework No exams Homework exercises 6i compuTing assignmenTs ProjecT 6i presenTaTionjoinT is OK Can Tailor some or all work 5 IaTer IecTures To your inTeresTs Philasaphy Big on fundamentals principles 5 simple ideas Think abouT The scienTific meThod in general UndersTand by concreTe examples 5 experience Know The whole picTure Ask quesTions 6i inTerjecT commenTs Make sure I explain whaT you need TexT A MuITigrid TuToriaI 2quotd ediTion 2quotd prinTing SupplemenTaI maTeriaI as needed CUrBuulder Zurziz Sources MGNeT NewsleTTer hTTpwwwmgneTarg SofTware reposiTory MaThSciNeT Many papers now available elecTronically Copper MounTain Conference April 3 Apri 8 2005 We hope To supporT your aTTendance hTTpwwwamsargmaThscineT Course web site I J CUrBuulder 3mm Homework exercises Due 1 week afTer The relevanf chapfer is covered 1 34 6 126 2 1 3 8 101316 7 12710 12 15 21 3 2 6 8 2 6 8 4 6 711 9 1 3 5 1 3 1213 10 1 3 5 8 9 CUrBuulder 4am Computing assignments Due 2 weeks after the relevant chapter is covered Start your assignments early multigrid algorithms can be tricky to code Use whatever computing languageplatform you like 2 20 4 13 15 6 6 by computer 7 Convert your 2 D code developed for Chapter CUBoulder 4 standard coarsening amp point relaxation to solve 714 Verify the code using a 1 Test its performance using 3 1215 110 2 5 10 Interpret your results 5 0f312 Project amp presentation Due at the end of the semester Project definition is intentionally vague Think about what has captured your attention See me but only after you39ve thought about it Computing ampor theory ampor application ampor exploration I39d like to see a presentation 10 minutes plus a short lt5 pages writeup about what you did CUBoulder Presentation Prepare Speak to your peers not me Check course web site for suggestions 6 0f312 Successful Scientific Inquiry Attitude You can do it Be positive But is it really right Be critical Don39t hope or guess THINK Control your emotions Expect ups amp downs Method Start simply Reduce issue to the simplest possible case Take tiny steps but keep the big picture in mind Study concrete examples Look for analogies Can A be done in any way like how B was done Creativity What do you really want What end are you really aiming for What do you really need What you39re trying may be sufficient to do what you want but would an easier to prove weaker result do instead Intelligence It doesn39t hurt to try to be quotsmartquot too CUBoulder 7 0f312 A Multigrid Tutorial 2quot 39 Edition 2quot 39 Printing By William L Briggs CU Denver Van Emden Henson LLNL Steve McCormick CU Boulder e THANKS 9 THANKS CUBoulder 8 0f312 Outline Multilevel methods have been by chapter developed for 1 Model Problems 6 Nonlinear PPObleS PDEs CFD porous media elasticity electromagnetics 2 Basic Iterative Methods Pu aPPquot le quot heme Purely algebraic problems with no physical grid for 7 Selected A lications pp example network Si geodetic survey problems Neumann boundaries Convergence tests AnalySis A 39 39 bl I a e reconstruction amp to o ra h 3 Elements of Multigrid an olrI oplc pr ems m 9 m 9 p y39 Relaxa on m 5 ms 55 Optimization eg the Traveling salesman Si long Variable coefficients 1 1 1 bl coarsening 8 Algebraic Multigrid AMG ranspor 0 Ion pro ems 4 Implementation Matrix coarsening Statistical mechanics Ising spin models C mPl5x Y 9 Multilevel Adaptive Methods 39 Quantum chromo dynamics D39agnosms Quadrature Si generalized FFTs 5 Some Theory 10 Finite Elements Spectral vs algebraic Variational methodology Integral equations CUBoulder 9 0f312 CUBoulder 11 of312 Suggested reading Everyone uses multilevel methods CHECK THE MG LIBRARY amp MGNET REPOSITORY Multigrid multilevel multiscale multiphysics A Brandt Multilevel Adaptive Solutions to Boundary Value Problemsquot U I I II I II h I I Mam Compw31I1977IPP 333390 se oca governing ru es on t e finest eve to A Brandt Multigrid techniques 1984 guide with applications to resalve lhe slale of The Syslem al lhese delalled computational fluid dynamicsquot GMD 1934 scales butrecognizing that these quotrulesquot have w Hackbusch MultiGrid Methods 5 Applicationsquot Springer 1985 broader implications that are hard to determine W Hackbusch amp U Trottenberg Multigrid Methodsquot SpringerVerlag l39her39equotUSC COGF SCY leVelS 1390 FCSOlVC larger SCOlCS 1982 Continual feedback is essential because improving 5 McCormick ed Multigrid Methodsquot SIAM Frontiers in Applied one scale impacts other scales Math III 1987 U Trottenberg C Oosterlee amp A SchLiller Multigridquot Academic Press 2000 Sight art politics thinking scientific research P Wesseling An Introduction to Multigrid Methodsquot Wylie 1992 cookmgI team sporttsI Common uses CUBoulder 10 of312 CUBoulder 12 of312 1 Model problems 1D boundary value problem uquotx mum fx u0 u1 0 0ltxlt1 020 39 Grid 1 26 ih 39 NH L l 01 N1 x 0 x 1 I I I I I I I I I I I I I I I I I I I x0 X1 x2 xi xN1 Letvl z uxl ampffx for i01N1 This discretizes the variables but what about the equations CUBoulder 13 0f312 Approximate Ll39x via Taylor series Approximate 2391d derivative using Taylor series 0 h2 h3 uxi1 uxI hu39 1 3u xi gu h2 ux1 ux u39x Eu xi Summingampsolving ux 2ux ux urxi CUBoulder 14 0f312 Approximate equation via finite differences Approximate the BVP uquotx mum fx u0 u1 0 0ltxlt1 020 by a finite difference scheme 39vi 12vi39vi1 hz 0 fi 139 12 N CUBoulder 15 0f312 Discrete model problem Letting v 121122 VNTamp f f13f23 3fNT we obtain the matrix equation AV 7 where A is Nx N symmetric positive definite Si 2 0W 1 W v f1 1 2ahZ 1 2 v2 f2 1 1 2Uh l V f 47 1 V E f 3 2 L 1 2Uh 1ZJ vm fr 1 2Uh v f CUBoulder 16 0f312 Stencil notation A121 dropping h392 amp o for convenience 2 o 391 0 1 CUBoulder Basnc solution methods Direct Gaussian elimination Factorization Fast Poisson solvers FFT based reduction based Iterative Richardson Jacobi Gauss Seidel Steepest Descent Conjugate Gradients Incomplete Factorization Notes This simple 1 D problem can be solved efficiently in many ways Pretend it can39t amp that it39s very hard because it shares many characteristics with some very hard problems If we keep things as simple as possible by studying this model we39ve got a chance to really understand what39s going on CUBoulder But to keep our feet on the ground let39s go to 2 D anyway 2D model problem Consider the problem uxx uyy0ufxy 0ltxlt1 0ltylt1 110 when x0 x1 y0 ory1 020 Consider the grid Z 1 1 h L1 M1 xj yj 0 si s Lt 0 S sMI 17 of312 CUBoulder x 19 0f312 Discretizing the 2D problem 39 Lei Vij uxiayj Si f fxyj Again using 2 order finite differences to approximate uxx Si uyy we arrive at the approximate equation for the unknown uxyj for 212 L ampj12 M Vi 1j2quotij i1j Vij 12Vij ij1 2 2 Vij fij h hy v0 i0 iL1 j0 jM1 Ordering the unknowns amp also the vector 7 lexicographically by yIines T v Vll v12quot 39 v1M v2l v22quot 39 VIM 39 VL1 VL2quot 39 VLM 18 of312 CUBoulder 20 0f312 Resulting linear system We ob rain a blockTridiagonal sys rem AV 7 81 MHH l y A3 V3 f3 39 Iy Iy AMA Iy Viv71 fMil Iy AM VM 1 fM where Iy is a diagonal ma rrix wi rh h Z on The diagonal Si y 33 i hf hf hf 1 2 2 1 7 73373 73 L 11 hz hf hf A 1 7W 1 2 1 U7 77 37 i 0 CUBoulder hf hf hf Zlof312 STencnls preferred for grid issues S rencils are much be r rer for showing The grid pic rure again dropping h392 amp 0 O 1 O 0 0 r2 y 3 1 1 2 1 72 72 72 4 x y x 0 1 0 o 4 o S rencils show local rela rionshipsugrid poin r in rerac rions CUBoulder 22 0f312 Model Problems CUBoulder Outline Chapters 1 5 Chapters 6 10 Nonlinear Problems Basic Iterative Methods Full approxima rion scheme Convergence TESTS Selec red Applica rions boundaries Ana39vs39s mework Elemen rs of AAng V blelc Tablems aria emes es Relaxa rion Variable coefficien rs coarsening Algebraic Mul rigrid AMG Implemema on Ma rrix coarsening comPleXlW Mul rilevel Adap rive MeThods DiagnosTics PAC Some Theory Fini re ElemenTs Spec rral vs algebraic VariaTional meThodology 23 0f312 Example of RBFs for a PDE Poisson39s equation Direct collocation Method by Kansa On Boundary u gX y 62u In Interior LU 6X2 ayz fx y n Let ult J Manx 4H y Collocation gives llt ltjlllxx g lj X L llt ltjlllxx f Key features Spectral accuracy if smooth RBFs Completely arbitrary geometry Code maybe 15 lines in Matlab if using a direct solver Numerical tests for Poisson39s eguation Larsson and Fornberg 2003 2 may in interior The RHS functions are chosen so 6X2 ayz th t L U 900 0 boundary a X y100X 0222y2 Direct RBF collocation Pseudosgectral PS Finite differences FD2 Test with different Fourier angularly Centered FD2 in both W and s Chebyshev radially directions In all cases 48 nodes n the interior 16 nodes on the boundary Comparison between RBF PS and FD2 approximations RBF approximations Gaussians GA r e l 2 Inverse quadratics IQ r 11 sr2 Multiquadrics MQ r l1sr2 mm Using direct computation Using ContourPade algorithm 0 10 100 1o 5 75 g E10 L LE 10 10 1o 10 10 10 10 10 10 101 E s For FD2 in 2D Error is inversely proportional to number of points 2 RBF with 64 points similar accuracy to FD2 with 64 10 6 points Convective flow over a sphere Flyer and Wright 2007 Governing PDE au atcosoc tanr951ngps1naa cosgpsmaag O I RBF collocation of PDE in spherical coordinates eliminates all coordinatebased singularities Spectrally accurate numerical methodologies DF Double Fourier series l l l W ll RBF Radial Basis Functions 1 If I r quotif Hf I I W I D 139 1 I I I i i I I quotI I I 1 32 Elf 39 39 39 a 39 39 39 5 quot 39 v q 39 39 E 17 I14 3quot I I v a I t w 39 A v i F My 0 393939393939393939 U 7 5 i 0 39 39 1 2 r 2195 a Hm F It u qr 3331 SE Spectral Elements 4 1 z 3 3 g 351 Implemented by means of cubed sphere 41E U 1 E f I I t i 4 Eff 3 5 iquot n E I is I n 39 39l l E In D E l SPH Spherical Harmonics Collocation with orthogonal set of triglike basis functions which lead to entirely uniform resolution over surface of sphere Convective flow over a sphere Comparison between methods Snapshot of 4096 node RBF calculation after Relative error in parts per thousand one full revolution 12 days ofa cosine bell In order to obtain a relative error of about 0006 the requirements ofthe different methods are Method Number of node points Time step Code length Local refinement free parameters RK4 lines feasible RBF Radial basis functions 4096 12 hour lt 40 yes SPH Spherical harmonics 32768 90 seconds gt 500 no DF Double Fourier 32768 90 seconds gt 100 no SE Spectral elements 7776 6 minutes gt 1000 yes Long time integration of convective flow over a sphere Fornberg and Piret 2007 39Unrolled39 spherical coordinate system Initial condition Cosine bell discretized at n 1849 39minimal energy39 nodes 10 E e as TPS a 101 239 6 f a e l GA w 1 MG 10 3 l l I I 039 2000 4000 6000 8000 10000 t Evolution of numerical error as time increases One full rotation corresponds to 1 27 For best longterm accuracy we need to use small a and the RBFQR algorithm APPM 7400 RADIAL BASIS FUNCTIONS Pseudospectral PS methods Approx 16 lectures Introduction to Finite Differences FD Lagrange s amp Newton39s interpolation formulas Elementary error estimates and illustrations of the Runge phenomenon Elementary ways to generate nite difference FD stencils Pade approximations Pade method for FD formulas Nonequispaced FD weights algorithm FD stencils in 2D FD limits Differentiation matrices DMs Fourier transform series FFT Relations between different types of Fourier transforms series Gibbs39 phenomenon Convolution theorem Applications of the DFT FFT algorithm via sparse matrix factorization 2D Fourier transform rotation property PS in periodic cases PS DM equivalence to FD limit of increasing order PS in non periodic cases Runge phenomenon theory Lebesque constants Jacobi and Chebyshev polynomials Key properties of PS methods Convergence in nonperiodic periodic and nonsmooth cases DM eigenvalues Time stepping and stability considerations ODE methods and stability concepts root condition stability domain etc von Neumann analysis PS variations and enhancements Staggered grids preconditioning Polar and spherical coordinates double Fourier method spherical harmonics PS methods and timespace domain comer singularities Fictitious points for ODE boundary value problems and for highorder IBV problems Some applications Nonlinear waves numerical uid mechanics turbulence etc Radial basis functions RBFs Approx 27 lectures Introductions to RBFs Introduction of RBFs Via failure of xed basis function sets Nonsingularity results for different types of radial functions Micchelli s theorem Different types of radial functions nonsmooth VS smooth global vs compact Introduction to RBFs Via cubic splines Cubic splines end conditions Matlab RBF demo code Shape parameter issues Determinant formula for the REF interpolant Various shape parameter 8 gt 0 results ill conditioning ContourPadeSVD algorithms RBFQR algorithm on a sphere and in 2D spherical harmonics Besseltype radial functions Gibbs and Runge phenomenon issues Boundary effects and boundary conditions for RBF approximations Runge phenomenon for RBF interpolants Gibbs phenomenon for RBF interpolants Spatially variable 8 opportunities RBFs for PDEs Collocation with RBFs RBFs for elliptic PDEs 1D and 2D equispaced lattice cases infinite interval and periodic results some closedform expressions Periodic implementations circlesphere time stepping stability theorem RBFs for wavetype equations RBFs together with least squares RBF with domain decomposition RBF implementation of special operators Laplacian gradient diV etc RBF applications in geophysics the Williamson eta1 test cases Some additional topics Fast numerical algorithms eg BFGP Krylov fast multipole methods Some possible topics for study presentations PS Methods 1 Describe PS for BV problems 2 Implement and compare FD2 FD4 and PS for a simple wave equation 3 Plot some cases of the Runge phenomenon Compare against analytical result 4 Read and describe Richardson39s classic 1910 paper 5 Survey references on PS for unbounded domains 6 Find and describe some key PS calculations in uid mechanics 7 Implement and do further explorations based on various Matlab codes in quotSpectral Methods in RBFs bP N Matlabquot Describe the Micchelli s theorem and its background Describe some RBF applications Search for good RBF point distributions Via optimization compare lD and 2D Explore some of the fast RBF algorithms

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.