New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Special Topics

by: Alayna Veum
Alayna Veum

GPA 3.81


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 4803 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/234146/cs-4803-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

Similar to CS 4803 at

Popular in ComputerScienence


Reviews for Special Topics


Report this Material


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: 11/02/15
Introduction to Modeling and Simulation Particle methods Cont d Introduction to Monte Carlo Methods Outline I Wrap up particle methods Hardsphere interactions Limitations of particle methods I Brief review of randomnumber generation I Numerical integration by quadrature rules I Integration using MonteCarlo methods Review of Particle Simulations I Molecular dynamics has many applications I Many problems are concerned with interaction forces among particles which take most of computational time I Improve efficiency using cutoff radius and periodic boundary condition I Use statistics to obtain mean pressure or temperature HardSphere Interactions o I A simplified potential cgto r30 u r O r gt Oquot I Interaction only at collisions at other times motion is near I Event driven simulation each collision is event I To speed up detection of collisions one can use cells to or other data structures to accelerate I Reference H Sigurgeirsson A Stuart WL Wan Algorithms for particlefield simulations with collisions Journal of Computational Physics 172 766 807 2001 1 Limitations of Molecular Dynamics I Use of classical forces Only approximations to true physics have limited accuracy especially for very light systems I Time and size limitations Require small time steps can simulate up to a few picoseconds to hundreds of nanoseconds Interesting phenomena often may require much longer simulations Monte Carlo Method I Monte Carlo methods are stochastic and are typically simple to implement I MC is often used to solve stochastic problems to mimic randomness of physical behavior Example 1 Random walk or drunkard s walk I Walk toward different directions randomly with uniform distribution I Make n steps with length d each what is expected final distance from starting point I Solved by Einstein in 1905 I Related Markov chain Monte Carlo simulations Example 2 Find rootmeansquare rms path length for n steps while not crossing itself I Applications in polymer physics I Cannot only be solved numerically I MC can also be used to solve deterministic problems by usmg probability for estImatIon Example Evaluation of n highdimensional integration Requirements of Stochastic Simulations I Knowledge of relevant probability distributions Knowledge of relevant probability distributions depends on theoretical or empirical information about physical system being simulated I Supply of random numbers for making random choices By simulating large number of trials probability distribution of overall results can be approximated with accuracy attained depending on number of trials JIIII Random Number Generation Review I Actually pseudorandom numbers Random patterns long period repeatability I Lehman s algorithm gX a X mod m with proper choice of a and m A special case of congruential generator I gX aX c modm I Nonuniform distribution Use uniform random number generator and invert distribution function Example normal distribution ftle I Take xk log1 yk1 where ykis uniform tgt0 Evaluation of it I Monte Carlo calculation ofn I Evaluation of area is essentially a simple integration of 1 jde I What about more general definite integration problem jfrdr I Integration is viewed geometrically as evaluation of area OneDimensional Integration The problem evaluate integration of function fx For function f definite integral over interval a b is defined by limit of Riemann sums I Evaluation of onedimensional integral W la malt can be viewed as solution to differential equation M fx where fa 0 dx Numerical integration of function and solution of differential equations are intimately related Lowerorder methods are equivalent eg trapezoid rule midpoint rule but highorder methods are in general different 10 Numerical Integration of Quadrature Rule I Quadrature rule is weighted sum of finite number of sample values of integrand function I An npoint quadrature rule has form Qnfwfx Points xi are called nodes or abscissas 1 Multipliers wi are called weights How should sample points be chosen How should their contributions be weighted I Quadrature rules are based on polynomial interpolation Examples Simpson s rule Guassian quadrature Numerical Quadrature I Evaluate integration over interval X0X1 1 39 S39mpSO S Ru39e39F gifltxogt4fltxlizgtfltx1 gt1Ax 3rdorder integrating quadratic functions exactly I Gaussian quadrature Example 4thorder 1 fxdx z f13 M173 6thorder f1 fxclx s f J35f0fJ3 5 12 HighDimensional Integration I For higherdimensions take Cartesian product of quadrature points and product of weights I If each dimension uses p points then d dimensions would require pd points I If d is large the number of points is huge I Can we do better Monte Carlo Integration I One simple way is hitandmiss approach for area calculation I Another way is based on meanvalue lffltxgtdx b agtf where f denote average value of integrand f I Simple mean method F nab mig xi where X are chosen randomly I Works exactly the same in higher dimensions and for complex domains Error Analysis of Monte Carlo I Variance 62 is 02 ltf2gt f and standard deviation is o I It can be shown that standard error of means is given by 0 2 o z i m n l J I cm is a probably error meaning there is 68 of chance for Fn to be within cm and 97 of chance to be within 26m I Error decreases if n increases or 6 decreases 6 depends on probability distribution I Comparison with Quadrature Rules I For Monte Carlo errors converge at rate On12 I This seems inferior in 1D as trapezoid rule converge as rate On2 and Simpon s rule converge at rate On3 I Given n points when using quadrature rules with error rra in 1D then in dD the error is nad I So for higherdimensional integration Monte Carlo method is more effective troduction to odeling and mulation Applications and Types for Physicsbased Models Outline I Why use continuous modeling I Types of continuous modeling I Processes of continuous modeling I An example problem I Brief review of numerical differentiation ContinuousTime vs Discrete TIme Dynamic Models I Discretetime models may change their values only at discrete times in time 2 Many formulated by difference equations I Continuoustime models evolve their variable values continuously over time 2 Many formulated by differential equations algebraic equations I Some systems may be combination of two Time Why Study Continuous Modeling I In engineering and science a Eg fluid dynamic aerodynamics blood flow etc Structural mechanics building machines I In computer scientists Computer graphics computer vision animation Computer games Geometric computing and image processing 1 Analytical and Numerical Solutions I Analytical problems are best are solving linear problems 39 Eg solving Newton s second law of motion I Many physical problems are nonlinear so must resort to numerical solutions I Nevertheless analytical solutions are often valuable Why Verification of numerical solutions Gaining insights I Examples where analytical solutions do not work Threebody problem 39 Types of Simulations I Particle simulations I Monte Carlo Simulations I Continuum physics Finitedifference Finiteelement I Hybrid simulations 1 Particle Methods Bodies are simulated as point mass Particles interact with each other Numbers of particles may be small eg solar system 10 or large molecular dynamics 103107 galaxies 1011 or plasma Systems 1024 molecular dynamics It can be challenging to simulate interaction of large number of particles El Use of super particles to reduce amount of particles El Particle in cell PIC method to reduce interactions in Periodic structures to reduce domain size galaxy 39 Monte Carlo Method I Monte Carlo methods are stochastic and are typically simple to implement I MC is often used to solve stochastic problems to mimic randomness of physical behavior rquot Example 1 Random walk or drunkard39s walk I Walk toward different directions randomly with uniform distribution I Make n steps with length deach what is expected final distance from starting potnt I Solved by EinsteinDin 1905 I Related Markov chain Monte Carlo simulations r Example 2 Find rootmeansquare rms path length for n steps while not crossing itself I Applications in polymer physics I Cannot only be solved numerically I MC can also be used to solve deterministic problems by using probability for estimation Example Evaluation of TE highdimensional integration I l Continuum Physics Using FiniteDifferent Method Simulate continuous variations of physical39 properties such as temperature density 2 etc in space or time using PDEs a 7 Some may be solved using particle methods but finite difference method may be more efficient Formulation values are represented at grid points often with known boundary values and partial derivatives are approximated by linear combinations of gridpoint values I Often resulting in linear system of equations l Problems often involve diffusion processes wave motion or steadystate problems A cousin finitevolume method often used in CFD J Continuous Physics Using FiniteElement Method I Alternative to finitedifference methods I Especially for problems with complex boundary where domain is discretized by meshes I Method determines values at nodes I Traditionally used in steadystate problems but also often used for diffusion or wave motion 391 Hybrid Simulations I Combination of different types I Combination of particles and Monte Carlo Brownian motion I Combination of finitedifference and particles Particle in cells I Hybrid discreteevent and continuous modeling Eg multiscale simulations a Process of Solving Continuous Problems I Modeling I Numerical solutions I Analysis of data visualization I Verification and validation Often iterative process Verification amp validation are very important aspect 2 Many sources of errors program bugs numerical errors round off and truncation errors and modeling errors Compare against analytical solution Compare against experimentation Sanity checking convergence study consistent story F Focus in This Course I We will focus on from models especially differential equations to numerical algorithms ie numerical solutions of physical models We assume physical lawsmodels are knowngiven Wellknown physics with very complex systems eg astrophysics Lessknown physics eg oil extraction Choose and implement numerical solutions efficiently 1 Example Harmonic Oscillator I If no damping or oscillator by Newton s second law of motion 2 mg FWhereF kx 7 Can be solved analytically x A coshlk mt a A and e depend on initial condition of position and velocity I In the presence of nonlinear damping and driving forces equation may not be solvable analytically eg dzx Pendulum wrth damping Jraraz 2 FWhereF kxacosmI gt and forcing Vibration I d Must solve numerically troduction to odeling and mulation Techniques for higherorder ODEs Simulation with Particles Outline I Techniques for solving higherorder ODEs General approaches for higherorder ODEs Special method for 2ndorder ODEs Solving sample problem I Simulations of particles Basic concepts and techniques 7 Examples of fewbody problems 7 Overview of manybody problems Example Harmonic Oscillator I Newton s second law of motion l I In the presence of damping and driving forces equation is 2 Ind 2x FwhereF kx acosmr g g 11 d Animation Some other problems have similar lt gt formulation eg electrical circuit X oscillations displacementcharge velocitycurrent forcevoltage drop massinductance dampingresistance How to solve it numerically Pendulum with damping and forcing vibration F HigherOrder ODEs I Order of ODE is determined by highest order derivative of solution function in ODE quot Eg Newton s second law of motion y f I y I Solving higherorder ODEs quot In general convert to system of firstorder ODEs For secondorder ODEs one could use centered difference directly eg halfstep Verlet algorithm HigherOrder ODEs Cont d I Given kth order ODE 1m y u t y39 I Define k new unknowns MN ya I Original ODE equivalent to firstorder system 1quot1 1quot2 u u3 lquot12 1 k u ftu1u2uk I So most software packages solves only first order ODEs Solving Example Problem I Forced damped oscillator 2 m FWhereF kxacosat g t t t I Defining ux and vx yields system of two firstorder ODEs u39 v v Ftuvm I Then apply techniques for 1storder ODEs v 1 v At l i Eg Forward Euler Backward Euler n1 n n1 u Atvn1 9V 7V Ft1av1av1 VH1 V A m m Fl ln matrix form forward Euler typically involves matrixvector multiplication while backward Euler involves linear or nonlinear systems i i Stability analysis is done using eigenvalue analysis of matrix 1 Another Method Halfstep method I For integrating Newton s second law of motion I Sometimes also called leapfrog method or EulerRichardson method X n1 xn hxmlZ xn32 xn12 hxml X I I I I I I I tlh V I Secondorder accurate efficient but not self starting I Stable so commonly used in textbooks 39 1 Velocity Verlet Method I Sometimes also called Verlet algorithm 1 x 1 x ngt xAt2 I I 1 1 1 A xn1 xn Exn1xn t Derivable from Taylor series and centered difference i i It is equivalent to another method that is also called Verlet method M 2x xn1 xAt2 I Stdorder accurate selfstarting less roundoff I A symplectic algorithm in that it is conservative I Velocity Verlet method is often choice of method for molecular dynamics 8 1 FewParticles Problem with InterParticle Forces I Examples Planetary motion of a planet or several planets Electron in magnetic field 2 Molecular dynamics I Objectives of particle methods 2 Study interactions interparticle force or collision to obtain physical properties i i Results are often time averaged or averaged over multiple particles especially for manybody problems I Focus on deterministic processes and consider stochastic process in Monte Carlo simulations I Considerations conservation of energy momentum and angular momentum 9 W 1 Example TwoBody Problem 39 3U Of mass M and Earth of mass m I Animation I Newton s universal law of gravitation FGMmA GMm 1 2 3 I I where G667e11 m3kg s2 is gravitational constant r is vector from Mto m I If we fix coordinate system at M equation of motion of particle m IS then mr 3 139 r where rx y and rX2y212 1 Simplification of equation Mm GMm OK since Mgtgtm 139 3 139 mM r I 10 TwoBody Problem Cont d GM WX x y GMy I I x2y232 I ThlS IS a coupled system where X and ydepend on each other I Convert to system of four firstorder ODEs and solve using your favorite method I You can now simulate Earth orbiting Sun I How to verify the accuracy of your code Sanity checking conservation of energy of momentum etc 7 Compare with analytical solutions I So we have y 11 NBody Problem I How to simulation of whole solar system l The general strategy for solving a problem w many interacting bodies where only pair interactions occur is to consider all pairs of bodies in turn In other words force on each particle must take into account all other particles ie GMm Gmm ll 1 j miri 31134 2 3 rij Vi j i ry where ris position of particle i and rij is vector from particle ito particlej M Gm I SO ri3 n2 3 3 t 9 Again reduce to 1Storder ODEs and solve using RK4 rt 12 troduotion to odeling anol mulation Monte Carlo Simulations Intro to Boundary Value Problems Outline I Markov chain method I Simulation of fluid by Monte Carlo method I Monte Carlo solution of Poisson s equation I Introduction to finitedifference method Shooting method for boundary value problems BVP Finite difference method for BVP quot1 Markov Chain Methods I A method for generatinganalyzing nonuniform distribution I Discretetime stochastic process of a series of states where each states depends on only the states immediately before it I Defines through a stochastic matrix P specifying probability of transition from one state to another t t Adjacency matrix of weighted directed graph i Probabilities of states after a large number of transitions 39i Each column must sum up to 1 and every entry is nonnegative i i Eigenvector corresponding to largest eigenvalue gives probability distribution M Eg 12 13 Whose eigenvector is O406 12 23 I There are large number of applications in simulations eg queueing theory statistical mechanics and mathematics eg PageRank of Google 1 Application in Statistical Mechanics Probability of arrangement Pa with total potential energy CD is proportional to expCIgtkt 39 kis Boltzmann constant 1 38O7x1023 jouleK 39 Tis absolute temperature 39 Socalled Boltzmann distribution If some quantity 0 eg energy is associated with some arrangement a then average of Q for all possible arrangements would be Q ZaQaPa 20 Q0 eXp CIgta kT Zaexp CIgta kT Evaluating this is challenging because CI can be very large so Pa can be extremely small 39 MetropolisHastings Algorithm l Generate succession of configurations such that each configuration has desired probability quot Discovered by N Metropolis in 1953 for Boltzmann distribution quot Generalized by WK Hastings in 1970 for more general distributions Outline of Metropolis Algorithm 1 2 Generate initial configuration can be uniform distribution Select particle randomly in uniform distribution select direction randomly and move particle for a distance 8 randomly chosen between 0 and a fraction eg 005x of average distance between particles Calculate new potential CD and change of potential AcIgtcIgt CIgt lf ACID is negative then new configuration is accepted as a potential configuration and return to step 2 to find next configuration If ACID is positive then compare expAcIgtkt with a random number r 6 01 i If expACIgtktgtr accept new configuration i Otherwise reject new configuration and accept old configuration i x Return to step 2 to find next configuration Mean is averaged overall accepted potential configuration quot Monte Carlo Solution of Laplace Equation I Heat transfer problem Given temperature of boundary of domain determine temperature of interior Temperature of each point is average of its neighbors Modeled by Laplace equation I Monte Carlo method can also be used to solve this problem I Animation 1 Summary of Monte Carlo Methods I Monte Carlo methods are very simple and powerful methods with many applications I Monte Carlo integration is particularly effective in higher dimensions I Monte Carlo simulations are often used in statistical mechanics in conjunction with particle methods and in other mathematicalphysical problems using Markov chain methods Shooting Method for Boundary Value Problems I Solution of equation u ftuu39 with boundary conditions at Xa and Xb l Shooting method try a sequence of increasingly accurate guesses until we find proper u a v Solve a sequence of initial value problems Example of Shooting Method I Consider two point BVFIIfor secondorder ODE u 6t 0lttlt1 With boundary condition uO O u1 1 For each guess for u 0 integrate ODE using RK4 Li Try initial slope of u 0 1 hit u1 2 i Try initial slope of u 0 1 hit u1 0 t Next try u 0 1 hit u 1 20 7 lst attempt 15 10 e target 05 00 g 2nd attempt 705 05 10 A problem of shooting method is that a poor initial guess may lead to instability even if BVP is stable 1o 1 Finite Difference Method for BVP I Finitedifference method converts BVP into system of algebraic equations by replacing derivatives by finite difference approximations I For example to solve twopoint BVP u ftuu a lttltb With BC ua a ub 8 I Introduce mesh points ti aihfori01n1 whereh b an1 I Seek for approximate solution yut for i1n 11 F Finite Difference Method Cont d I Replace derivatives by finite difference quotients eg centered differences u ti 3 yi12hyi 1 bizti z yi122i yi l yielding system of equations yi1 2 yi l yi1 yi l t v hz 1quot 1 y 2h to be solved for y for i1 I This results to a sparse linear system 12 Introduction to Modeling and Simulation Simulation with Particles Cont d I Outline I Manybody simulations focus on molecular dynamics LennardJones potential Integration Hard disks I Calculations of interactions Cell method Superparticles Collisions Molecular Dynamics and Applications I What is molecular dynamics Computer simulation technique where time evolution of interacting atoms is followed by integrating their equations of motion I History since 1957 and still widely used for applications involving liquids solidatom systems biomolecules I Goals of molecular dynamics Ensemble average thermodynamics Realtime evolution chemistry Groundstate of complex structures materials science optimization of structures I Compared to Monte Carlo simulations molecular dynamics is deterministic but it also statistical method statistical mechanics Computational Procedure of MD I Initialization Initial positions and velocities of each particle I lnteg ration Compute all forces and determine new positions of particles I Equilibrium Let system reach equilibrium I Average Accumulate quantity of interests Basics of Molecular Dynamics I In principle systems at atomistic level obey quantum laws governed by Schrodinger s equation First principles or ab initio Very dif cult and expensive I In practice Newton s 2nd law of motion I LennardJones potential Po e ntial Funclio n gt 12 6 C7 C7 urij48 y rt Distance x Attraction pa is van der Waals potential Often a and o are used for units of energy and distance respectively I Force determined as gradient of LennardJones potential is 14 8 48s 0 1 o r 2 y 0 ry 2 rt fl Vurij Calculation of Interactions I Typically every particle interact with every other particle I Most computational time is spent on calculating interactions in any MD program Given 17 particles interaction is up to nn12 I Potential cutoff shortrange potential Use cutoff criterion set to zero after cutoff distance rC eg 256 or 326 Must check whether distance is greater than rC 1 Efficient Implementation of Cutoff I Use cells method or other spatial data structures to speed up checking use distance among cells as upperbound of distance I Alternatively one can use neighborlist method each particle maintain list of particles with rCAr where Ar provides safe zone assuming particles move slowly I Calculation of Interactions Cont d I Cutoff criteria may lead to errors Discontinuities of potential at cutoff resolved by shifting potential du ur rrc 2 dr 0 4 rlt4 a 0 rzn Approximate interactions with faraway particles can be treated as uniform continuum beyond RC Such corrections are unnecessary for periodic BC I Note that similar techniques also applicable to astrophysics where force is gravitational and can be calculated more accurately Periodic Boundary Conditions I At microscopic level often huge number of particles eg 1023 I Smaller number of particles can give reasonable approximate qualitatively but boundary effect becomes more important I To reduce number of particles and reduce surface effect Use virtual box for interactions Tile up boxes in all directions lt Particle leaving from a boundary enter from opposite boundary Distance in force calculation i O must also be adjusted consider quot r a 39 closest images of particles Note In implementation only store one copy of particles Velocity Verlet Method I Sometimes also called Verlet algorithm er1 xquot xAt xAt2 1 xn1xn3xnlxnAt Derivable from Taylor series and centered difference It is equivalent to another method that is also called Verlet method x 1 2xquot xquot1 xAt2 I 3rdorder accurate selfstarting less roundoff I A symplectic algorithm it conserves energy I Velocity Verlet method is almost the universal choice of method for molecular dynamics Initialization and Equilibrium I Initialization Positions are often defined on a Lattice Initial velocities are from some MaxwellBoltzmann distribution at certain temperature T NUMBER OF MOIJECULES SPEED Note Initial conditions are randomized but computations are deterministic initial condition needs often adjustment to ensure center of mass is at rest I Equilibrium check timeaveraged quantities eg temperature pressure meansquare displacements remain unchanged


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Bentley McCaw University of Florida

"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!"

Parker Thompson 500 Startups

"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."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.