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