Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #11039 > unrolled thread
| Started by | W Craig Carter <ccarter@MIT.EDU> |
|---|---|
| First post | 2012-07-23 05:04 +0000 |
| Last post | 2012-07-26 07:38 +0000 |
| Articles | 9 — 5 participants |
Back to article view | Back to comp.soft-sys.math.mathematica
Can anyone see a faster way to compute quantities for a pair or large matrices? W Craig Carter <ccarter@MIT.EDU> - 2012-07-23 05:04 +0000
Re: Can anyone see a faster way to compute quantities for a pair or daniel.lichtblau0@gmail.com - 2012-07-23 23:59 +0000
Re: Can anyone see a faster way to compute quantities for a pair or large matrices? "andre.robin3" <andre.robin281@orange.fr> - 2012-07-24 08:15 +0000
Re: Can anyone see a faster way to compute quantities for a pair or Ray Koopman <koopman@sfu.ca> - 2012-07-24 08:15 +0000
Re: Can anyone see a faster way to compute quantities for a pair or Ray Koopman <koopman@sfu.ca> - 2012-07-24 08:16 +0000
Re: Can anyone see a faster way to compute quantities for a pair or W Craig Carter <ccarter@MIT.EDU> - 2012-07-25 06:34 +0000
Re: Can anyone see a faster way to compute quantities for a pair or large matrices? W Craig Carter <ccarter@MIT.EDU> - 2012-07-25 06:31 +0000
Re: Can anyone see a faster way to compute quantities for a pair or Ray Koopman <koopman@sfu.ca> - 2012-07-26 07:36 +0000
Re: Can anyone see a faster way to compute quantities for a pair or Sseziwa Mukasa <mukasa@gmail.com> - 2012-07-26 07:38 +0000
| From | W Craig Carter <ccarter@MIT.EDU> |
|---|---|
| Date | 2012-07-23 05:04 +0000 |
| Subject | Can anyone see a faster way to compute quantities for a pair or large matrices? |
| Message-ID | <juim0j$k9a$1@smc.vnet.net> |
Hello,
I am computing the gradient on a grid, then computing the gradient's
angle, and its magnitude. The computations below are the bottleneck for
a longer bit of code. I would be grateful for any insights on how to
speed these up.
(*
Let gradfield be the gradient that I have computed and placed in two matrices. Here I will just use random numbers as a proxy:
*)
(*i.e., df/dx, df/dy*)
gradfield = { RandomReal[{-1, 1}, {256, 256}], RandomReal[{-1, 1}, {256, 256}]};
(*my gradients has many zeroes, so I need to handle these*)
SetAttributes[myArcTan, {Listable, NumericFunction}];
myArcTan[0.0, 0.0] = 0.0;
myArcTan[x_, y_] := ArcTan[x, y]
(*the angles, this is slow*)
psiField = MapThread[myArcTan, gradfield, 2];
(*the magnitudes, this is slower*)
magfield = MapThread[Norm[{#}] &, gradfield, 2];
(*examples*)
Do[psiField = MapThread[myArcTan, gradfield, 2], {100}] // Timing
Do[magfield = MapThread[Norm[{#}] &, gradfield, 2], {100}] // Timing
W Craig Carter
Professor of Materials Science, MIT
[toc] | [next] | [standalone]
| From | daniel.lichtblau0@gmail.com |
|---|---|
| Date | 2012-07-23 23:59 +0000 |
| Subject | Re: Can anyone see a faster way to compute quantities for a pair or |
| Message-ID | <jukogk$o1j$1@smc.vnet.net> |
| In reply to | #11039 |
On Monday, July 23, 2012 12:04:19 AM UTC-5, W Craig Carter wrote:
> Hello,
> I am computing the gradient on a grid, then computing the gradient's
> angle, and its magnitude. The computations below are the bottleneck for
> a longer bit of code. I would be grateful for any insights on how to
> speed these up.
>
> (*
> Let gradfield be the gradient that I have computed and placed in two matrices. Here I will just use random numbers as a proxy:
> *)
>
> (*i.e., df/dx, df/dy*)
> gradfield = { RandomReal[{-1, 1}, {256, 256}], RandomReal[{-1, 1}, {256, 256}]};
>
> (*my gradients has many zeroes, so I need to handle these*)
>
> SetAttributes[myArcTan, {Listable, NumericFunction}];
> myArcTan[0.0, 0.0] = 0.0;
> myArcTan[x_, y_] := ArcTan[x, y]
>
>
> (*the angles, this is slow*)
> psiField = MapThread[myArcTan, gradfield, 2];
>
> (*the magnitudes, this is slower*)
> magfield = MapThread[Norm[{#}] &, gradfield, 2];
>
>
> (*examples*)
> Do[psiField = MapThread[myArcTan, gradfield, 2], {100}] // Timing
> Do[magfield = MapThread[Norm[{#}] &, gradfield, 2], {100}] // Timing
>
> W Craig Carter
> Professor of Materials Science, MIT
Could use Compile to get a speed improvement. below shows one way to go about this.
In[445]:= myArcTanC2 = Compile[{{xy, _Real, 1}},
With[{x = xy[[1]], y = xy[[2]]},
If[x == 0. && y == 0., 0., ArcTan[x, y]]]];
In[452]:= psiFieldFinder = Compile[{{gfield, _Real, 3}},
Map[myArcTanC2, Transpose[gfield, {3, 1, 2}], {2}],
CompilationOptions -> {"ExpressionOptimization" -> True,
"InlineCompiledFunctions" -> True},
CompilationTarget -> "C"];
In[453]:= Do[psiField2 = psiFieldFinder[gradfield], {100}] // Timing
Out[453]= {0.85, Null}
If you intend to do this on the same array then pre-transposing, and removing that step from the compiled function, might give a further slight improvement.
For norms you might get better speed using Sqrt[arg1.arg2].
Daniel Lichtblau
Wolfram Research
[toc] | [prev] | [next] | [standalone]
| From | "andre.robin3" <andre.robin281@orange.fr> |
|---|---|
| Date | 2012-07-24 08:15 +0000 |
| Message-ID | <julljf$pt3$1@smc.vnet.net> |
| In reply to | #11039 |
Your problem is a good candidate for parallel computing.
It can be :
1) multi-kernel computing (with Mathematica 7 or Mathematica 8). It's easy to implement.
Of course, it needs a multi-core machine.
2) GPGPU computing (with Mathmatica 8)
It needs a Graphic Card with CUDA or OPENCL capabilities.
I can try 1) or 2) with CUDA.
Are you interested ?
"W Craig Carter" <ccarter@MIT.EDU> a écrit dans le message de news:
juim0j$k9a$1@smc.vnet.net...
>
> Hello,
> I am computing the gradient on a grid, then computing the gradient's
> angle, and its magnitude. The computations below are the bottleneck for
> a longer bit of code. I would be grateful for any insights on how to
> speed these up.
>
> (*
> Let gradfield be the gradient that I have computed and placed in two
> matrices. Here I will just use random numbers as a proxy:
> *)
>
> (*i.e., df/dx, df/dy*)
> gradfield = { RandomReal[{-1, 1}, {256, 256}], RandomReal[{-1, 1}, {256,
> 256}]};
>
> (*my gradients has many zeroes, so I need to handle these*)
>
> SetAttributes[myArcTan, {Listable, NumericFunction}];
> myArcTan[0.0, 0.0] = 0.0;
> myArcTan[x_, y_] := ArcTan[x, y]
>
>
> (*the angles, this is slow*)
> psiField = MapThread[myArcTan, gradfield, 2];
>
> (*the magnitudes, this is slower*)
> magfield = MapThread[Norm[{#}] &, gradfield, 2];
>
>
> (*examples*)
> Do[psiField = MapThread[myArcTan, gradfield, 2], {100}] // Timing
> Do[magfield = MapThread[Norm[{#}] &, gradfield, 2], {100}] // Timing
>
> W Craig Carter
> Professor of Materials Science, MIT
[toc] | [prev] | [next] | [standalone]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2012-07-24 08:15 +0000 |
| Subject | Re: Can anyone see a faster way to compute quantities for a pair or |
| Message-ID | <jullig$psh$1@smc.vnet.net> |
| In reply to | #11039 |
On Jul 22, 10:04 pm, W Craig Carter <ccar...@MIT.EDU> wrote:
> Hello,
> I am computing the gradient on a grid, then computing the gradient's
> angle, and its magnitude. The computations below are the bottleneck for
> a longer bit of code. I would be grateful for any insights on how to
> speed these up.
>
> (*
> Let gradfield be the gradient that I have computed and placed in two matrices. Here I will just use random numbers as a proxy:
> *)
>
> (*i.e., df/dx, df/dy*)
> gradfield = { RandomReal[{-1, 1}, {256, 256}], RandomReal[{-1, 1}, {256, 256}]};
>
> (*my gradients has many zeroes, so I need to handle these*)
>
> SetAttributes[myArcTan, {Listable, NumericFunction}];
> myArcTan[0.0, 0.0] = 0.0;
> myArcTan[x_, y_] := ArcTan[x, y]
>
> (*the angles, this is slow*)
> psiField = MapThread[myArcTan, gradfield, 2];
>
> (*the magnitudes, this is slower*)
> magfield = MapThread[Norm[{#}] &, gradfield, 2];
>
> (*examples*)
> Do[psiField = MapThread[myArcTan, gradfield, 2], {100}] // Timing
> Do[magfield = MapThread[Norm[{#}] &, gradfield, 2], {100}] // Timing
>
> W Craig Carter
> Professor of Materials Science, MIT
Do[magfield = MapThread[Norm[{##}]&, gradfield, 2], {100}] // Timing
Do[magfield2 = Sqrt[Plus@@(gradfield^2)], {100}] // Timing
Max@Abs[magfield - magfield2]
{72.02 Second, Null}
{2.31 Second, Null}
2.220446049250313`*^-16
Do[psifield = MapThread[myArcTan, gradfield, 2], {100}] // Timing
Do[psifield2 = ArcTan@@{gradfield[[1]], gradfield[[2]] +
UnitStep[-magfield2]}, {100}] // Timing
Max@Abs[psifield - psifield2]
{56.07 Second, Null}
{2.56 Second, Null}
0.
[toc] | [prev] | [next] | [standalone]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2012-07-24 08:16 +0000 |
| Subject | Re: Can anyone see a faster way to compute quantities for a pair or |
| Message-ID | <julllb$ptk$1@smc.vnet.net> |
| In reply to | #11039 |
On Jul 22, 10:04 pm, W Craig Carter <ccar...@MIT.EDU> wrote:
> Hello,
> I am computing the gradient on a grid, then computing the gradient's
> angle, and its magnitude. The computations below are the bottleneck for
> a longer bit of code. I would be grateful for any insights on how to
> speed these up.
>
> (*
> Let gradfield be the gradient that I have computed and placed in two matrices. Here I will just use random numbers as a proxy:
> *)
>
> (*i.e., df/dx, df/dy*)
> gradfield = { RandomReal[{-1, 1}, {256, 256}], RandomReal[{-1, 1}, {256, 256}]};
>
> (*my gradients has many zeroes, so I need to handle these*)
>
> SetAttributes[myArcTan, {Listable, NumericFunction}];
> myArcTan[0.0, 0.0] = 0.0;
> myArcTan[x_, y_] := ArcTan[x, y]
>
> (*the angles, this is slow*)
> psiField = MapThread[myArcTan, gradfield, 2];
>
> (*the magnitudes, this is slower*)
> magfield = MapThread[Norm[{#}] &, gradfield, 2];
>
> (*examples*)
> Do[psiField = MapThread[myArcTan, gradfield, 2], {100}] // Timing
> Do[magfield = MapThread[Norm[{#}] &, gradfield, 2], {100}] // Timing
>
> W Craig Carter
> Professor of Materials Science, MIT
My previous post should have said
psifield2 = ArcTan@@{gradfield[[1]] + UnitStep[-magfield2],
gradfield[[2]]}
(ArcTan with two arguments is not like atan2. Old habits die hard!)
[toc] | [prev] | [next] | [standalone]
| From | W Craig Carter <ccarter@MIT.EDU> |
|---|---|
| Date | 2012-07-25 06:34 +0000 |
| Subject | Re: Can anyone see a faster way to compute quantities for a pair or |
| Message-ID | <juo420$17n$1@smc.vnet.net> |
| In reply to | #11039 |
Thanks to Ray, Dan, Sseziwa, Andre, and David Park (offline response)
for their suggestions which improve computation time by about a factor
of 100.
I am very curious what is going on under the hood that makes my original
method (pasted again below) using MapThread so inefficient compared to
the better solutions (i.e., using Apply and Map solutions not the
Compile solution). This seems a good learning--and
teaching--opportunity.
(*original posting, the myArcTan is not the real culprit (btw, I am very
impressed with Ray's UnitStep trick*)
(* original inefficient posted method*)
gradfield = { RandomReal[{-1, 1}, {256, 256}], RandomReal[{-1, 1},
{256, 256}]};
SetAttributes[myArcTan, {Listable, NumericFunction}];
myArcTan[0.0, 0.0] = 0.0;
myArcTan[x_, y_] := ArcTan[x, y]
(*the angles, this is slow*)
psiField = MapThread[myArcTan, gradfield, 2];
(*the magnitudes, this is slower*)
magfield = MapThread[Norm[{#}] &, gradfield, 2];
>
> psifield2 = ArcTan@@{gradfield[[1]] + UnitStep[-magfield2],
> gradfield[[2]]}
[toc] | [prev] | [next] | [standalone]
| From | W Craig Carter <ccarter@MIT.EDU> |
|---|---|
| Date | 2012-07-25 06:31 +0000 |
| Message-ID | <juo3ra$14u$1@smc.vnet.net> |
| In reply to | #11039 |
Thank you Andre,
I did do a version using ParallelTable and that give me some speed up.
But, mostly, I am trying to develop techniques for teaching
Mathematica's more advanced constructs. This was a good lesson. I am
trying to understand why my MapThread solution was so slow.
Thank you for your kind offer for help. I tried for about an hour or so
about a year ago, but I wasn't able to get CUDA to work on my mac laptop
(with which I use to teach and give seminars). If I remember
correctly, the message I get implies that it doesn't work with my
graphics card.(AMD Radeon HD 6770M 1024 M).
I would **very much** like to see an example of how to get it to work;
more to the point, I am hopeful that that I can get an fft (Fourier[])
to use the GPU on a depth 3 array (e.g., RandomReal[{0,1} ,
{nx,ny,nz}]. I am developing a spectral methods example for a course
that I am teaching.
Thank you, Craig
W Craig Carter
Professor of Materials Science, MIT
On Jul 24, , at Tue Jul 24, 12 @4:14 AM, andre.robin3 wrote:
> Your problem is a good candidate for parallel computing.
>
> It can be :
>
> 1) multi-kernel computing (with Mathematica 7 or Mathematica 8). It's
easy to implement.
> Of course, it needs a multi-core machine.
>
> 2) GPGPU computing (with Mathmatica 8)
> It needs a Graphic Card with CUDA or OPENCL capabilities.
>
> I can try 1) or 2) with CUDA.
>
> Are you interested ?
>
>
>
> "W Craig Carter" <ccarter@MIT.EDU> a =E9crit dans le message de news:
> juim0j$k9a$1@smc.vnet.net...
>>
>> Hello,
>> I am computing the gradient on a grid, then computing the gradient's
>> angle, and its magnitude. The computations below are the bottleneck for
>> a longer bit of code. I would be grateful for any insights on how to
>> speed these up.
>>
>> (*
>> Let gradfield be the gradient that I have computed and placed in two
>> matrices. Here I will just use random numbers as a proxy:
>> *)
>>
>> (*i.e., df/dx, df/dy*)
>> gradfield = { RandomReal[{-1, 1}, {256, 256}], RandomReal[{-1, 1}, {256,
>> 256}]};
>>
>> (*my gradients has many zeroes, so I need to handle these*)
>>
>> SetAttributes[myArcTan, {Listable, NumericFunction}];
>> myArcTan[0.0, 0.0] = 0.0;
>> myArcTan[x_, y_] := ArcTan[x, y]
>>
>>
>> (*the angles, this is slow*)
>> psiField = MapThread[myArcTan, gradfield, 2];
>>
>> (*the magnitudes, this is slower*)
>> magfield = MapThread[Norm[{#}] &, gradfield, 2];
>>
>>
>> (*examples*)
>> Do[psiField = MapThread[myArcTan, gradfield, 2], {100}] // Timing
>> Do[magfield = MapThread[Norm[{#}] &, gradfield, 2], {100}] // Timing
>>
>> W Craig Carter
>> Professor of Materials Science, MIT
>
>
>
[toc] | [prev] | [next] | [standalone]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2012-07-26 07:36 +0000 |
| Subject | Re: Can anyone see a faster way to compute quantities for a pair or |
| Message-ID | <juqs15$66q$1@smc.vnet.net> |
| In reply to | #11039 |
On Jul 24, 11:34 pm, W Craig Carter <ccar...@MIT.EDU> wrote:
> Thanks to Ray, Dan, Sseziwa, Andre, and David Park (offline response)
> for their suggestions which improve computation time by about a factor
> of 100.
>
> I am very curious what is going on under the hood that makes my original
> method (pasted again below) using MapThread so inefficient compared to
> the better solutions (i.e., using Apply and Map solutions not the
> Compile solution). This seems a good learning--and
> teaching--opportunity.
>
> (*original posting, the myArcTan is not the real culprit (btw, I am very
> impressed with Ray's UnitStep trick*)
>
> (* original inefficient posted method*)
> gradfield = { RandomReal[{-1, 1}, {256, 256}], RandomReal[{-1, 1},
> {256, 256}]};
>
> SetAttributes[myArcTan, {Listable, NumericFunction}];
> myArcTan[0.0, 0.0] = 0.0;
> myArcTan[x_, y_] := ArcTan[x, y]
>
> (*the angles, this is slow*)
> psiField = MapThread[myArcTan, gradfield, 2];
>
> (*the magnitudes, this is slower*)
> magfield = MapThread[Norm[{#}] &, gradfield, 2];
>
>
>
>> psifield2 = ArcTan@@{gradfield[[1]] + UnitStep[-magfield2],
>> gradfield[[2]]}
I can only speculate about why the original code is slow,
but I can offer informed advice about how to keep my code
running fast: gradfield must be a packed array.
Also, my code for the angles can be simplified slightly,
with no change in speed:
psifield2 = ArcTan[gradfield[[1]] + UnitStep[-magfield2],
gradfield[[2]]]
[toc] | [prev] | [next] | [standalone]
| From | Sseziwa Mukasa <mukasa@gmail.com> |
|---|---|
| Date | 2012-07-26 07:38 +0000 |
| Subject | Re: Can anyone see a faster way to compute quantities for a pair or |
| Message-ID | <juqs4u$67m$1@smc.vnet.net> |
| In reply to | #11039 |
I can only guess as to what's under the hood, but I suspect it's
something like this:
- MapThread can't know the depth of the result, since the function being
mapped may return a non-atomic result. So it can't allocate the space
to contain the result, or it allocates space to the depth it knows about
from its second and third arguments, then uses a pointer to hold the
result.
- It then computes the values by mapping the function across the second
argument of MapThread. If it did not pre-allocate the space then every
result has to be inserted into the result using a Join like operation
which is known to be slow. Otherwise it still has to allocate space to
hold the result and each allocation takes time.
To demonstrate this idea I ran the following test for which it takes
several seconds to do 100 iterations of MapThread on a 256x256x2 array:
(Debug) In[49]:= data = RandomReal[{-1., 1}, {2, 256, 256}];
(Debug) In[61]:= Do[MapThread[0. &, data, 2], {100}] // Timing
(Debug) Out[61]= {11.5296, Null}
Ray's solution is faster because the interpreter is optimized to handle
the case of threading ArcTan. Making a user defined listable, numeric
function is not as efficient:
(Debug) In[62]:= returnZero[x_, y_] := 0.
SetAttributes[returnZero, {Listable, NumericFunction}];
(Debug) In[64]:= Do[returnZero @@ data, {100}] // Timing
Do[ArcTan @@ data, {100}] // Timing
(Debug) Out[64]= {10.4257, Null}
(Debug) Out[65]= {0.191412, Null}
If there's a teachable moment in this I suppose it's use the built-in
listable numeric functions instead of Map, Apply etc. whenever possible.
Regards,
Sseziwa
On Jul 25, 2012, at 2:32 AM, W Craig Carter wrote:
> Thanks to Ray, Dan, Sseziwa, Andre, and David Park (offline response)
> for their suggestions which improve computation time by about a factor
> of 100.
>
> I am very curious what is going on under the hood that makes my
original
> method (pasted again below) using MapThread so inefficient compared
to
> the better solutions (i.e., using Apply and Map solutions not the
> Compile solution). This seems a good learning--and
> teaching--opportunity.
>
> (*original posting, the myArcTan is not the real culprit (btw, I am
very
> impressed with Ray's UnitStep trick*)
>
>
> (* original inefficient posted method*)
> gradfield = { RandomReal[{-1, 1}, {256, 256}], RandomReal[{-1, 1},
> {256, 256}]};
>
> SetAttributes[myArcTan, {Listable, NumericFunction}];
> myArcTan[0.0, 0.0] = 0.0;
> myArcTan[x_, y_] := ArcTan[x, y]
>
> (*the angles, this is slow*)
> psiField = MapThread[myArcTan, gradfield, 2];
>
> (*the magnitudes, this is slower*)
> magfield = MapThread[Norm[{#}] &, gradfield, 2];
>
>
>
>>
>> psifield2 = ArcTan@@{gradfield[[1]] + UnitStep[-magfield2],
>> gradfield[[2]]}
>
>
>
[toc] | [prev] | [standalone]
Back to top | Article view | comp.soft-sys.math.mathematica
csiph-web