<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>Yes, It seems I am wrong and you are right.</p>
<p>I think I can then make electric and magnetic fields local and do
parallel partitioning only in v space - it will defiantly restrict
the problem size, but maybe the code still be still useful and I
get petsc experience with it :) The question here if I will just
parallize along v-space, the 3d DMDA should be enough, right? I do
not really understand how would I do the partitioning here, can
you please give me some hints?</p>
<p>Another approach is to abandon global Fourier, let say for
education purposes I will pick some finite difference along
spacial dimensions, how would you advice me to partition this
problem with PETSc then?</p>
<p><br>
</p>
<p>I know something like spectral elements or discontinuous Galerkin
will be ideal, but I want to get petsc experience first with
simpler problem and then move to discontinuous Galerkin (this will
be defiantly the next step). (Unfortunately, I have never done any
unstructured meshes like spectral elements or discontinuous
Galerkin myself before, but did some finite difference and
spectral methods)<br>
</p>
<br>
<div class="moz-cite-prefix">On 07/30/2017 12:46 PM, Matthew Knepley
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAMYG4Gk51m7YVXyVP2KjPQG6QaqcyKwvi9k10rgFSJC8bc+4dw@mail.gmail.com">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">On Sun, Jul 30, 2017 at 12:44 PM,
Oleksandr Koshkarov <span dir="ltr"><<a
href="mailto:olk548@mail.usask.ca" target="_blank"
moz-do-not-send="true">olk548@mail.usask.ca</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<p>Thanks for the references, and warning.</p>
<p>I am trying to do exactly this<br>
</p>
<p><a
class="m_-2170408591196595834moz-txt-link-freetext"
href="http://www.sciencedirect.com/science/article/pii/S0021999115004738"
target="_blank" moz-do-not-send="true">http://www.sciencedirect.com/<wbr>science/article/pii/<wbr>S0021999115004738</a></p>
<p>(I probably should have added the reference in the
first place, sorry)</p>
<p>the evolution formula is (15) in the article.</p>
<p>So, I will do convolution only in 3D (while full
system is 6D) because velocity space is not
discretized with Fourier</p>
<p>So As I understand, it will not be N^2 vs N logN.
Moreover, I know that algorithm with FFT has
significantly larger "constant".</p>
<p>Please correct me if I am wrong here :)</p>
</div>
</blockquote>
<div>I think you are wrong here. First, I do not understand
why you think the asymptotics have changed. Second, the
constant for</div>
<div>FFT is about 6, which would be really hard to beat with
a quadrature.</div>
<div><br>
</div>
<div>Last, this discretization looks fully coupled to me. I
cannot see how you would parallelize this right off the
bat. This is a problem</div>
<div>with spectral discretizations, and the main motivator
for spectral elements.</div>
<div><br>
</div>
<div> Thanks,</div>
<div><br>
</div>
<div> Matt</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<p>I know for sure that FFT is a must at the end, but I
thought I can start with matrix product to get more
familiar with PETSc as it will be simpler to implement
(At least I think so).</p>
<p>I hope it does make sense.</p>
<p>Another question about convolution via matrix
product. Is there better way to do it other then to
construct NxN Toeplitz-like matrix each time step on
the "fly" from state vector and then multiply it to
state vector?</p>
<p>p.s. Probably I should do FFT from the start, but I
am a little bit intimidated by the problem taking into
account that I do not have PETSc experience.<br>
</p>
Best regards,<br>
Oleksandr Koshkarov.<br>
<br>
<div class="m_-2170408591196595834moz-cite-prefix">On
07/30/2017 09:01 AM, Matthew Knepley wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">On Sat, Jul 29, 2017 at
7:01 PM, Oleksandr Koshkarov <span dir="ltr"><<a
href="mailto:olk548@mail.usask.ca"
target="_blank" moz-do-not-send="true">olk548@mail.usask.ca</a>></span>
wrote:<br>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">Thank you
for the response,<br>
<br>
Now that you said about additional
communication for fft, I want to ask another
question:<br>
<br>
What if I disregard FFT and will compute
convolution directly, I will rewrite it as
vector-matrix-vector product<br>
</blockquote>
<div><br>
</div>
<div> I would caution you here. The algorithm is
the most important thing to get right up
front. In this case, the effect of</div>
<div>dimension will be dominant, and anything
that does not scale well with dimension will
be thrown away, perhaps</div>
<div>quite quickly, as you want to solve bigger
problems.</div>
<div><br>
</div>
<div>Small calculation: Take a 6-dim box which
is 'n' on a side, so that N = n^6. FFT is N
log N, whereas direct evaluation of</div>
<div>a convolution is N^2. So if we could do n =
100 points on a side with FFT, you can do,
assuming the constants are about</div>
<div>equal,</div>
<div><br>
</div>
<div> 100^6 (log 100^6) = x^12</div>
<div> 1e12 (6 2) = x^12</div>
<div> x ~ 10</div>
<div><br>
</div>
<div>Past versions of PETSc had a higher
dimensional DA construct (adda in prior
versions), but no one used it so we removed
it.</div>
<div><br>
</div>
<div>I assume you are proposing something like</div>
<div><br>
</div>
<div> <a href="https://arxiv.org/abs/1306.4625"
target="_blank" moz-do-not-send="true">https://arxiv.org/abs/1306.<wbr>4625</a></div>
<div><br>
</div>
<div>or maybe </div>
<div><br>
</div>
<div> <a
href="https://arxiv.org/abs/1610.00397"
target="_blank" moz-do-not-send="true">https://arxiv.org/abs/1610.<wbr>00397</a></div>
<div><br>
</div>
<div>The later is interesting since I think you
could use a DMDA for the velocity and
something like DMPlex for the space.</div>
<div><br>
</div>
<div> Thanks,</div>
<div><br>
</div>
<div> Matt</div>
<div> </div>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex"> x^T A x
(where T - is transpose, x - is my state
vector, and A is a matrix which represents
convolution and probably it will be not very
sparse).<br>
<br>
Yes - I will do more work (alghorithm will be
slower), but will I win if we take the
parallelization into account - less
communication + probably more scalable
algorithm?<br>
<br>
Best regards,<br>
<br>
Alex.
<div
class="m_-2170408591196595834gmail-m_6801210051757406332HOEnZb">
<div
class="m_-2170408591196595834gmail-m_6801210051757406332h5"><br>
<br>
<br>
On 07/29/2017 05:23 PM, Barry Smith wrote:<br>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
DMDA provides a simple way to do domain
decomposition of structured grid meshes
in the x, y, and z direction, that is it
makes it easy to efficiently chop up
vectors in all 3 dimensions, allowing
very large problems easily.
Unfortunately it only goes up to 3
dimensions and attempts to produce
versions for higher dimensions have
failed.<br>
<br>
If you would like to do domain
decomposition across all six of your
dimensions (which I think you really
need to do to solve large problems) we
don't have a tool that helps with doing
the domain decomposition. To make
matters more complicated, likely the 3d
mpi-fftw that need to be applied require
rejiggering the data across the nodes to
get it into a form where the ffts can be
applied efficiently.<br>
<br>
I don't think there is necessarily
anything theoretically difficult about
managing the six dimensional domain
decomposition I just don't know of any
open source software out there that
helps to do this. Maybe some PETSc users
are aware of such software and can chime
in.<br>
<br>
Aside from these two issues :-)
PETSc would be useful for you since you
could use our time integrators and
nonlinear solvers. Pulling out
subvectors to process on can be done
with with either VecScatter or
VecStrideScatter, VecStrideGather etc
depending on the layout of the unknowns,
i.e. how the domain decomposition is
done.<br>
<br>
I wish I had better answers for
managing the 6d domain decomposition<br>
<br>
Barry<br>
<br>
<br>
<br>
<br>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex"> On
Jul 29, 2017, at 5:06 PM, Oleksandr
Koshkarov <<a
href="mailto:olk548@mail.usask.ca"
target="_blank"
moz-do-not-send="true">olk548@mail.usask.ca</a>>
wrote:<br>
<br>
Dear All,<br>
<br>
I am a new PETSc user and I am still
in the middle of the manual (I have
finally settled to choose PETSc as my
main numerical library) so I am sorry
beforehand if my questions would be
naive.<br>
<br>
I am trying to solve 6+1 dimensional
Vlasov equation with spectral methods.
More precisely, I will try to solve
half-discretized equations of the form
(approximate form) with pseudospectral
Fourier method:<br>
<br>
(Equations are in latex format, the
nice website to see them is <a
href="https://www.codecogs.com/latex/eqneditor.php"
rel="noreferrer" target="_blank"
moz-do-not-send="true">https://www.codecogs.com/latex<wbr>/eqneditor.php</a>)<br>
<br>
\frac{dC_{m,m,p}}{dt} =\\<br>
\partial_x \left ( a_n C_{n+1,m,p}
+b_n C_{n,m,p} +c_n C_{n-1,m,p} \right
) \\<br>
+ \partial_y \left ( a_m C_{n,m+1,p}
+b_m C_{n,m,p} +c_m C_{n,m-1,p}
\right ) \\<br>
+ \partial_z \left ( a_p C_{n,m,p+1}
+b_p C_{n,m,p} +c_p C_{n,m,p-1}
\right ) \\<br>
+ d_n E_x C_{n-1,m,p} + d_m E_x
C_{n,m-1,p} + d_p E_x C_{n,m,p-1} \\<br>
+ B_x (e_{m,p} C_{n,m-1,p-1} +
f_{m,p}C_{n,m-1,p+1} + \dots) + B_y
(\dots) + B_z (\dots)<br>
<br>
<br>
where a,b,c,d,e,f are some constants
which can depend on n,m,p,<br>
<br>
n,m,p = 0...N,<br>
<br>
C_{n,m,p} = C_{n,m,p}(x,y,z),<br>
<br>
E_x = E_x(x,y,z), (same for
E_y,B_x,...)<br>
<br>
and fields are described with equation
of the sort (linear pdes with source
terms dependent on C):<br>
<br>
\frac{dE_x}{dt} = \partial_y B_z -
\partial_z B_x + (AC_{1,0,0} +
BC_{0,0,0}) \\<br>
\frac{dB_x}{dt} = -\partial_y E_z +
\partial_z E_x<br>
<br>
with A,B being some constants.<br>
<br>
I will need fully implicit
Crank–Nicolson method, so my plan is
to use SNES or TS where<br>
<br>
I will use one MPI PETSc vector which
describes the state of the system
(all, C, E, B), then I can evolve
linear part with just matrix
multiplication.<br>
<br>
The first question is, should I use
something like DMDA? if so, it is only
3dimensional but I need 6 dimensional
vectots? Will it be faster then matrix
multiplication?<br>
<br>
Then to do nonlinear part I will need
3d mpi-fftw to compute convolutions.
The problem is, how do I extract
subvectors from full big vector state?
(what is the best approach?)<br>
<br>
If you have some other suggestions,
please feel free to share<br>
<br>
Thanks and best regards,<br>
<br>
Oleksandr Koshkarov.<br>
<br>
</blockquote>
</blockquote>
<br>
</div>
</div>
</blockquote>
</div>
<br>
<br clear="all">
<span class="HOEnZb"><font color="#888888">
<div><br>
</div>
-- <br>
<div
class="m_-2170408591196595834gmail-m_6801210051757406332gmail_signature">
<div dir="ltr">
<div>What most experimenters take for
granted before they begin their
experiments is infinitely more
interesting than any results to which
their experiments lead.<br>
-- Norbert Wiener</div>
<div><br>
</div>
<div><a
href="http://www.caam.rice.edu/%7Emk51/"
target="_blank" moz-do-not-send="true">http://www.caam.rice.edu/~mk51<wbr>/</a><br>
</div>
</div>
</div>
</font></span></div>
</div>
</blockquote>
<br>
</div>
</blockquote>
</div>
<br>
<br clear="all">
<div><br>
</div>
-- <br>
<div class="gmail_signature" data-smartmail="gmail_signature">
<div dir="ltr">
<div>What most experimenters take for granted before they
begin their experiments is infinitely more interesting
than any results to which their experiments lead.<br>
-- Norbert Wiener</div>
<div><br>
</div>
<div><a href="http://www.caam.rice.edu/%7Emk51/"
target="_blank" moz-do-not-send="true">http://www.caam.rice.edu/~mk51/</a><br>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<br>
</body>
</html>