Chapter 8.3 - Advanced Time Stepping Algorithms

0:08 We're going to talk now about more advanced time stepping schemes and algorithms. So what we've learned so far are simple things like mungakuta schemes, Adam bashforth, Adams molten and we can see that most of it just comes down to thinking about the differential equation in ways we're going to either approximate the derivative or the integral and then building a time stepper out of it. We also showed that depending upon your stepper, you can get very different accuracy and stability properties. And so part of what we're after is not just some generic scheme because what we're finding is that in general, a generic scheme might not work across the board.

0:43 What you really need to do is exploit structure and exploit some of the mathematical underpinnings of a differential equation that allow you to get stability and accuracy both together into this. So we're going to talk here about some advanced timing stepping schemes that allow us to do this. so the first thing we want to do is you know really just take advantage of the mathematical structure that's there. And I'm going to show you one method that does it but also we want to start understanding how to best solve differential equations and make really robust time steppers. So the first thing I'm going to talk about is what's called adaptive time stepping. And this isn't really so much about exploiting structure as it is doing something smart about taking the biggest time steps possible. Remember, part of what you're trying to do is not just, you know, a lot of these schemes will say, well, as long as you take a time step that's sufficiently small, you can make a stable scheme. But what you don't want to do is wait for hours for a computation that might take minutes, right? So there's still this interesting architecture which is how do I take the biggest step possible to solve the the problem as fast as possible. And so a lot of this is with adaptive time stepping in any of the good numerical integrators would use an adaptive time stepper. And the entire idea behind it is to basically allow you to take as big a steps as possible when you can. And if you have to take smaller steps that it will adaptively take smaller delta t's to accommodate the solutions numerical solutions that you have. So let's talk about how this might work. So the first thing is you might start off with an initial time step. In fact many of the the really good time stepping algorithms like an OD you know a fourth order one kata should have an adaptive time stepper built in. And so you're not even choosing the delta t. It's going to choose an initial time step size to pick like a a delta t knot. And the question is, is that a good choice? And it really depends on the problem you're solving.

2:47 It could be your delta t is way too small. It could be it's way too big. So what you want to do is have an adaptive sidstepper figure out what is the right delta t to be taking so I can advance the solution as fast as possible, but guarantee you a certain accuracy of your solution. So you start off with a certain delta t and what you do is that's the first step. The second step then is to take that and advance the solution and compute the solution using that delta t. Okay, so that's your base set. Whatever your initialization is, that's the delta t you're using. You compute a solution. You take a few steps forward in time and say, okay, how well did I do in taking steps forward in time? That's step one. Step two then is to say, well, maybe that delta t was too big or maybe it's too small. So, what you might do is say take that and say, I'm going to now solve the same problem over or I'm going to walk it forward a couple steps, but now I'm going to take the delta t and cut it in half. So, the delta t, let's say, was 0.01. I'm going to cut it in half to 0.005.

3:53 Okay? And ask the question, okay, what's the accuracy of that? So in other words that would be the solution f_sub_2. So I have two solutions one with a delta t one with a delt half the delta t. Okay. So if the solution is appropriately converged those should be the same. Okay. And so what we're trying to do is figure out what's how should I be taking time steps. And so what I can do is once I've done this is go ahead and compare those two solutions and look at the difference between their errors. If I'm building a numerical stepper whose error has to be smaller than 10 - 6 and if the difference between them is 10 minus 8, then it really doesn't matter which one of those steppers I would use except for the one with the delta t that's bigger is going to go twice as fast. So I should definitely use that one. And in fact, you might suggest, well, what if I take a time step of 2 delta t? And if that works well, what about four delta t? In other words, you take as big a time step as possible until the difference between your delta t and the next size delta t that that's twice as big, let's say, differs by some tolerance. Let's say 10 minus 6. That's the typical structure. It's like I'm going to take a delta t big enough so that you can't see the difference.

5:16 it's the error is on the level of 10 minus 6. And so that mean allows me to go take the largest delta t possible to solve your problem. And in cases I can solve it 10 times as fast, twice as fast, 20 times as fast. Alternatively, I might get to a point where all of a sudden I realize I have to take much smaller steps. Maybe there's a structure a rapidly changing solution and then I would want to take much smaller time steps in that region and so this would automatically then start cutting the time step in half and then half and half and half again till it's small enough to make sure that the error is 10 minus 6.

5:55 So this is kind of the the the idea is that you're looking for a tolerance difference between a time step of delta t twice the delta t half the delta t to see is there any difference? Do I have to make my time step smaller? Can I make my time step bigger? Okay. And so those are the ideas that the practical considerations that you would want to do be and you just do this over and over until you get a good time step and then you just march forward. and this is how you would do an adaptive time stepping algorithm. So, instead of you knowing ahead of time what's the right delta t, the adaptive stepper will figure it out for you and it will do a better job than you because you would actually have to go through this and keep cutting it down. But also, since the adaptive stepper is monitoring the whole time, if there comes a point at which it needs to change the time step either bigger or smaller, it just does it automatically instead of you having to manage that. So good adaptive stepping schemes are really critical in solving differential and partial differential equations. Keep that in mind. It's absolutely a really critical piece of how you would actually be efficient in your computations.

7:06 So that's step one. so this is also why maybe you could certainly write your own rung cuta stepper but really at the end of the day unless you're going to write that adaptive stepping algorithm you should really use a bulletproof you know fourth order ring cutter scheme that has an adaptive stepper built into it. So for instance, Mat Lab's OD45 is one of the really great algorithms that has been developed because it is has so many features including a great adaptive timestamping algorithm underneath it that allows you to take the biggest time steps possible to solve your your problem. Okay, so that is one thing we want to do to be efficient. A second scheme I want to show you a more advanced scheme is what are called exponential time steppers. And often what this does is get you around the issues of what are called numerical stiffness where maybe you have to take such small steps because in fact the linear term is creating a problem for you to and then so now your your time step has to be so small that you're taking a very long time solving your problem. So I want to come to this differential equation here. Notice this differential equation. Why? It's got a linear term, a nonlinear term. And in fact, if you took a course in differential equations, you'll see this as sort of in some sense one of the simplest representations of differential equations that we learned in the first few days of class typically, which is how do you solve this using integrating factor methods. So, let me show you how this works. So I'm going to take this and I'm going to we're going to actually use that analytic solution technique to help us build a much better and robust time stepping algorithm.

8:55 So here's the analytic solution in some sense for the linear part. So if I were to take this and multiply it by e to the minus ct, where do I get the e minus ct? Well, if I if I take out this this term here, that's the solution to the linear part, right? E to the minus ct is sort of what I would get. Sorry, e to the ct is the solution to this. E to minus ct is the inverse of that. So I'm going to multiply both sides by it. And I'll just show you how this unfolds. This is going to be my integrating factor. So multiply by e minus ct every term of that differential equation. Now bring this second term over to the left hand side.

9:33 The c y eus ct. I have this here. And then on the other on the right hand side I just have the f * eus ct. Now this side here is a perfect differential. In other words, it's the derivative of y e to the minus ct. So if you differentiate this, you get this term here. So the reason we did this and this is the integrating factor method we used in the first few weeks of learning differential equations is that this now is a perfect differential which means if I integrate this side, integrate both sides, this is easy to different integrate which is all I do is I integrate it. What I get is the solution y eus ct at t plus delta t minus y t e minus ct. I'm integrating now from t to t plus delta t. So just over a little time bin and then the right hand side is the integral of this thing here. So what I've done here is I'm creating a numerical scheme where essentially I've explicitly taken out the exponential behavior due to this term here. In other words, I know the analytic solution, so maybe I can just pull it out directly because otherwise it creates often times numerical stiffness issues, especially when you come to solve partial differential equations or even differential equations that have linear terms that create numerical stiffness.

