Discretization of Elliptic Differential Equations Using Sparse Grids... (Cristoph Pflaum)
22 Video Views·Sep 5, 2023
"Discretization of Elliptic Differential Equations Using Sparse Grids and Prewavelets"
Cristoph Pflaum
3/27/15
Multigrid Methods Conference
Hello everybody, I'm very glad to be here again in Copper Mountain.
Yeah, my talk is about discretization of elliptic equations
using sparse grids and pre-wavelengths. I suppose that
most, maybe most of you don't know a lot about sparse grids, I don't know, but I think it's important to recall what that is.
And sparse grids was an idea which came up by Zenger
to discretize partial differential equations.
You all know what a full grid is. A full grid has n points in one direction and then n in the other direction.
So in 2D you have n power 2
grid points and in 3D you have n power 3 and in 4 you have n power 4 and so on.
And you see, when you really go to high dimensions, you will have big problems solving a PDE.
And that is an interesting property now of sparse grids is that the number of unknowns
does not increase in such a dramatic way. You can see with these dimensions
we only have n and then logarithm n power d minus 1
grid points.
And the reason for that is the structure of sparse grids.
So in the middle of the domain you have only n points,
then in the upper half n by 2, in the lower part n by 2, and that recursively goes on.
So when you add that up you have n plus 2 times n by 2, 4 times n by 4.
So you see you get a logarithmic term and in other dimensions you get logarithmic terms as well.
So the interesting thing is now when you can interpolate
functions
just by using B-linear functions, tree-linear functions, that would be very often used when you solve PDEs.
And when you use such B-linear or tree-linear functions or multilinear functions, then
the interpolation error is roughly the same as when we would have a full grid.
Of course, functions have to be smooth enough to this end,
but if functions are smooth enough, the interpolation error is nearly the same. So we have a
much less grid points, but nearly the same error. So the important question was now, how can we solve PDEs?
And there are two techniques. One is the combination technique. The other one is the Galerkin approach.
The combination technique is very simple to implement, but it has a very strong requirement
for the solution, a very strong smoothness requirement, and that's the reason why you cannot make it adaptive and
that's, it's not a very useful method for general PDEs.
And that's the reason why a lot of people were interested in the so-called Galerkin approach and
Zeringer, Bungerts and Balder at the beginning started with that, and they wanted to solve
PDEs in an adaptive way on sparse grids.
So this method would be a method
where you can also make an adaptive refinement when you have a singularity and in some parts functions not so smooth.
Yeah.
But before I explain what kind of difficulties we get when I do that, I think it's important to know,
okay, what is now the finite element space we are using, yeah?
In 2D, we can use, for example, just piecewise bilinear functions, as you all know.
And that would be, for example, the support of a very coarse piecewise bilinear function,
and then you refine it in x direction,
then you would have here a piecewise bilinear function with such a support,
and you can refine else in the other direction, and then you would get such a
function with such a very long
support. And you can refine here in the middle too, but you would not refine that area where you would have a full grid.
Yeah, and then when you overlap all these grid points you see, you get this pattern.
So in this finite element space you use in your Galerkin approach,
it's just a space spanned by functions of this support.
So the main idea of this function is you should not refine in x and y,
you should only refine so that either one of them is
very fine, but not in both directions.
Yeah, so what is now the difficulty in solving PDEs? The difficulties are so-called overlapping
basis functions.
What is an overlapping basis function? You can see when you take, for example, this basis function on that one,
they are overlapping,
which means
they overlap in this way, but here inside is no grid point. We have no
discretization point, and the difficulty is now to calculate a of vp vq.
So that's what, somehow you have to compute when you want to build out a stiffness matrix, or at least
implicitly you have to be able to handle that value.
And if you would have a full grid, then you can calculate
vp vq from these two basis functions, because you may also have a coarsening or prolongation.
Somehow you get the connection between coarse and fine points by prolongation correction, but here we have no fine grid points,
so here's no grid point inside, so we have a difficulty. And in particular, when we have variable coefficients,
we have difficulties because the number of data we have is already O of n squared,
so we have a lot of data, and when we would all compute them, we would lose all our benefits from sparse grids.
Okay, so what to do? So let us
look back to the history of sparse grids. Then we see, okay, the first discretization, where all
discretization for constant coefficients, and
and what
Zenger and Balder and Bader at that time found out a very tricky way to calculate these values in an efficient way, and
to evaluate matrix-vector multiplication in an efficient way. For constant coefficients, they found a very nice method.
Then later, there was the
concept of so-called semi-orthogonality, which I will explain to you in more detail later.
And then you have this method at that time, that's
nearly 20 years ago.
You get a very nice conversion theory. You get a very nice method. It's not too difficult to implement.
You have a very nice multigrid algorithm, and
everything is fine, with the exception that it works only in 2D.
Like, we want to have sparse grids in 3D and higher dimensions, maybe. So that was nice, but it was only something which worked in 2D.
That's the reason why other people came up with other concepts, but what you can say, the other concepts have some
difficulties. One of them was they were all non-symmetric for symmetric problems.
That somehow shows there's something not going in the right way.
Second, there was no proof of conversion.
It was very difficult to analyze for these other methods to show that they really work.
And the only
proofs were something like simulation results in 3D for variable coefficient, but never something for 4D.
I couldn't find something for 4D. And there were really serious problems in getting and finding a good fast multigrid algorithm.
Maybe that's also the reason why now, and this year, comes up a new article in CISC
about a multigrid algorithm for sparse grids,
but again for constant coefficient, because handling variable coefficients in sparse grids is a serious problem.
Yeah, there were some problems.
So my talk now is about exactly these questions. How can we handle
sparse grids' variable coefficients? And the idea is you only have to use pre-wavelengths. If you do that, then everything is fine.
A very simple answer. So what are pre-wavelengths? Maybe some don't know.
First of all,
have a look to standard piecewise linear function in 1D. That's a coarse grid function, and these are fine grid hat functions.
And
now when you look to this bilinear form here with derivatives,
everybody, most of you might know, okay,
these functions are orthogonal to each other with this H1 semi-bilinear form.
So when you take derivative of this function, you get 1 minus 1, and here 1, so we integrate, you get 0.
So what is a pre-wavelength? A pre-wavelength is now a function with a similar property,
but it has an L2 orthogonality property. So when you take this function here,
multiply it with that one, a coarse grid function, and integrate, you would get 0.
So pre-wavelength function is somehow a function with a little bit of larger support than these hat functions,
but they are L2-orthogonal.
At the end, you get the same fine element space in 1D and so on, but
it's just a little bit different function, which is L2-orthogonal. So the interesting property is now the following.
When we look to this
semi-bilinear form,
with here a constant coefficient, let's start with that, and we look now to these overlapping functions.
I told you, the overlapping functions are just what is difficult to compute in this part of it, to calculate
how one overlapping function is related to the other. That's the difficult thing.
So,
now what you can prove is that the value of a of b, p, q is 0.
Yeah, when it's 0, we don't have to compute anything, then it's easy.
But only
when we are in 2D, and have a constant coefficient, and use hat functions.
But when we use pre-wavelength, then it doesn't matter what kind of dimension you have, you all the time get 0.
So that's the big advantage, and that's also the reason why this discretization I showed you here in 2D
worked only
in 2D, because hat functions are only,
have this property only in 2D for c, constant 0.
But when you use pre-wavelength, all the values which are difficult to compute are 0, then we don't have to compute anything.
So now what we do, we do in case of variable coefficients.
We use the idea of
semi-orthogonality, the discretization of semi-orthogonality, and what is this
concept saying? It's saying the following, when you have a b-linear form like that,
and you have difficulties computing
a of b, p, v, q for overlapping functions, just put it 0.
So we don't, you know, that was difficult to compute. We could put 0
if we have a variable coefficient. So we define a new b-linear form, which is the modification of the old one,
by saying it's the same if we don't have overlapping function, and it should be 0 if we have overlapping functions.
Yeah, so we made a so-called
variational crime, but you know where variational crimes are not so
dangerous, like usually crimes are, because there's a big theory in mathematics showing that variational crimes
might not be really something very dangerous.
And that's what we have to prove later, that this variational crime is not a serious crime.
Okay, and then the discretization
we get is this kind of discretization, you know, just what we would do when we have a finite element approach.
Let me first show you an interesting impact on implementation.
The interesting impact is when you want to solve really a
PDE,
then these overlapping functions also lead to difficulties
when you want to really solve the linear equation system, because you have to handle a lot of values.
But when you have the same linearity, then everything is much easier,
because all the overlapping values are 0, so you don't have to take them into account.
So the multigrid algorithm you can use then is the so-called Q-cycle. What means Q-cycle?
It's just a semi-coarsening cycle, you know. Here, this scheme here shows the grid very fine in y-direction, here in x-direction,
and it's a scheme which is doing a lot of semi-coarsening, and it's doing a lot of v-cycles in y-direction and in x-direction.
That's it. And it starts at the same point as it ends,
and there's
the formulas you have to use here in semi-coarsening.
You can derive completely from the 1D case. You don't have to take into account anything overlapping. You just
derive the formulas you have to use for restriction prolongation for the 1D case, and you do also
use pre-wavelengths only in the direction where you restrict.
So you don't have to use pre-wavelengths in all directions. Only in the direction where you restrict you use the pre-wavelengths.
You can also do the relaxation only with standard basis function, if you like to, and then switch
to pre-wavelengths in the direction you are coarsening as soon as you want a coarsening.
So from
computational model, that's also not too bad. There's only one big difference,
which you might should remember,
between a multi-grid algorithm and full-grid and sparse grids.
That has to do with restriction and prolongation.
You all know you never would prolongate a right-hand side, right? You would
restrict the right-hand side, and you would prolongate the approximate solution.
But nobody comes to the idea to prolongate the right-hand side. Why should we do that?
We know the right-hand side on the fine grid, but that's not something we have to do in sparse grids.
You make a coarsening of the right-hand side, and you have to do a prolongation of the right-hand side.
We use exactly the same formula, but just change a little bit.
And the reason is you have to prolongate the right-hand side
because you have some change values from the other direction. That you have to take into account.
Well, that's the main difference between
multi-grid from
full-grid and sparse grid.
So now let's go to theory. I hope I still have some time.
I think I have some time, so good.
So, okay.
Now let's go to theory, which
certainly makes a lot of fun, to show that the variational crime is not a big crime.
First, let us see what kind of conversions we get when we apply semi-coarsening for constant coefficient.
That's the constant coefficient. What that would be. Then, in principle, you get the standard
convergence theory, which is
not bad at all for sparse grid. The computational amount for solving the linear equation system is something like
O of H power minus 1, with some logarithmic terms.
So it does mean there are some logarithmic terms. So you don't have a very high
computational amount in solving the linear equation system.
But the error in H1, though, is
roughly in the same range as you would have in a full-grid. It's O of H.
This is what you have.
So that's the same thing
for what you usually have in sparse grid.
But the semi-organality here is something you get for free because you're using pre-variables.
So what happens now if we really have a variable coefficient? And the analysis takes some time. It's some time to prove it.
Let's start first with this case. So when we have a Helmholtz term,
and we see here a variable coefficient and it's smooth enough,
then we can show we get the same order of convergence
until order 4.
But when you go to higher orders, then
the ratio of crime has some influence. And I think it's not too bad.
Somehow it's a good method. The ratio of crime really plays a role because if you
really have a very high dimensional problem, and to solve it in an extremely fast way,
even for variable coefficient, that would be great. But
with such a simple method,
I think we can be very happy about this result. Even when you think about the half-year convergence, the H1 norm, which is H power 1 half,
when you have only some less grid points, it's really great when you have that in dimension 6.
So,
okay,
another thing I also recently wrote down in a proof, but I only have to say it on a piece of paper.
But I think it works out fine. We can also prove if this coefficient here is variable,
if the principal part is variable.
And I have to say, proof needs some time really to do in this case, because some
things are a little bit
difficult. But when can I do it? And then we can also show this optimal convergence until dimension 3.
For dimension 4, higher, I don't know, I
need some time. We just need some time to do all the analysis and find out what's really going on in higher dimensions.
But let me, I think I still have some time, let me briefly tell you how the proof works.
So what we have to show is that the variational crime is not a too big crime.
That's what we mainly have to prove. So what we typically have to show is that the B-linear form
we were defining, and it's different to the original one, is small.
Sorry, it's small. That means we have such an estimating and
this term here.
Yeah, and it's something like O of h. Let's say O of h, but depending on the dimension, it's a little bit different.
It's something like O of h. And what is this difference? This difference is just this term when we have this Hamilton.
So we're not talking only about a variable Hamilton's term. So we have the integral,
this variable coefficient here, and then that's estimate we have to do for overlapping functions. Only for overlapping functions
we have to do that.
Okay.
The difficulty now is we have to really precisely to define what means an overlapping function. In 2D
I showed you this picture, but if we go to, oh
no, I will tell you that later.
Oh no, let me go back. Okay, here we have to show that this is small, and the idea is the following.
We want to show that this is small, and the idea is the following. When you put in here a piecewise constant function,
then by the case that we are using pre-Wavelets here, we would get
zero. So what we have to put in here, we can put in a function, a suitable
interpolation function, which interpolates constant in some direction, only in those directions,
where the levels in p and q are different, and then you can get this estimate. And
for doing that in detail, you have to know what are overlapping functions. To this answer,
let me show you that all this analysis goes at the end to
some playing around with numbers.
That, at the end, was a tricky part. You have to deal with numbers, with integer numbers, and
let me explain to you why that is the case for the analysis. So when you have these path grids,
then each of these basis functions, we can associate some levels or depths. We can say, okay,
this function, for example, is on the level 2,
0. That function is on the level 0, 2, and that's on the level 1, 1.
And then we'd have to do the following formal definition. Two basis functions are overlapping.
We say two basis functions are overlapping if, first of all, they're contained in this path grid. That means,
oh,
here's a power d missing.
That's what I forgot.
t should be here a vector of
of
levels of power d. And when you add up all these levels, it should be smaller than 1.
That means we have a function in this path grid, but the maximum of both should be larger than n. So
remember that these are both vectors
of dimension d.
And
then we need the following really technical lemma. So what we have is we have vectors
corresponding to levels. So level 1, level 2, level 3, and so on. These vectors, here I have written it correctly,
these vectors must satisfy certain properties
that they come from overlapping functions. Then we look to those
dimensions where these vectors are not equal, and then we have to show such an estimate.
But this estimate, it has nothing to do with, let me say, with Zobel's basis.
It's just a plain route with numbers. And then you can also get counterexamples. First of all,
let me make the following example. Say, let's say you have two functions, and one is on level 1, 0,
2 by 3, minus 1, 2 by 3, 2 by 3. And the other one is on
0, 1, 2 by 3, 2 by 3, 2 by 3. That's in dimension 5 now. When we have these integers,
we can first of all see when we add up that 1 by 3, 1 by 3, and here we get something smaller 1.
So it's related to a sparse grid. So that's also related to a sparse grid, because adding up gives only one n.
But when you take maximum, you see we get something larger n, because, sorry, because
here we have 0, 1, maximum gives 1, 1, 0, maximum gives 1. So that's related really to a problem.
To, to, these are overlapping functions, but they are overlapping in such a way
that the maximum here of these values and that values is only n by 3, and that's the reason. Yeah, oh, sorry.
Okay, my summary is now, sorry, my summary is now, we can discretize
partial differential equations,
even on 3D in a very efficient way, on higher dimensions in a very efficient way, with sparse grids and
variable coefficients when we use
semi-orthogonality and prevalence. These are the important properties, that's very important, and that makes the
algorithms easier. We only have to implement 1D dimensional formulas and
we get out a very nice conversion theory. Thank you very much.

