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
>
> 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