Limits to Det Function

*To*: mathgroup at yoda.physics.unc.edu*Subject*: Limits to Det Function*From*: ross at macadam.mpce.mq.edu.au*Date*: Thu, 23 Apr 1992 18:15:49 +1000

The recent discussion concerning symbolic determinants has overlooked a very significant constraint, imposed by Mathematica. That is, how large can an array/list be? Why did all the timings for the various versions of NewDet[] stop at 8x8 matrices? Someone said they "...could not afford the 45 minutes.." to do the 9x9 case. My experience is that it would have taken a lot longer than just 45 minutes!! Look at these timings, done with Mma version 2.0, under DEC ULTRIX RISC. Do[ Print[ First[ Timing[ NewDet4[ a[i]]]]], {i,1,9}] 0.0166667 Second 0.0166667 Second 0.0333333 Second 0.0833333 Second 0.166667 Second 0.833333 Second 6.2 Second 55.65 Second The i = 9 timing is missing because the calculation had not finished after more than an hour. Simplifying a little bit... Do[ Print[ First[ Timing[ Permutations[ Range[i]]]]], {i,1,10}] 0. Second 0. Second 0. Second 0.0166667 Second 0. Second 0.05 Second 0.4 Second 3.33333 Second 31.55 Second The pattern suggests 5-6 minutes for the i = 10 calculation. I gave up after closer to 30 minutes!! How big are the arrays generated by Permutations[ Range[i]] ? Map[{#,#!}&, Range[10]]//ColumnForm {1, 1} {2, 2} {3, 6} {4, 24} {5, 120} {6, 720} {7, 5040} {8, 40320} {9, 362880} {10, 3628800} ... this latter size is significantly greater than 2^21 . Here is a much simplified example of the same phenomena, using the built-in function Reverse[] . Do[ Print[ {i, 2^i, First[ Timing[ Reverse[ Range[2^i]]]]} ] , {i,10,22}] {10, 1024, 0. Second} {11, 2048, 0.0333333 Second} {12, 4096, 0.0833333 Second} {13, 8192, 0.183333 Second} {14, 16384, 0.35 Second} {15, 32768, 0.716667 Second} {16, 65536, 1.41667 Second} {17, 131072, 2.88333 Second} {18, 262144, 5.7 Second} {19, 524288, 11.45 Second} {20, 1048576, 22.4167 Second} Note the missing entries for i = 21 and i = 22 . This is because the calculation still hadn't finished after 3+ hours!! Recall the definition of NewDet4[] ... NewDet4[M_] := ( Signature[M] Plus@@Times@@ Append[ Transpose[#,{2,1,1}],(Signature/@#) ]&@ Permutations[ M ] ) For M = a[9] with ... a[n_] := Table[ StringJoin["a",ToString[i],ToString[j]] , {i,1,n},{j,1,n}] the structure Permutations[ M ] has size 9 x 9! which is larger than 2^21 . (My) Conclusion: with lists of size > 2^20 (approx) don't expect even the simplest operations to work. Break up the array into smaller pieces and work with these, if you can. I first encountered this type of problem 2 years ago using version 1.2 on a Macintosh IIci. Then I wanted to work with Permutations[8] but found everything grinding to a virtual stand-still. Things worked again after nesting Permutations[6] inside two nested Do 's -- ugly for functional programming, but necessary timewise. Is this apparent size limit machine-dependent ? and/or version-dependent ? Would someone please confirm (or rebuff) my suspicions here. _______________________________ Ross Moore | Mathematics Dept | Macquarie University | North Ryde, Sydney | Australia | | ross at macadam.mpce.mq.edu.au | ______________________________|