Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: problem with very slow matrix function

• To: mathgroup at smc.vnet.net
• Subject: [mg50929] Re: [mg50911] problem with very slow matrix function
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Tue, 28 Sep 2004 00:58:43 -0400 (EDT)
• References: <200409270442.AAA07181@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

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>