Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: problem with very slow matrix function

• To: mathgroup at smc.vnet.net
• Subject: [mg50960] Re: problem with very slow matrix function
• From: drbob at bigfoot.com (Bobby R. Treat)
• Date: Wed, 29 Sep 2004 03:15:48 -0400 (EDT)
• References: <200409270442.AAA07181@smc.vnet.net> <cjasku$nrg$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

>>You can get a further factor of 5 or so speed improvement if your 
>>conditional instead uses Eigenvalues[N[aa[n-1],25]].

Perhaps the max eigenvalue is never exactly 12, but if it were, the
above suggestion would create a small problem, I think.

If that is an issue (or we simply don't know), the code can be changed
to something like solution c or e below. 12 could be replaced by
something that DOES appear as a max eigenvalue, after all.

digits = 19;
M = {{0, 1}, {1, 1}};
Clear[a, b, c, d, e]
a[n_] := If[Max@Eigenvalues@a[n - 1] < 12, M.a[n - 1], a[Floor[(n -
1)/2]]]
a[0] := {{0, 1}, {1, 1}}
b[n_] := b[n] = If[Max@Eigenvalues@b[n - 1] < 12, M.b[n - 1], b[
    Floor[(n - 1)/2]]];
b[0] := {{0, 1}, {1, 1}};
delta = .001;
c[n_] := Module[{previous = c[n - 1], max},
      max = Max@Eigenvalues@N@previous;
      If[max < 12 - delta || max < 12 + delta && 
        Max@Eigenvalues@previous < 12,
        M.previous,
        c[Floor[(n - 1)/2]]]
      ];
c[0] := {{0, 1}, {1, 1}};
d[n_] := Module[{previous = d[n - 1]},
      If[Max@Eigenvalues@previous < 12, M.previous, d[Floor[(n -
1)/2]]]
      ];
d[0] := {{0, 1}, {1, 1}};
e[n_] := e[n] = Module[{max},
        max = Max@Eigenvalues@N@e[n - 1];
        If[max < 12 - delta || max < 
          12 + delta && Max@Eigenvalues@e[n - 1] < 12,
          M.e[n - 1],
          e[Floor[(n - 1)/2]]]
        ];
e[0] := {{0, 1}, {1, 1}};

For digits=19, timings for a, b, c, d, and e on my machine are 19.968,
0.016, 0.016, 0.172, and 0. seconds, respectively.

For digits=50, timings for b, c, d, and e are 0.031, 0.719, 7.015, and
0.

For digits=1000, timings for b and e are 0.485 and 0.046.

For digits=10000, timings for b and e are 4.625 and 0.484.

b is the simple DP solution, c uses the faster test and eliminates a
duplicated calculation, d eliminates the duplicate with no other
change, and e combines DP with the faster test.

Even if we know the max eigenvalue is never exactly 12, the test used
in c and e is probably not a lot slower on average than the simpler
one Daniel suggested.

Bobby

Daniel Lichtblau <danl at wolfram.com> wrote in message news:<cjasku$nrg$1 at smc.vnet.net>...
> Roger Bagula wrote:
> > Mathematica will do this function, but only very slowly...
> > Thsat limits the number of values and how big I can make my critical point.
> > I'd like a better , faster expression to do this kind of matrix 
> > switching function.
> > I'm also looking for a way to make the switch depend on a random
> > level as well (&& / And).  
> > I tried a version and it ignorred the second "and" implicit
> > and did it on only the first implicit expression.
> > As I want to do this on higher matrix level Bonacci/ Pisot
> > systems, I would appreciate any help.
> > 
> > (*  2by2 Markov sequence Critical Eigenvalue collapse of   golden mean*)
> > digits=19
> > M={{0,1},{1,1}}
> > Det[M]
> > A[n_]:=If[(Max[Eigenvalues[A[n-1]]])<12, M.A[n-1],A[Floor[(n-1)/2]]];
> > A[0]:={{0,1},{1,1}};
> > (* Critical Eigenvalue collapse at 12 of 2by2 matrices made with  golden 
> > mean  recurrence*)
> > b=Flatten[Table[A[n],{n,0,digits}]]
> > ListPlot[b,PlotJoined->True,PlotRange->All]
> > 
> > {0,1,1,1,1,1,1,2,1,2,2,3,2,3,3,5,3,5,5,8,5,8,8,13,1,2,2,3,2,3,3,5,3,5,5,8,5,8,
> >   
> > 8,13,3,5,5,8,5,8,8,13,5,8,8,13,1,2,2,3,2,3,3,5,3,5,5,8,5,8,8,13,3,5,5,8,5,8,
> >   8,13,5,8,8,13}
> > Respectfully, Roger L. Bagula
> > 
> > tftn at earthlink.net, 11759Waterhill Road, Lakeside,Ca 92040-2905,tel: 619-5610814 :
> > URL :  http://home.earthlink.net/~tftn
> > URL :  http://victorian.fortunecity.com/carmelita/435/ 
> > 
> 
> It is slow because there is massive recursive recomputation. To avoid 
> this one "memoizes", that is, caches the values. This is discussed in 
> section 2.5.9 of the reference manual. For your example one might do as 
> follows.
> 
> mat = {{0,1},{1,1}};
> Clear[aa]
> aa[0] = mat;
> aa[n_] := aa[n] = If[Max[Eigenvalues[aa[n-1]]]<12,
>    mat.aa[n-1],
>    aa[Floor[(n-1)/2]]
>    ]
> 
> In[56]:= Timing[bb = Flatten[Table[aa[n], {n,0,2000}]];]
> Out[56]= {3.33 Second, Null}
> 
> You can get a further factor of 5 or so speed improvement if your 
> conditional instead uses Eigenvalues[N[aa[n-1],25]].
> 
> 
> Daniel Lichtblau
> Wolfram Research

• References:
  • problem with very slow matrix function
    • From: Roger Bagula <tftn@earthlink.net>