Matrix-vector-multiplication for solving high dimensional Schrödinger problems (Rainer Hartmann)
3 Video Views·Sep 5, 2023
14th Copper Mountain Conference on Iterative Methods
An efficient matrix-vector-multiplication for solving high dimensional Schrödinger problems using prewavelets and sparse grids
Rainer Hartmann
3/25/2016
It's sparse grids.
OK, thank you for the introduction.
So I'm Rainer Hartmann from Germany.
And good morning, first of all.
So in my talk, I will present an algorithm
for the efficient matrix vector multiplication
using sparse grids and three-way flaps.
So first of all, let's have a look
at high-dimensional problems.
So I picked up a Schrodinger equation problem
for a 10-electron water molecule.
So we would have to solve a 30-dimensional problem.
Unfortunately, if you use a standard finite element
technique with regular grids, we run out of memory.
So curves of dimensionality is showing up.
And for dimensions more than 5 or 5, we get problems.
So standard finite element method would not work.
And we need another method.
And in this case, I suggest sparse grids.
So I will discuss that in detail now.
And first of all, one example problem
that will show up later again.
So that's the main problem I want to solve for the moment.
So it's a six-dimensional problem.
So we talk about unit sphere in 6D.
And we have homogeneous boundary conditions.
And we have a variable coefficient.
In this case, it's a cu.
And it's like a tensor product of sinus functions
in each dimension.
But of course, we are not restricted to those tensor
product functions.
So we can use arbitrary variable coefficients
for the Helmholtz term and also for the diffusion term.
So our method is general.
But it's easier to get here an exact solution.
That's why we will stick to that problem.
OK, let me shortly introduce sparse grids.
Maybe some of you know it.
For others, it's some kind of tree-like structure.
So we start with a very coarse grid or large mesh size.
And then we refine semi-refinement-wise
in one direction, in this case, in x direction and y direction.
And we do that again.
So a tree structure.
And in that case, we get a pattern that looks like this.
So it's not a regular full grid.
There are some parts missing.
And the important thing is that the number of grid points
is not n power d.
But instead, it's n times a logarithmic term,
log n power d minus 1.
And that saves a lot of memory.
So let's have a look at the interpolation error
for sparse grids.
So in H1 norm, we have O of H. And in L2, in an infinity norm,
we get H squared times a logarithmic term, log n power
d minus 1.
So this term does not influence, for large dimensions,
our result significantly.
So we still have convergence close to H squared.
Yeah, so let's span the piecewise linear finite element
space.
And the first discretization with linear finite elements
using sparse grids was given by Zenger and Balder.
So Zenger and Balder was the first one
who settled up sparse grids in the beginning of the 1990s.
So let's have a look at the space
where we have a union of where we start
with a very, very coarse grid.
And then add some more levels.
So see my refinement by 1 half in x dimension
and also in y dimension.
And let's add more levels.
So in this case, we have maximum depth 3.
So level 1, level 2, and level 3.
And the corresponding grid pattern is shown here.
So how do we calculate the depth?
So in this case, we have a vector
with a depth of each dimension.
So in this case, d1 and d2 for a two-dimensional problem.
And we limit the maximum depth, which
is the sum of all depths by n.
So in this case, we get dn.
And the corresponding space, vector space, is vdn.
Yeah, so now we have a look at the finite element
discretization.
So it showed up by Balder and Zenger.
And it was the first one discretizing finite element
problem on sparse grids.
So first of all, we have, in this case,
just the diffusion term.
So no variable coefficient.
In this case, what we will later see,
we get some orthogonality property.
So we have an a-orthogonality, since the operator gives us
a half-hard basis.
And if you swap over to variable coefficients,
we do not have this orthogonality anymore.
And in this case, I will introduce pre-webplots
that have L2 orthogonality.
So let's have a look at our iterative solver.
So we want to solve Au is Mf.
So Mf has to be given either in a surplus notation
or pre-webplot notation.
And then we have here a matrix vector multiplication.
But more important is Au.
So we need A times U for our iterative solver,
which is a preconditioned conjugated gradient
method.
So preconditioning is by Jacobi preconditioning done.
And together with pre-webplots, we
have a small condition number in the order of O of 1.
So well-known behavior given in literature.
And if you have a look at a three-dimensional Poisson
problem, I stated here the tail of the condition numbers
for level 6, 7, 8, and 9.
So 6, 7, 8, and 9 for a sparse grid.
So we are close to 5.
So pretty good conditioning.
But what is problematic is to have an efficient matrix vector
multiplication.
So sparse grids reduce the complexity for the memory.
And we want to have that complexity also
for the matrix vector multiplication.
Do not lose efficiency.
OK, so the matrix vector multiplication,
we want to calculate A times U. And U
is given on the sparse grid.
So sparse grid, we have the decomposition
in all those regular full grids.
So what do we have to do?
We have to multiply each component of that sparse grid
or full subgrid of the sparse grid by A or AN,
since A, the stiffness matrix, is also
given on that sparse grid level.
So U, the solution or the input, is
a decomposition of surpluses.
So we have to sum up all those WTs to get U.
And now we want to apply the bilinear operator on U.
So we have to take the sum over all the surpluses.
So what does that mean?
We have to sum up all those elements here.
Oh, I think I got the black button.
OK, so we have to go over all those hierarchical surpluses.
Yeah, and if we have a look at our sparse grid,
we want to sum up all those.
But first of all, I want to stick to a full grid,
because for a full grid, it's easier to explain.
And yeah, what the basic idea is,
if you want to calculate the energy
for one specific element, let's say,
for example, for that subgrid here,
then we have to sum up over all others.
And we do that by a decomposition
in four directions.
So we sum up from all directions.
In this case, we come from the top left, down, top right,
and so on, and pick up all those elements.
So let's discuss that in more detail.
So we have, again, AU times our test function.
And we want to calculate the entry of phi ti.
So in this case, it's that dark blue element
down here, which has index t.
And i means that we have all element, or one specific
element on that level.
And now I have, again, here the decomposition into four cases.
It's one, two, three, four.
The first one comes from the left bottom and wants to go up.
And what do we do to go up?
We apply prolongation.
So we are prolongating our solution.
And here, for the right, we have restriction, restriction.
So we start here and restrict one dimension.
And then we restrict the second dimension and go down.
In the middle, we have the mixed cases,
so restriction and prolongation.
And here, it's important that we have, firstly,
to apply prolongation.
And then we have matrix multiplication.
And finally, we apply restriction.
So you see that here also in the formula.
This term here corresponds to the second pattern here.
So inside, we have prolongation, since we
are starting with smaller depths.
So we are starting from downwards and going upwards.
Prolongate.
Then we apply the bilinear operator.
And finally, we restrict.
So restriction is here, since we have here higher depths.
In this case, it's Tx for x dimension and Ty for y
dimension.
Yeah, the algorithm works recursively
over all dimensions.
So we have a dimension vector.
And it starts with the first entry
and goes down to the last entry.
So we can easily adapt that algorithm
for arbitrary dimensions.
So 6, 10, 30, however.
So in this case, we get two power d cases.
So either prolongation or restriction.
And that power of dimensions.
And it is still important that we
have to do, firstly, prolongations.
And then we have matrix-vector multiplication.
And finally, restrictions.
So we have to reorder our dimension vector.
And here is the formula for going over those two power d
cases.
So we have an outer sum.
And then we are restricting in some dimension
of all dimensions.
So we're picking out those two power d cases.
And then we have the restriction operator outside.
We have the bilinear operator.
And inside, we have prolongation.
So finally, let's have a look at the computational costs.
So we have to apply two power d operations on each subgrid.
And the number of grid points was 2 power n, nd minus 1,
which is n times log n, d minus 1.
So we are still in the order of n log n, d minus 1.
So we didn't lose any efficiency.
So next part is to concentrate on sparse grids.
So what happens on sparse grids?
We are losing those domains here.
And in this case, we have again the splitting, our four cases.
Prolongation is still the same.
Restriction, restriction.
In this case, OK, they are missing some elements,
but no problem.
They are missing on the sparse grids anyway.
And now we have the mixed terms, restriction, prolongation,
and prolongation restriction.
And now let's have a look at the red boxes here.
So we want to calculate the overlapping
of red box and dark blue box.
And in this case, there is one path which would go like here,
down, and then right.
Down, right, what does it mean?
First, we have to restrict, and then prolongate.
Unfortunately, that's not allowed.
And going like this, first prolongation, then restriction,
that would be fine.
But you see, this element box here is missing.
So this would be going like here, right, and then down.
And we're missing that element in our sparse grid.
And if you would do the calculation on a full grid,
we lose all the memory gain we have on the sparse grid.
OK, let's say, or sum up, this element is not picked up.
But it is not a problem.
Why?
So in 2D, we have so far orthogonality.
I will explain in detail why on the next slide.
And in higher dimensions, we will introduce pre-wavelengths.
And pre-wavelengths also give us orthogonality.
And then we come to variable coefficients.
And then we lose again the orthogonality.
And then we will introduce semi-orthogonality.
But first of all, let's go back to two dimensions.
So in this case, we have linear finite elements.
So in this case, let's say we have this function here.
And we split it up into a hierarchical surplus
and a coarse grid, or coarse grid-hacked functions.
And then we apply the following bilinear operator.
So we have here differential operator on u and v.
And in this case, we get a half-basis.
And half-basis is orthogonal.
So at least under this operator,
we have a orthogonality.
And let's go to the next slide.
So we have this upper left missing element together
with a dark blue one.
And in this case, we have a very nice behavior.
And we call that overlapping.
So overlapping means we have twice the support.
The first basis function is vp, and the second one is vq.
And since they have different depths in each dimension,
we have an overlapping region of the surplus.
So here is the intersection where
no grid point is contained in.
And in this case, if two functions are overlapping,
which means that the grid point is not inside the intersection
domain, we get orthogonality.
So let's have a look at the differential operator.
So we have then differential operator
in at least one dimension.
And then those functions are a-orthogonal.
And a, vp, vq evaluates to 0.
So what does it give us?
So it shows that the missing elements are not a problem
since they are anyway 0.
We can leave them out.
Unfortunately, in dimensions higher than 2,
we have only overlapping functions in two dimensions.
But we have maybe three dimensions.
And then for the plus operator, not all elements
evaluate to 0.
In this case, we introduce pre-wavelength.
So in this case, we have a splitting
into coarse-grained hat functions and now
pre-wavelength basis for the fine grid.
So here we have some boundary elements, homogeneous
spherical pre-wavelengths, and in the middle,
classical pre-wavelengths.
And here again, a boundary element.
And for pre-wavelengths, we have l-orthogonality.
So now, l2-orthogonality, sorry.
And this solves the problem for higher dimensions.
So in this case, this operator evaluates
to 0 for overlapping domains, basis functions.
Let's come now to variable coefficients.
So for variable coefficients, we do not
have still our l2 operator.
So we have there a variable coefficient.
And we lose the orthogonality property of pre-wavelengths.
And in this case, we apply a trick.
So we call that semi-orthogonality property.
So we just set this entry here when two basis functions
are overlapping to 0.
So we introduce our variation at prime.
And our new problem is then using this semi-orthogonality
bilinear operator to solve the system.
So the question is, does it still converge?
And the good message is, yes, it does.
So we have our detailed proof submitted to CINAHM.
And then we show that the variation at prime
goes down, or can be approximated
by a constant h log h minus 1 power d minus 1.
So there are some better bounds for lower dimension.
But this holds for high dimensions of field.
So at least the variation at prime goes down.
And we can show that our solver converges.
Yeah, the solver is working.
So we can use it now to solve our test
problem from the beginning.
So a six-dimensional problem.
In this case, we have depth varying from 2 to 6.
And we consider the error in L2 norm.
So error goes down by a factor of up to 2.6,
which is very close to a theoretical maximum, which
is given by the interpolation error of sparse grids.
And I think it's really fascinating
if you have a look at the number of unknowns.
So for a lower depth, it's both handleable.
But if you increase the depth, we
have 10,600 unknowns for sparse grid with a depth of 6.
And the order of 10 power 10 unknowns for full grids.
And for full grids, we would have an error reduction by 4.
And here we have 2.61, which is not bad.
Well, let's have another problem.
And in this case, it's three-dimensional.
And omega is not really 0, 1 power 3,
since we have here a curve linear bounded domain.
So the x dimension has shifted by a sinus term.
And again, we have our problem where
we know the exact solution and calculate the error.
And now we are, for a three-dimensional problem,
the error reduction is even better,
since the logarithmic term is lower.
And we are approaching 3.4 for the infinity norm
and 3.3 for a 2 norm.
And in this case, I have the maximum depth of 9.
So if you compare the number of unknowns, we have 20,000.
And here, quite a lot more.
So finally, let me sum up my talk.
So I have introduced a new discretization
for elliptic differential equations
with a variable coefficient in three-dimensional space.
So d can be quite high.
Test problem was 6, but we also had problems
with order of 10 and more.
Yeah, the basic idea was to use sparse grids and pre-wavelengths.
So sparse grids have reduced the memory costs,
and pre-wavelengths gave us some orthogonality.
And then we introduced the theme of orthogonality property,
which was needed to also handle variable coefficients.
Yeah, and for these properties, we
developed an efficient matrix-vector multiplication.
So we skipped some parts, and we just
showed that this part can be skipped,
since we have this semi-orthogonality property.
And then we used the solver to simulate a 3D and a 6D problem.
And we also showed the convergence
case of variable coefficients, which was non-trivial.
And we had our variational crime there.
OK, what is still open is to have adaptive refinement.
And then I think adaptive refinement is the biggest gain
we got from Galerkin discretization.
So other methods, like combination technique,
do not allow adaptive refinement.
But so far, we did not use adaptive refinement.
We started developing it.
But we need a better data structure for that case
and have to adapt our algorithm a little bit.
And then we also want to simulate
more complex domains, like block-structured domains.
And yeah.
And finally, we need some kind of parallelization
for larger problems.
So that's why I stopped for sometimes a level of depth
of 10 and more, since we run out of memory.
OK, there can also be some improvements,
since we handled the boundary point.
And if you have boundary points included,
we have a higher amount of memory.
But nevertheless, parallelization,
I think it's a problem we should start now.
And I think it's promising and will speed up our algorithm,
because it easily can be separated and parallelized
by the two power D cases.
OK, thank you.
Thank you.

