ROM introduction

okay so I'd like to present some notes or an overview on model reduction in particular we're thinking about this whole concept of reduce sort of modeling and what the theme of these sets of lectures will be on is on nonlinear model reduction and I want to give us sort of a high-level overview of what we want to accomplish in this so there's a lot of different aspects of model reduction and this is just one where we're going to think about thinking about nonlinear dynamical systems and how to think about solving them in an efficient way using the fact that there is in fact usually some low dimensional embedding which you can do computations in a much faster more efficient way so let me give you an example of what it means to think about the idea of dimensionality reduction and I'm going to motivate this by several examples that come from biological physical engineering Sciences just so you get a concept of what we're trying to actually do with this model reduction framework the first example I want to give here is actually from recordings of an antenna lobe on a locust what they do is stick probes in this antenna lobe and they record off these neurons and the neurons themselves are spiking and in that spiking is information information about sensory input into the system and the data typically then ends up looking something like this where these are different trials or different recordings from different neurons you apply stimulus and you get these spikes and what you'd like to do is make sense of all this there are maybe hundreds of thousands to the millions of neurons in this olfactory processing system and one of the questions you could ask is well how does this thing actually decode information now one of the most amazing things that was observed and this is a G Lorentz group that observed this on the locust is that they said okay let's take all these spike recordings and let's look at the firing rate activity so not just spikes but you know the density of spikes and then what they did is a singular value decomposition or a principal component analysis it said in the first three principal components this collection of hundreds of thousands of neurons looks something like this here let me explain what this is so what this is is right here where it says B is where this thing is basically sitting the activity this is in principle component space one two and three and here's the AXA coordinate axis right here and it's sitting right over here and then when they apply stimulus takes a directory up to this fixed point you turn it off comes back down turn it on comes back down so this entire system which is being driven by noise processes and stochastics looks to be three dimensional this picture kind of conveys that idea so the idea is you could do a simulation on hundreds of thousands of millions of neurons or with the right basis set or the right representation of the dynamics you could drop it down to three dimensions which is what the data says is sort of the intrinsic dimensionality of the Seoul factory system and that's the kind of thing we want to take advantage of in this reduced order modeling framework so it's a biological system but you see this across the sciences so I'm giving you here an example for Incheon but for instance of an optical system and this is in these a collection of waveguides where you see self localizing patterns as you increase intensity sorts of noland your phenomena yet everything looks to be very low dimensional you also see this in turbulent flows here you see large-scale structures that develop out of the fluid system same thing here here's a turbulent flow that's being developed this is a hurricane off the coast of Florida and again you see this very large spatial temporal structure that is forming there and of course if you were to put this on some very high dimensional grid you could do the simulation but really the thing you're after is this low dimensional structure that's embedded in this seemingly high dimensional system down here this is what's called a bose-einstein condensate when you cool at supercooled atoms - you know milli kelvins microkelvin you can get atoms to basically form a condensed matter of state which is this both sind deine condensate again a low dimensional representation and over here you have this granular flow in a four system where you see clear structures develop from a micro scale physics and it is exhibited on a macro scale so these are examples just like the neural system of systems that develop low dimensional coherent structures that you would like to take advantage of instead of doing very large simulations is there a way to trade this out and frame the problem in some low dimensional embedding that you see clearly here develops in the system okay so that's the that's the main idea of course where we're gonna working with this directly is with equations so we're going to start off here there's going to be our basic framing of the problem we're to assume either we have a partial differential equation or a large system of differential equations where the state of the system is given by you a vector u and we're interested in is how does that change in time we're gonna make an assumption that the du DT depends upon some linear term here that's right so L times u so L can be prescribe some linear dependence in the problem it can also take into account derivatives things like diffusion advection processes these are linear dynamics they're all encoded in this L operator and then we have the nonlinear dynamics okay so we're gonna want to understand how this thing of all is in time and one of the things that we know if we derive this system let's say from a large partial differential equation then this is a very high dimensional system U is okay with a lot of independent degrees of freedom that are connected kept together to all the other all the other points in the system and but on the other hand you also observed from what we just saw that chances are there exist some low dimensional embedding of where this dynamics is happening so there's a couple other things here you typically are going to prescribe some boundary conditions that go with this as well as initial conditions so this is the full set up of the system PDE or system of differential equations that rises from a PD high dimensional linear nonlinear term some boundary conditions initial conditions and what you would like to do is find an efficient way to simulate this into the future now we learned a lot of numerical techniques for doing this but when this gets to be very high-dimensional it becomes quite a challenge as big as the computers we are have right now I can give you a problem that will exceed the capacity of your computation at this point so you can think about reduced order modeling is for very large scale systems this is not necessarily geared for smaller systems you can put on a laptop this is stuff that would go on a supercomputer or are potentially problems that are even beyond the reach of supercomputers at this point now the challenge ultimately is just going to come down to that nonlinear term if this thing we're linear we would be in good shape we could actually do quite a bit but the non-linearity is actually where all the complications arise and also where all the interesting phenomena typically occur right so a lot of things that were very interested in modeling and all the interesting dynamics we see that non-linearity drives these processes on the other hand is that non-linearity that's going to create a lot of our computational challenge and how we handle that non-linearity is going to be really important for us to make effective reduce to our models okay so what's going to be our process to solve problems when we do start a modeling one of the first steps you've got to do is you've actually got to potentially do a short time run of that very high dimensional system okay so in essence you're not necessarily committing to doing a large-scale simulation of the system for a long time but you want to do a burst of high fidelity simulation for some amount of time and what you're going to do is collect the state of the system at different snapshots of time so this X matrix here is a collection of data so u1 is the data of that dynamical system collected at time T 1 u 2 is at time T 2 all the way up to time t of em so we're just simply sampling our dynamics the full state dynamics and this matrix X tells us you know stacks up our data and then we can start thinking about doing an analysis of where does this data live and what kind of space does it live in and one of the you know standard techniques for getting at sort of what is the intrinsic coordinates or the dimension of the dynamics or data is through the singular value decomposition perhaps one of the most important algorithms that you can use in data analysis it's also frames how we think about reduced order modeling here so the way this thing is a value decomposition works it takes this data matrix and decomposes into three matrices you're guaranteed to have a singular value decomposition of any matrix and so you take your data matrix X which is this box here and this box has a certain number of high dimensional space here so these are all your when you discretize a partial differential equation you might have millions or billions of states of the system and then the columns are the snapshots in time and what this mated matrix decomposition does it creates for you three additional matrices the u matrix which tells you about the spatial correlations in your data this is this matrix here it's the same size if you use the economy SPD which is what we mostly want to think about in this case although I will have some separate lectures about the singular value decomposition outside of this remember this is just an overview but the idea is that this thing will create this embedding space spatially it also creates a sigma matrix which is a diagonal matrix which tells you essentially how the importance of these made of these vectors in weighting of the data so it's going to give you an orthogonal set of vectors in which the data is embedded and it's going to tell you how important each direction is in other words with your data how much does it project into each of these individual directions and then the V gives you the corresponding time dynamics for each of these vectors in you okay again we'll have a separate lecture separate set of lectures actually just on the singular value decomposition because it in it of itself is one of the most important workhorse algorithms available to us in thinking about doing model reduction now oftentimes the singular value decomposition these modes that come out are often called PID modes proper orthogonal decomposition so that's one standard term for them people have used other terminology for this it's also known as the Haute link transformation karlova modes or karlova analysis also empirical orthogonal functions and it's very closely related to principal component analysis and the only difference between principal component analysis and all those other terms is that what you would do for each column of data is you would mean subtract and set the variance to 0 to 1 so every row would have mean 0 unit variance and this way is one way to handle the data so that you can normalize it in some sense so PCA enforces that Pio DSV d EO FS Carla Melvin they don't necessarily enforce that kind of normalization but they're really all the same they're the SVD now what's important about this SVD is that the SVD gives you a principled way to do a low-rent truncation of the data in other words find the dimensionality of your data or the intrinsic dimension of your data where you can use some low rank or low dimensional embedding to represent your data so what I've done here is taken my data matrix and said hey look I've taken a lot of snapshots of this system and I might find and the way you would find this is looking at your singular values you might find that Hey look there's about ten modes or our modes that matter in the data to have 99% of the variance or 99.9 percent of the variance in other words they capture most the variability of the data so what you'd want to do is say well that's the case if I find our modes that really dominate everything I'd want to pull out our modes from my u matrix the first R modes I'm going to stack those in a matrix called V of R so the R represents the rank and this V of R represents the low dimensional manifold or subspace in which this data is embedded these are the coordinate system that I want to use in which I know the data is best represented in fact it's guaranteed to be the best representation in an l2 sense now how you would find the number of modes and truncation again will be a separate lecture related to the singular value decomposition but normally what you'd find is it principled way to take are modes out of this and that's going to give us an our rank or low rank truncation of our of our model so once you have this now you can start building a reduced order model and the way you're going to do this is through this technique called galerkin projection so what you're going to do is say hey look my U as it changes in time is I will do this galerkin projected framework which is I'm gonna say that I'm gonna embed all my date all my dynamics in this sea of our space in other words this our rank subspace where most of the data was found and here a of T is now the coordinate system I want to discover it has all the time dynamics on this subspace so I'm gonna basically assume my solution is sort of a separation of variables solution where I embed everything in this low rank subspace and now my job is just to find a of T now one thing to keep in mind about these few are the Ivar has a bunch of modes are of them in fact so these are vectors and when you do the SVD these are the first are columns of U so each one of these columns is orthogonal to all other columns so in other words if you have V of J transpose V of K so I want to take the inner product of any two of these well this thing here is either equal to one because the use were an orthonormal basis so if JFK if J is equal to K in other words it's the same vector then the it's unit length however if J is not equal to K then there are thought Cannell and then you get zero so this is an idea here that's very important and it's very nice that the SVD automatically gives you an orthonormal embedding space which has this nice ortho and allottee property now that becomes important because one of the properties we're going to use is the fact that this property suggests that the transpose of the r matrix times of the fee may trick with rank truncated with r times V of R is equal just to the identity okay and we're going to use that in our next step when we plug this expansion right here into our governing non linear dynamical system okay so that's an important point to keep in mind and again you get it for free from the SVD this orthogonality orthonormal basis that you're gonna start using now to embed all your dynamics in okay so now we have this orthogonal property we have some low rank subspace we want to work in what do we do next well what we could do is simply plug in that expansion multiply on the left side by the transpose V of R and what you end up getting is this equation right here this is your low rank dynamic what I've traded out is the evolution on this you vector which is very high-dimensional for evolution on the a vector which is our dimensional and here's what the equations look like so da DT so now what I'm solving for is the time dynamics associated with each mode each of those poto D modes that I actually extract it out with the SVD and this becomes my reduced order model so I went from an n-dimensional space down to an R dimensional space and if I have a very small rank truncation it means I've got myself a very large dimensionality reduction now this isn't so bad except for again the nonlinear term so if you look at this I'm just gonna look here on the left side for a minute I have the time dynamics they and then here I have the lvl matrix which is essentially the linear dynamics times V of R and over here on the left is VR transport and so I could pre compute all of this and this just becomes one vector multiplied by a so it's kind of trivial to do the linear terms are trivial to handle in this setup problem is the nonlinear terms as I've suggested non-linearity is what kills you here which is now you have V transpose R times the evaluation of the non-linearity in this low dimensional embedding space so every time you you update the a values you have to update the non-linearity so every single time step requires you to reevaluate the non-linearity and do an inner product with Phi transpose R where is the linear terms I can just do this all once at the beginning of the computation and I don't have to do it again it's done here I have to keep doing this and this is very expensive actually and let me show you why I'm going to give you a simple example of the challenges that are imposed by this non-linearity so let's say that the non-linearity is something simple the non-linearity is a function of you our state space which is suppose it's you cubed so I have a cubic non-linearity in my PDE and what I'd like to do is evaluate that cubic in this reduced order model and let's do something simple suppose that our fine that the rank of this system is there's two modes that matter okay so I want to do a two mode expansion now watch what happens just with a simple two mode expansion with a cubic non-linearity so cubic a two mode expansion replica Li is going to assume that you state of my system is going to be some coefficient a1 times Phi 1 which is the first pewdie mode times a2 times Phi 2 which is the second P OD mode now presumably I would have found this from the snapshots and what I need to determine is a 1 and a 2 what are their dynamics so once I determine a 1 and a 2 my solution is right here I just take a1 times Phi 1 a 2 times Phi 2 already know Phi 1 I already know Phi 2 I discovered those from the snapshot matrix in the sed so I'm going to take this hint thing here but now I've got to take the cube of it right so a simple two mode expansion in that cubic expands out to four terms and there they are at the bottom here so now I have four terms and then once I get these four terms remember I still have to hit it with an inner product so the simple cubic requires me to compute four inner products remember each one of these Phi 1 and Phi 2 is length n so it's very high-dimensional so the inner product computation I have to do is very large so even if I have this low dimensional embedding sitting there if I have to work with this with nonlinearities just think about this thing maybe if I had a 10 mode expansion a 10 mode expansion going through that cubic would generate a very large collection of terms and I have to do an inner product on every single one of these terms to compute how its projecting into my Phi of our space this is the challenge of non-linearity in reduced order models and in fact it becomes the heart of thinking about none linear model reduction is how to handle nonlinearities in efficient ways and we'll spend quite a bit of time talking about it from a historical perspective and building up towards understanding how would we be able to do this computation in some kind of fast way okay so here is the summary of this model reduction architecture I've kind of stayed high level and I want to touch back on the key aspects of this and this is what we're going to spend a lot of time building out going very slowly through examples and code just so the understand all these pieces but the idea is the following you're given some differential equation or partial different equation that's been discretized and it's very high dimensional so as a linear and a nonlinear part so that's the first step is you have that system and typically in model reduction you have to do initially some high fidelity simulation of this system but allows you to produce a snap snapshot matrix X and these are vectors U at T 1 T 2 all the way to say P snapshots of the system so you take lots of snapshots of the system and this thing here is something like an N by P matrix and what you're going to do with this X matrix is you're going to do a singular value decomposition and in that singular value decomposition you're going to evaluate how many modes you're going to keep what is the underlying or intrinsic dimensionality of the system or underlying rank of the system and you're gonna keep a small collection of modes in other words when you look at it the u matrix that's produced in the SVD you're gonna take the first are columns that would represent the low dimensional embedding space of this dynamical system now the second thing after we've done this discovered the low dimensional structure we want to work on is that we have to actually go and build a model now for how the evolution of the Dino happens in that low dimensional subspace and we do this with the galerkin expansion so we said that you itself is essentially now we're gonna use a basis set of functions which are my rank truncation of the SVD modes times a of T now a of T itself is of rank R so what I've really done is said look R is much smaller than n so this original system is very high dimensional potentially millions billions trillions of degrees of freedom which might come from a disk ritas ation of some very large partial different equation but then I might find some our rank truncation maybe I find 50 modes maybe 10 maybe 200 which is much smaller than the millions or billions that I have over here so I'm gonna try to project everything down into this rank R sub space in which I observe the most of the dynamics to be evolving on so I'm going to plug this into this equation multiplied by P R transpose and I get my finally my Galera can projected dynamics which is a system of our differential equations so I went from n differential equations to our differential equations that's it that's the whole reduced order modelling story the problems come and the fact that how do I discover the right embeddings and how do I handle that non-linearity if I'm going to go to this low rank structure so most of them are going to talk about is handling that non-linearity in what we do in the future here alright so that is the general broad overview and again we're gonna think about workhorse methods singular value decomposition be one of those the proper orthogonal decomposition which is again is just a name another name for that singular value decomposition we're going to talk a lot about choleric and projections then because once you discover from here your low dimensional embedding how do you project your whole dynamical system into that low dimensional space and then the most important thing that we have to build out is handling the non-linearity we're gonna use several non linear interpolation techniques we're gonna cover what's called gap EP OD and also the dine method which is discrete empirical interpolating method this is a method in both these methods are all about the fact that when you go from a high dimensional space this non-linearity is also embedded in a low dimensional space do I need to do in dimensional inter products to get me accurate approximation in this R dimensional space the answer of course is no there is a very efficient way to evaluate the non-linearity in our dimensional space which is much better than doing full inner products and n dimensions and so we'll talk a lot about historical developments around these ideas once we've kind of outlined most of this and developed it out we'll have a set of lectures on singular value decomposition on p OD methods on galerkin projection and then there's no linear interpolation we'll talk about emerging methods of machine learning and manifold learning that allow us to do even more things for parameterize partial difference equations or non-linear model reduction that sort of represents state of the art of where people are right now so that's the overview we're gonna start building it all out from here and but this is very important that you understand the generic architecture first before you start getting into the details and if you can understand this basic framing then it will help you understand exactly where we want to go at each one of these points because the rest of this nonlinear model reduction course is really just geared at hitting these topics and in building them out so you understand how each one of these relates to the overall theme and computational efficiency we need to use to make these reduced sort of models efficient ok so I'll see you in these lectures as we go forward in the class

Channel: Nathan Kutz

Views: 19,841

Keywords: nonlinear model reduction, reduced order modeling, nathan kutz, introduction, proper orthogonal decomposition, singular value decomposition, gappy POD, DEIM method

Id: YtFuVwrZxC4

Length: 28min 50sec (1730 seconds)

Published: Mon May 02 2016