10:57 So here's how you do this. So here is re-representing this thing. So this is y of t plus delta t. And what I did now, by the way, let me go back a slide. I'm going to multiply both sides by e. I'm by by this here. I'm I'm going to isolate the the solution in the future yt plus delta t by multiplying by e to the c of t plus delta t. So it's going to cancel this term out. And what it's going to leave me here is y of t e to the c delta t plus c. Okay. So I get this this combination here. y times this exponential the exponential here times this integral.

11:33 And now what I can do is basically come up with a scheme. So what the scheme says is the solution in the future is what it is now times this exponential times an approximation of this f. In fact, I'm going to go ahead and do this integral out. So this is the f of n is this approximation integral where I've essentially assume this thing to be constant. in other words, evaluate the function f at the current time point and then what's left in there is this exponential and just integrate it out.

12:05 And this is essentially an equivalent scheme to an oiler stepping scheme, right? I did the simplest approximation integral. I just took the f and approximated by the current the value at time t of n and I get this as a numerical scheme. That's how we do this. So essentially what I've done is the linear part the term that contains a C, I actually have the analytic solution already taken care of in some sense. So I already know what that term is going to do. So I've taken it out instead of making my numerical solver figure out that it's going to be e to the ct. I've already factored that out right into the into this numerical scheme. So I can just figure out what the correction is due to the f of n. You can change this around approximate this with a higher order polomial like an anom bash for scheme.

12:54 Here's your numerical stepper that you would get from that. And again, it's essentially an integrating factor method. This and it solves this exponential solving exponential stepper problem. And you can even integrate this up into a fourth order exponential runga scheme which is a little bit fancier here, but you can look this up. It's Cox and Matthew or also Kasam and Trafan show this. And by the way, this is not just some, you know, mathematical tricks and games. Look, you can do this. When you have numerically stiff problems, especially higher order derivative terms will often create a lot of numerical stiffness. So for instance where this is heavily used in system solving for instance fourth order PTEES like the kuro shivashinsky equation where this scheme here is absolutely critical for getting stable solutions quickly in fact it saves you orders of magnitude and computation time by using this scheme and they show this especially in this casthan paper and so it's not just some trick it's actually really critically enabling especially when you have higher derivatives. I use these exponential steppers all the time. Whenever I have more than two derivatives, spatial derivatives, like when I'm solving a PD, anytime you have more than two spatial derivatives, you should think about this scheme here because essentially what it does is it takes care of all the numerical stiffness that's being generated by the linear terms. We're going to talk more about numerical stiffness in in upcoming sections, but now you have a highlight of a different way to handle numerical stiffness. It's just coming about from the structure of your OD or PTE, right? And you're exploiting the structure to make a faster scheme. So, in general, some just bullet points here to remember. you really definitely want to exploit the mathematical structure. So you want to take as largest time step as possible and I've shown you that with adaptive stepping.

14:57 So yes, you could write your own stepper, but again a lot of the good steppers that are out there have adaptive stepping built in. So instead of you relying on you to figure out what the right delta t is, this thing will figure it out for you. second is if you can remove numerical stiffness issues which is this exponential ex exponential steppers does that also helps speed your computation up. So these are the kind of tricks that take you from, you know, a beginning user, computational person to a much more advanced user. And so you should always exploit them when possible because it's going to give you speed, accuracy, stability, all the things that you need to to develop good robust software infrastructure and coding infrastructure. So keep that in mind when you're solving differential equations.

15:47 Your basic move could be something like using a fourth order run cutter with adaptive time steps, but sometimes that still will have some problems and then you start looking for and that by the way already has the adaptive stepper built in. But if you have higher order derivatives, you want to definitely start thinking about how can you leverage something like these exponential steppers. So keep that in mind. These are advanced time and space stepping schemes and we will use them throughout later in the book especially as we get into PTE.

16:27 >>