Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #11039 > unrolled thread

Can anyone see a faster way to compute quantities for a pair or large matrices?

Started byW Craig Carter <ccarter@MIT.EDU>
First post2012-07-23 05:04 +0000
Last post2012-07-26 07:38 +0000
Articles 9 — 5 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  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

#11039 — Can anyone see a faster way to compute quantities for a pair or large matrices?

FromW Craig Carter <ccarter@MIT.EDU>
Date2012-07-23 05:04 +0000
SubjectCan 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]


#11049 — Re: Can anyone see a faster way to compute quantities for a pair or

Fromdaniel.lichtblau0@gmail.com
Date2012-07-23 23:59 +0000
SubjectRe: 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&#39;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[{#}] &amp;, gradfield, 2];
> 
> 
> (*examples*)
> Do[psiField = MapThread[myArcTan, gradfield, 2], {100}] // Timing
> Do[magfield =  MapThread[Norm[{#}] &amp;, 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]


#11053

From"andre.robin3" <andre.robin281@orange.fr>
Date2012-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]


#11056 — Re: Can anyone see a faster way to compute quantities for a pair or

FromRay Koopman <koopman@sfu.ca>
Date2012-07-24 08:15 +0000
SubjectRe: 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]


#11057 — Re: Can anyone see a faster way to compute quantities for a pair or

FromRay Koopman <koopman@sfu.ca>
Date2012-07-24 08:16 +0000
SubjectRe: 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]


#11060 — Re: Can anyone see a faster way to compute quantities for a pair or

FromW Craig Carter <ccarter@MIT.EDU>
Date2012-07-25 06:34 +0000
SubjectRe: 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]


#11063

FromW Craig Carter <ccarter@MIT.EDU>
Date2012-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]


#11080 — Re: Can anyone see a faster way to compute quantities for a pair or

FromRay Koopman <koopman@sfu.ca>
Date2012-07-26 07:36 +0000
SubjectRe: 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]


#11084 — Re: Can anyone see a faster way to compute quantities for a pair or

FromSseziwa Mukasa <mukasa@gmail.com>
Date2012-07-26 07:38 +0000
SubjectRe: 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