Message Boards Message Boards

Parallel Computation of Fourier Transform and Integrate

Posted 10 years ago
I have a large symbolic equation that I must first integrate (continuous) over a closed domain (say from 0 to 1).  I then manipulate the output (and descretize it) and eventually take an inverse fourier transform.  I tried to set up a parallel computation by using Parallelize but it didn't reduce the computation time (currently on the order of a few hours).  I suspect that I am implementing the parallel computation incorrectly but can't seem to find anything that can walk me through setting it up.  Can someone explain to me how to set up this problem to reduce my run time?

Thank you.
POSTED BY: Eric Kjolsing
2 Replies
Also, generally built-in functions do not know about problem symmetries and properties.
Some times it is beneficial to create simplified versions of such functions, but with correct symmetries in mind.
As an example of such approach, once I had a problem to determine Fourier Coefficient of a function composed of different trigonometric functions.
The build-in FourierCoefficient[] will take forever in this case and it can't parallelized. Example:
 (* My FourierCoefficient for *)
 (* 2-Harmonic function coeffs. *)
 Expansion2D2F[function_, args_List] := Module[
    {FUNCTION, ARGS, OUTPUT = {__, __}, a, b, ZERO},
    {
     Parallelize[
      ARGS = args;
      ZERO = Coefficient[Expand[TrigToExp[function]] /. E^a_ -> b, b, 0];
      FUNCTION = List @@ Expand[Expand[TrigToExp[function]] - ZERO]
          /. a_ E^b_ -> {a, b} 
          /. {a_ ARGS[[1]] + b_ ARGS[[2]] -> {a, b}}
           /. {a_ ARGS[[1]] -> {a, 0}}
            /. {a_ ARGS[[2]] -> {0, a}} ;
     OUTPUT[[1]] =
      Join[Take[
        Flatten[FUNCTION, 1], {1, Length[Flatten[FUNCTION, 1]], 2}]];
     OUTPUT[[2]] =
      Join[Im[Take[
         Flatten[FUNCTION, 1], {2, Length[Flatten[FUNCTION, 1]], 2}]]];
     OUTPUT
     , Method -> "FinestGrained"]
    }];
In[3]:= f = A Cos[f1] Sin[2 f2] + B Sin[4 f1] Cos[3 f2] ;

In[4]:= (* EXAMPLE *)
Expansion2D2F[f, {f1, f2}][[1]] // AbsoluteTiming
Out[4]= {0.0170010, ...}

In[5]:= AbsoluteTiming[{FourierCoefficient[f, f1, n],FourierCoefficient[f, f2, m]}]
Out[5]= {0.2440139, ... }

I.M.
POSTED BY: Ivan Morozov
Hi,

I'm far from being an expert with Parallel computation with Mathematica, but here is what I can suggest.
Since you basically taking integrals (like Fourier Transform), why do not use their properties?
1) Int(x+y+z+...) = Int(x)+Int(y)+Int(z)+...
2) Int(f(x),{x,0,1}) = Int(f(x),{x,0,0.5})+Int(f(x),{x,0.5,1}) = ...
3) ...
The first property looks promising, you can decompose integrand that is a sum into a list and do integration for each part with ParallelSum[].
Here is an example:
 In[1]:= LaunchKernels[];
 
 In[2]:= (* LINEAR PARTS *)
 DATA = Table[Sin[n x], {n, 0, 200}];
 LENGTH = Length@DATA;
 
 In[4]:= f[x_] = Total@DATA;
 
 In[5]:= (* SEQUENTIAL *)
INTA =  AbsoluteTiming[N@Integrate[f[x], {x, 0.5, 1}]]

Out[5]= {74.5442637, 0.661469}

(* PARALLEL *)
INTB =  AbsoluteTiming[
  ParallelSum[
   Integrate[DATA[[i]], {x, 0.5, 1}]
   , {i, 1, LENGTH}
   ]]
{27.5205741, 0.661469}
Also try to use other Parallel commands than just Parallelize[], the latter, as I understand, is build on top of them.
The general strategy for SPMD-like programs is to understand how the problem can be decomposed into uncorrelated parts,
multiple copies of a program are then launched for each sub-set.

I.M.
POSTED BY: Ivan Morozov
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract