Section Insights
Introduction to Ax = B and Computational Challenges
What are the practical implications of solving Ax = B numerically?
The discussion focuses on the practical implications of solving the Ax = B equation, particularly in relation to sparse matrices and numerical methods like FFT and iterative schemes.
- Understanding the structure of the matrix A is crucial for efficient computation.
- Sparse matrices can significantly reduce memory usage in scientific computing.
- Numerical methods need to be chosen based on the problem's characteristics.
Using FFT for Numerical Solutions
How can FFT be utilized to solve differential equations?
FFT can be used to compute derivatives efficiently by transforming functions into the Fourier domain, applying multiplication by i*k^n for derivatives, and then performing an inverse FFT.
- FFT allows for rapid computation of derivatives, especially with periodic boundary conditions.
- Understanding the FFT algorithm's structure is essential for accurate results.
- The FFT shift is important for interpreting results correctly in the Fourier domain.
Derivatives in the Fourier Domain
What is the process for computing derivatives using FFT?
To compute derivatives, one transforms the function using FFT, multiplies by the appropriate power of i*k, and then applies the inverse FFT to return to real space.
- The method is highly accurate for computing derivatives.
- Using FFT is one of the fastest ways to compute derivatives under periodic conditions.
- Proper scaling between the domain size and the FFT assumptions is critical.
Sparse Matrix Representation
How can sparse matrices be efficiently represented in memory?
Sparse matrices can be represented using specialized data structures that only store non-zero elements, significantly reducing memory requirements.
- Efficient memory usage is critical in large-scale scientific computing.
- Understanding the structure of the matrix helps in building it correctly.
- Sparse matrix representations can improve computational efficiency.
Building Sparse Matrices
What are the steps to construct a sparse matrix?
To construct a sparse matrix, identify the non-zero diagonals and use libraries like SciPy to create the matrix while only storing the necessary elements.
- The structure of the matrix is determined by the discretization method.
- Using libraries can simplify the process of building sparse matrices.
- A clear understanding of matrix construction is essential for solving equations.
Iterative Solvers for Ax = B
What iterative methods can be used to solve Ax = B efficiently?
Iterative solvers like GMRES and BICGstab can be employed to solve large systems efficiently, especially when using sparse representations.
- Iterative methods can significantly reduce computational time compared to direct methods.
- Providing a good initial guess can enhance the efficiency of iterative solvers.
- These methods are readily available in libraries, making them accessible for practical use.
Practical Considerations in Numerical Methods
What practical tips should be considered when using numerical methods?
When using numerical methods, it's important to consider the choice of algorithms, the representation of matrices, and the management of computational resources.
- Choosing the right numerical method is crucial for efficiency.
- Understanding the underlying algorithms helps in troubleshooting and optimizing performance.
- Practical implementation requires careful consideration of data structures and computational strategies.
Transcript
0:06 So we're going to talk start talking about when we've been talking about ax equal to b it's typically been in relationship to this streamlike stream function solving from the vorticity. So we show that the pon equation generates a large ax equal to b. And so I want to talk about some of the practical implications of this when you start to implement these things numerically. And I want to not only talk about how we might solve it with the FFT, how we might solve it also more rapidly with iterative schemes. And how would we represent this matrix A under discretization that is largely zeros is very sparse. In fact, just because scientific computing typically generates this, we are often working with very sparse matrices. So it's important to take advantage of that in terms of the memory footprint as well. So, I'm going to show you all of these things in terms of comparing and overcoming some of the computational difficulties we're going to encounter when we solve realistic problems. Not even ones that are that hard. These are just things we're going to have to deal with immediately as we start to solve any kind of problem at all. Okay. So first of all, I want to start off with the for transform and talk the usage of the for transform and some of the issues that we have right away and how we would take a derivative of it because that's exactly what we're going to have to do in context of this poison equation we want to solve. So first of all, let's build a function and think about taking in fft. So it's kind of as simple as this. Here you go. We define a domain.
1:40 We're going to find a domain of size 20. We're going to have 128 points and since it's periodic boundary conditions, this is very important. So I define a domain with n plus one points. But the last point is the same as the first because it's periodic boundary conditions. So I can remove it. That's exactly what I've done right here. Okay, that's an important step. You don't solve for the same point over again. You have the f the first end points and the n plus1 point is the first point. Okay, that's what it means to have the periodic boundary conditions. And what I'm going to do here is take a function here. The function is given by just Gaussian and then just FFT it. And as simple as this np fft function I have it there's one other command you want to know. So once I've done that I'm in the 4A domain and if you want to inverse for a transform you just if okay but I also have this function here. You're probably wondering like well what's FFT shift? Well, I'm going to show you that in a minute because one of the things that happens if we look carefully at the FFT algorithm, it does a what's called a butterfly sort of algorithm in which the structure of this is to intermix the the points. It turns in it turns a problem of size n into two problems of size n /2 to four problems of size n / 4 to eight problems of size n over 8 all the way to its n problems of size one by one. And so that's how this n byn log n by this n login algorithm works. It turns this problem into a bunch of one by1's which then get glued back together through this butterfly type architecture. I'm not going to go into detail that now but it does have a practical impact on what you're doing with the FFT. In particular, if you take the FFT, here's the Gaussian that we took FFT of the FFT of a Gaussian is Gaussian. But of course, when I take the FFT, this is what I get. Doesn't look like a Gaussian at all. Right? You get these edges with large oscillations. And in fact, this is simply to a consequence of that butterfly algorithm that we have for the FFT. So if what the FFT shift does is it brings it back to this representation here and then what we do instead of look essentially the FFT also multiplies every other one by negative one. So if we were just look at the absolute value of it it becomes the Gaussian that we would expect. So in other words wrapped up in the FFT is if you want to look at the FFT data in the for domain it's not in the way you would have it structured.
4:19 if wave numbers get shifted like this. And so you have to have that in mind when you're working in the FFT domain. And the reason they don't shift it back is because it costs computational time. The whole idea of this is to go as fast as pop possible with your computational algorithm. And so it's not going to do this for you because that's costing overhead in computational time. It's going to leave like here. And then you have to understand that when you take an FFT, it assumes you're on a 2 pi periodic domain and it's doing this to your data and you're in the shifted domain. So you remember I'm going to emphasize this again. If you're doing scientific computing, you have your number one job is to be the manager of your algorithm. A lot of the underlying stuff, the algorithms built in are going to take care of it for you. But if you're not organized about understanding what's happening in your code, like for instance, if you use FFT that this is happening, you're going to be in trouble when you try to solve this. Same thing with making sure you've organized your data correctly and you have the right differentiation matrices. This is all very important from an administrative point of view of getting the code correctly done.
5:25 So let's talk about then one of the most important results of FFT in addition to the n login speed you have this derivative relationship here. So if you take the nth derivative of something, all you have to do is multiply in the for domain by i k to the nth power and then inverse for transform and you have the derivative. So let's compute some derivatives. Let's actually use this in practice. I'm going to show you this in practice how to do this. And here's a little code that's going to do it. First I'm going to define a domain size 208 points. A linear space goes negative L over2 to L over2 and n plus1 points. And I just take out the first end points.
6:03 Remember the end the last point is same as the first. I'm going to define two functions hyperbolic secant hyperbolic tangent because in fact we're going to differentiate hyperbolic secant which we can actually write down analytic solution techniques for the first derivative, second derivative, third derivative and so forth. And we're going to compare our method to the exact derivatives that we can compute. Okay? And so here's what we're going to do. We're going to take this here's my function and we're going to fft it.
6:30 That's called ut. So just NP FFT FFT U. I'm now in the for domain. So all I have to do is apply this formula. Once I'm in the for domain, all I have to do is multiply by I K. Okay. So how do I define K? Well, couple very important assumptions. The FFT thinks that you're working on a 2 pi periodic domain. But notice I structured my entire algorithm to be on a domain that's size L. So to take into account this scaling difference between the 2 pi and your L, here it is right here.
7:03 There's a 2 pi over L multiplication that goes on right here. This is a scaling factor. So that if you work on a domain size L, this scales it down to 2 pi. What you're seeing here now are the wave numbers. In other words, when you do for a transform, you represent terms of e to the i kx where it's like you know cosine 1x cosine 2x cosine 3x. Those are the integers that you have and that's what these are here. Except for you understand that you did this. You did this thing when you did the butterfly flipping. And so the range goes from 0 to n /2 and then minus n /2 back to to zero. So this is the flip that you have. FFT shift undoes it. But we're going to use this because when we take derivatives when FFT, it assumes that we're in the shifted frame. And so we're going to use this as our wave numbers. And so to compute derivatives, here's how easy it is. First derivative, multiply by i k * ut. Second derivative k^ 2 * ut. Third derivative i k cubed, right? And then you just invert these. Just do the inverse for a transform, which is f oft.
8:16 And you're back in real space. That's as simple as it gets. And in fact, this is one of the most accurate way to compute derivatives. if you have periodic boundary conditions. Okay, so anytime you have periodic boundary conditions, you should definitely always be thinking about using a 4A transform. So here are the comparisons. The original function is this blue here. So it's just a Gaussian. And then you start seeing for instance the first deriv is in pink here. And we've compare put we've plotted directly on there the dots which are the exact solution. and then the approximation which is a line and the second and third derivative there as well. In fact, these are highly accurate derivatives for these functions. And so what you have here is a very simple way to produce derivatives with an FFT assuming that you have boundary conditions. This is about the fastest way you can do a derivative and one of the most accurate ways you can do a derivative as well. Okay, and this shows it. So this is again you can download all of this from a git and run through all this code. So you just have it there for you to play around with.
9:23 So let's move on to sparse matrices. So that's one of the issues is how do I do derivatives practically with the f oft. Another is how do I represent matrices like this? It's mostly zeros. So just think about the memory constraints. If this is an n byn matrix then memory wise I'd have to save order n squared to compete keep this matrix a in memory. But you notice it's almost all zeros. In fact, there's only nine diagonals on this matrix that matter. So really, I should have 9 * n is all I need to keep to represent this matrix. By the way, for a long time in scientific computing, people know this. They want to have a small memory footprint and make use of the fact that most differentiation matrices are massively sparse. And so they've invented an entire framework to represent these data matrices. So I want to start building this out in a code base. So for instance, this is a top view of that matrix where only the nonzero elements show up as white. So that's the structure of the matrix that you have. And so what we want to do is how do I build this matrix and only keep the nonzero components in memory. Okay.
10:37 And you can do this with sparse sparse diagonals. So you can bring this in import from scypi sparse import spice sparse diag and what this is going to allow us to do is have this infrastructure for sparity there. Now I'm going to do a very simple example of the matrix I just showed you right which is this one here which what I did is I assumed I have five points in X five and Y which is not nearly enough but just for illustrative purposes but it's a 5x5 this becomes a 25x 25 matrix and so it's five points in X five points in Y so the total matrix is going to be that squared and here's how you would do it so first of all I mostly have diagonals that either have ones on the diagonals or occasional ones or occasional zeros. So in fact this structure of this matrix you really have to study it to see it to see where for instance on this off diagonal it's mostly ones with an occasional zero mostly ones with an occasional zero and over here you get a one 0 0 0 1 0 0 0 1 so forth so building this matrix I've said this before that you have to understand how this matrix is built this came directly as a consequence of the discretization and x and y with periodic boundary conditions That was in the first lecture in this series. And so it is really important.
11:59 Your entire job really is to organize this matrix because once you have it, the rest is going to be very easy for us to do. And here's how you build this matrix though, right? You would start saying, okay, I first got to be a vectors that are mostly ones and then zero, ones and zeros. So I build these all up in here. And this is what exactly what this is doing. So area point I put a zero or I put a one depending if I have the 0 one matrix. And so I'm going to build all these. These are going to be my diagonal elements. My nine diagonals I'm going to lay down in that matrix. And how do I put them down there is now I use this essentially the spdx framework. So first of all where are the diagonals? They're this these are what the diagonals are.
12:44 These are the matrices that are going to be in the diagonals. And you can verify for yourself where they're going to be. And this is going to be where they're positioned. So the zero position is the main diagonal. This is above the diagonal. This is below the diagonal. So one above di diagonal I'm going to put. So on the diagonal zero I put negative4s. One above the diagonal is essentially going to be this matrix E3. One below is this E2. And you can look we just built them. And then spag says tell me what you're putting on where you're putting it on and the size of this matrix. This is the entire solution technique here.
13:22 And what this builds for you is it builds a sparse diagonal matrix with nine entries. It is really critical you know how to build this. This is the in fact the entire solution technique del square s= omega. You're mostly your job is to understand how this matrix is built because once you have it then it's really easy to solve from there. But if you don't know how to build this you don't really know how to solve this.
13:47 Again we have to switch your mindset of thinking about you are a manager of the data and your job is to understand how you're basically putting all your data together in a compact way because the rest of it's just going to be ax equal to b. So that's how we do a sparse model. Last thing I want to cover is again so we've got the FFT for fast solves sparse representation. The last thing we want to talk about is what about the iterative solvers that are sort of kind of higherend and a lot of these are built in directly into scikitlearn or sorry into python and site scypi and so I want to go through some of these because they're commonly used they are used everywhere in practice for largecale computing as a fast and efficient way to solve these axe equal to b problems. So I'm just going to introduce two of them GMRES and BICG stabs which are sort of common but there's others that are out there and essentially what it is you're going to call in from the sparse linear algebra package and notice that it's capable of using sparse representations of matrices but all you do is say the solution x is gmraz a b so it's ax equal to b you give me the a and the b solve that's it so the blend above is you're you're actually in notice this is coming from the sparse linear algebra package and you bring in GMRES or you bring in biccg and you just give me the A and the B and this thing will actually use these advanced iteration techniques to solve your problem directly that AX in an efficient manner and the goal with these is to beat order N squ right lmposition is going to be your baseline target of what you got to build beat which is N squ and N squ is a lot to pay FFT T is N log N. And if you can do an FFT, you do an FFT. But sometimes the boundary conditions aren't amanable to the FFT.
15:43 So you want to try to use something like this. And by the way, these algorithms have a lot of different things you can bring in, a lot of flags. You can specify how accurate you want it to be. You have to specify the number of iterations, preconditioning matrices, the initial guess vector. You always want to initially guess it when you're time stepping. you if you don't give it a guess, it just starts off with a guess of zeros. But what you want to do is say, well, if I'm solving the solution, the solution in the future is not that big of a change from what it is right now. So I'll use the current value of my stream functions for instance as the guess for the future, which is only delta t into the future and that will really cut down a number of iterations.
16:24 If you don't do this, it's a stupid way to solve it. So you want to use this, always use the x0, you can restart it and so forth. So lot of optionality with these codes. These are very sophisticated. We're not going to go into detail of how they're actually structured and work, but they are available to you really easily, just like the FFT. One line of code and you have all the power of this methodology available to you to solve fairly sophisticated problems that arise like the ax equal to b we have for solving that string function equation.
16:56 So that's kind of it. These are really practical tips of things you actually have to think about. These aren't just esoteric. They're like every day. If you're going to use FFT, if you're going to represent these m discretization matrices in sparse form and if you're going to use some higherend iterative schemes to beat the order n squared bottleneck of a computational algorithm, all these are not they're again not esoteric. They're like generic things that you have to be considering for every time you start thinking about any kind of serious PTE solvers that you're going to be using in general.
Summary
- The Poisson equation can be solved using FFT, which provides a fast O(n log n) computational complexity.
- Periodic boundary conditions are crucial when defining domains for FFT, ensuring accurate representation of functions.
- The FFT algorithm involves a "butterfly" structure that intermixes data points, necessitating careful management of data to avoid errors.
- Derivatives can be computed efficiently in the Fourier domain by multiplying by \(i k^n\) and then performing an inverse FFT.
- Sparse matrices, which contain mostly zeros, can be represented efficiently to save memory, using libraries like SciPy.
- Iterative solvers such as GMRES and BICGStab are introduced for solving large systems of equations, offering flexibility and efficiency.
- Proper initialization and preconditioning can significantly enhance the performance of iterative solvers.
- Understanding the underlying algorithms and data structures is essential for effective scientific computing and problem-solving.
Questions Answered
What are the practical implications of solving Ax = B numerically?
The discussion focuses on the practical implications of solving the Ax = B equation, particularly in relation to sparse matrices and numerical methods like FFT and iterative schemes.
How can FFT be utilized to solve differential equations?
FFT can be used to compute derivatives efficiently by transforming functions into the Fourier domain, applying multiplication by i*k^n for derivatives, and then performing an inverse FFT.
What is the process for computing derivatives using FFT?
To compute derivatives, one transforms the function using FFT, multiplies by the appropriate power of i*k, and then applies the inverse FFT to return to real space.
How can sparse matrices be efficiently represented in memory?
Sparse matrices can be represented using specialized data structures that only store non-zero elements, significantly reducing memory requirements.
What are the steps to construct a sparse matrix?
To construct a sparse matrix, identify the non-zero diagonals and use libraries like SciPy to create the matrix while only storing the necessary elements.
What iterative methods can be used to solve Ax = B efficiently?
Iterative solvers like GMRES and BICGstab can be employed to solve large systems efficiently, especially when using sparse representations.
What practical tips should be considered when using numerical methods?
When using numerical methods, it's important to consider the choice of algorithms, the representation of matrices, and the management of computational resources.