Lecture 19Course Summary So FarRemaining TopicsThe Heat Equation in 1-D1-D Diffusion EquationDiffusionDiagram of Diffusion ModelRough Derivation of Fickian DiffusionSlide 92-D DiffusionFirst: Taylor’s Theorem with Cauchy RemainderApproximation of the Second DerivativescontApproximate Formula For Second x-derivativeThe Separate PartsTwo Discrete SchemesIndex NotationTime SteppingBoundary ConditionsSummaryImplementationSlide 22Slide 23Example Matlab CodeJacobi IteratorSolvingLecture 19MA471 Fall 2003Course Summary So Far1) Writing a serial card playing game.2) Using MPI to convert the card playing game to run on multiple processors:•Blocking point to point communication•Non-blocking p2p.•Global communication.3) 1-dimensional finite volume scheme for a basic:•Serial implementation.•Parallel implementation.•Profiling the parallel code with upshot.•Trouble shooting bottlenecks (i.e. delaying global error reduction).4) 2-dimensional finite volume scheme introduced.5) Bandwidth reduction (example algorithm Cuthill-McKee).6) Load balancing with Karypis’ Metis software.7) Introduction to solving simple electrical circuit problems.•Using “direct” factorization methods (LU or Cholesky)•Practical limit for solving on a serial computer.•Using “iterative” solution methods (Jacobi, Gauss-Seidel, Conjugate-Gradient)•Practical issues relating to parallel implementation.•Using a sparse matrix methods with iterative methods.•Sufficient conditions for the Jacobi method to converge.•An approach for distributed storage and action of a sparse matrix on a parallel computer.Remaining Topics•We will discuss some simple finite difference methods for the heat equation.•We may also cover details of spectral methods.•Multigrid.•Projects.The Heat Equation in 1-D•Examples of diffusion?1-D Diffusion Equation•We consider the motion of a tracer solute in a fluid with zero mean velocity.•We will denote the concentration of the tracer by C(x,t)•The tracer will diffuse by random particle motion.•The diffusion equation is:22C CDt x� �=� �Diffusion•An underlying assumption of diffusion equation is that mechanical dispersion, like molecular diffusion, can be described by Fick’s first law:•where F is the mass flux of solute per unit area per unit time and D is the effective diffusion coefficient in a porous medium. •Fick.s law states that particle flux is directly proportional to the spatial concentration gradient. But it is not the spatial concentration gradient that causes particle movement, i.e. particles do not .push. each other (Crank, 1976). •Particles exhibit random motion on the molecular level. This random motion ensures that a tracer will diffuse, decreasing the concentration gradient (Crank, 1976). •Crank, J., 1976. The Mathematics of Diffusion. Oxford University Press, New York.CF Dx�=-�Diagram of Diffusion Modelabbb d+b d-Assume that each particle is jumping with a rate of R(delta) jumps per second which take it a distance of delta or more then there will be anumber of jumps out of the left delta width~= -R(delta)*0.5*delta*(C(b) + C(b-delta))We count the number of jumps in from the right delta width~= +R(delta)*0.5*delta*(C(b+delta)+C(b))Summing:( )( ) ( )( )2Rflux C b C bd dd d@ + - -Rough Derivation of Fickian Diffusion•Consider the x=b end of the section. We are going to “monitor” the random motions of a particle in and out of the region:•Assume that each particle is jumping with a rate of R jumps per second then there will be a flux of out of the b end (similar at the a end)•We apply tracer counting:( ) ( ) ( ) ( )2 2, , , ,2 2baC b t C b t C a t C a tdCdx R Rdtd d d dd dd d� � � �+ - - + - -= -� � � �� � � ��[ ],b bd d- +( )( ) ( )( )2Rflux C b C bd dd d@ + - -( ) ( )2222, ,babaC C Cdx R b t a tt x xCR dxxdd� � �� �@ -� �� � �� ��@���We now recall that R is a function of delta and clearly R must be inversely proportional to delta. i.e. as the region we are monitoring shrinks to zero, the rate of random motions into and out of the control region increases…We denote and obtain:22C CDt x� �=� �20limD Rdd�=[ Note continuity assumptions ]2-D Diffusion•We can follow the same line of reasoning to obtain the 2-D diffusion equation:•We are now going to create a very basic finite difference numerical scheme which we will use to solve this equation:2 22 2C C CDt x y� �� � �= +� �� � �� �First: Taylor’s Theorem with Cauchy Remainder( )( ) ( )( )[ ]2 2* *2, ,, , , , , , for some ,2!C t dt x yC dt CC t x y dt t x y t x y t t t dtt t+� �= + + � +� �i.e. ( )( ) ( )( ), , , ,, ,C t dt x y C t x yCt x y O dtt dt+ -�= +�Approximation of the Second Derivatives( ) ( ) ( ) ( ) ( )( )[ ]2 2 3 32 34 4* *4, , , , , , , , , , ...2! 3!, , for some x ,4!C dx C dx CC t x dx y C t x y dx t x y t x y t x yx x xdx Ct x y x x dxx� � �+ = + + + +� � ��� +�We use Taylor’s theorem twice:( ) ( ) ( ) ( ) ( )( )[ ]2 2 3 32 34 4* *4, , , , , , , , , , ...2! 3!, , for some x ,4!C dx C dx CC t x dx y C t x y dx t x y t x y t x yx x xdx Ct x y x x dxx� � �- = - + - +� � ��� +�cont•We add those two approximations together:( ) ( ) ( ) ( ) ( )( )( ) ( ) ( ) ( ) ( )( )( ) ( ) ( ) ( )( )2 2 3 342 32 2 3 342 322 42, , , , , , , , , ,2! 3!, , , , , , , , , ,2! 3!, , , , 2 , , , ,C dx C dx CC t x dx y C t x y dx t x y t x y t x y O dxx x xC dx C dx CC t x dx y C t x y dx t x y t x y t x y O dxx x xCC t x dx y C t x dx y C t x y dx t x y O dxx� � �+ = + + + +� � �� � �- = - + - +� � ���+ + - = + +�Approximate Formula For Second x-derivative( ) ( ) ( ) ( )( )22 42, , , , 2 , , , ,CC t x dx y C t x dx y C t x y dx t x y O dxx�+ + - = + +�( ) ( ) ( ) ( )( )( )222 21, , , , 2 , , , ,Ct x y C t x dx y C t x y C t x dx y O dxx dx�= + - + - +�Similarly:( ) ( ) ( ) ( )( )( )222 21, , , , 2 , , , ,Ct x y C t x y dy C t x y C t x y dy O dyy dy�= + - + - +�The Separate Parts( )( ) ( )( ), , , ,, ,C t dt …