MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Particular structure 2

  • To: mathgroup at smc.vnet.net
  • Subject: [mg33713] Re: [mg33627] Re: Particular structure 2
  • From: Yas <yast at optushome.com.au>
  • Date: Mon, 8 Apr 2002 03:04:52 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

Dear Allan and Hartmut,
   Thank you very much for your replies to my questions and the solutions 
you have provided. As has been pointed out, a best solution is hardly 
feasible without further details on the problem. The last reply from 
Allan ([mg33656]) containing the construct;

    x= y=Table[1,{400}];f=Plus;F= Times;

     Table[ReleaseHold[F@@#],{j, Length[y]}]&[
       Table[f[x[[i]],Hold[y[[j]]],z],{i,Length[x]}]];//Timing

is again another factor of two improvement in terms of speed but 
slightly less efficient than Hartmut Wolfs Case 6 (mg33657),

Plus @@ Map[Function[{yy}, Evaluate[F[Map[Function[{x}, f[x, yy, z]], 
x]]]], y] // Timing

in terms of memory use.

I was particularly encouraged by the speed of Thread, but unfortunately 
the structure of the resulting matrix gets jumbled up. I couldn't see a 
way around it. Transpose restructures it in a way where the 3x3 and 6x6 
relations get messed up.

   In my problem (the simplest case) f is the equivalent of a 3x3 matrix 
and is defined as, evalmat[x_,y_,z_] = mat[x, y, z], and mat has been 
built up from matrix elements containing functions depending on x, y and 
z. For fixed values of y and z and with x, a list of 500 or more 
elements, I use Fold or FoldList to construct a final vector or a list 
of vectors. So the new vector, newvec = Fold[#2.#1&, vec, g1], where vec 
={0,0,1} usually, and g1 is a list built by mapping x onto evalmat (g1 = 
evalmat[#, y, z]&/@x). Incidentally I found using Outer to be slightly 
quicker for mapping x onto evalmat with y held fixed which has had me 
stumped as to why.

   For the same list of x values and with y now variable as well my 
natural inclination was to create a large array of g1's with 
incrementing y which can be done by adapting either of the two 
constructs above,

e.g.   g1= Map[Function[{yy}, Evaluate[Map[Function[{x}, evalmat[x, yy, 
z]], x]]], y]
or      g1 = Table[ReleaseHold[#],{j, Length[y]}]&[
           Table[evalmat[x[[i]],Hold[y[[j]]],z],{i,Length[x]}]];

The building and evaluation of g1 is the slowest part if y is variable 
as well, and for sufficient resolution where any spurious jumps are 
avoided the number of increments of y has to be large, usually > 256 
points. But once g1 is built, and because the Fold part is fast the 
construct below is not limiting.

            profile = Table[Fold[#2.#1&, vec, g1[[k]]], {k, Length[y]}];

The elements of the vector can be extracted and plotted.

    Now that all this has been achieved, I immediately applied it to a 
larger matrix (6x6) only to find that I am back to square one in terms 
of time and memory. In the 3x3 case all the matrix elements have set 
delayed assignment and the functions inside the elements of the matrix 
also have delayed assignment. The matrix mat is also delayed but I 
figure using evalmat, rather than mat overcomes re-evaluation for each 
new x, y or z. Replacing := with = for the matrix element definitions 
and mat so that they are evaluated immediately did not seem to make a 
difference to the evaluation times, so what else can be done to improve 
the time for evaluation.


Regards

Yas




Dear Allan,
>
> I was let to ponder for a while why you held F in the Map over x. 
> Without
> knowing more details of the problem, a "best solution" can hardly be
> proposed. Of course there might be cases where the evaluation of F 
> might go
> astray unless the values y[[i]] are inserted. But normally, in the 
> interest
> of memory consumption and performance (partial) evaluation should be 
> done as
> early as possible.
>
>
> Here are some of my observations:
>
> (1) reproducing your case above
>
> In[1]:=
> x = y = Table[1, {400}]; f = Plus; g = Times @@ # &; z = 1;
>
> In[2]:=
> MemoryInUse[]
>
> Plus @@ Table[Function[yy, ReleaseHold[#]][y[[i]]], {i, Length[y]}] &[
>     Hold[g][f[#, yy, z] & /@ x]] // Timing
>
> MaxMemoryUsed[]
>
>
> Out[2]= 1275144
> Out[3]= {3.726 Second, \
> 2822031643462133028498570863037391848660317984511492630514848928370483422063
> 31\
> 7366263171941177885366326198093393014236474677191722872982667765803378181410
> 28\
> 11184114129504125276977313333635200400}
> Out[4]= 1358768
> In[5]:= Quit[]
>
> (I finally applied Plus just to check for check for correctness)
>
>
>
> (2) same with F (called g here) not held:
>
> Allan Hayes (not held)
>
> In[2]:=
> MemoryInUse[]
>
> Plus@@Table[Function[yy,#][y[[i]]],{i,Length[y]}]&[g[f[#,yy,z]&/@x]]//Timing
>
> MaxMemoryUsed[]
>
>
>
> Out[2]= 1274896
>
> Out[3]= {0.261 Second, =dito= }
>
> Out[4]= 1350856
>
> This is very fast (a little bit surprisingly to me).
>
>
> (3) The mapping over x (and evaluation of g) certainly should be done
> outside of the "inner loop" so to say. So this must be much slower:
>
> In[2]:=
> MemoryInUse[]
>
> Plus@@Table[Function[yy,g[f[#,yy,z]&/@x]][y[[i]]],{i,Length[y]}]//Timing
>
> MaxMemoryUsed[]
>
>
>
> Out[2]= 1274624
>
> Out[3]= {8.663 Second, =dito=}
>
> Out[4]= 1350856
>
>
> (4) However I was astonished about this being even slower:
>
> In[2]:=
> MemoryInUse[]
>
> Plus@@Table[g[f[#,y[[i]],z]&/@x],{i,Length[y]}]//Timing
>
> MaxMemoryUsed[]
>
>
>
> Out[2]= 1274256
>
> Out[3]= {14.792 Second, =dito=}
>
> Out[4]= 1350856
>
> Have you got an idea why?
>
>
> (5) A natural idea would be to use nested Maps:
>
> In[2]:=
> MemoryInUse[]
>
> (Plus @@ Map[Function[{y}, g[Map[Function[{x}, f[x, y, z]], x]]],
>         y]) // Timing
>
> MaxMemoryUsed[]
>
>
> Out[2]= 1274736
> Out[3]= {12.248 Second, =dito= }
> Out[4]= 1358512
>
> While this is economic on memory, performance is bad (on grounds stated
> above).
>
>
> (6) Evaluating the body of the Function definition improves that
> considerably:
>
> In[2]:=
> MemoryInUse[]
>
> Plus @@ Map[Function[{yy}, Evaluate[g[Map[Function[{x}, f[x, yy, z]], 
> x]]]],
>
>       y] // Timing
>
> MaxMemoryUsed[]
>
> Out[2]= 1274600
> Out[3]= {0.241 Second, =dito= }
> Out[4]= 1350856
>
>
> (7) The best result I attained, however was using Thread instead of the
> inner Map:
>
> In[2]:=
> MemoryInUse[]
>
> Plus @@ (Evaluate[g[Thread[f[x, #, z]]]] &) /@ y // Timing
>
> MaxMemoryUsed[]
>
>
> Out[2]= 1274040
> Out[3]= {0.181 Second, =dito= }
> Out[4]= 1350856
>
>
> yours, Hartmut
>



  • Prev by Date: combination of two ContourPlots - impossible?
  • Next by Date: Bayesian?
  • Previous by thread: Re: Re: Particular structure 2
  • Next by thread: Re: Re: Particular structure 2