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>
- problem with very slow matrix function