MathGroup Archive 1992

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

Search the Archive

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






  • Prev by Date: how to compute determinants
  • Next by Date: Iterations..
  • Previous by thread: Re: how to compute determinants
  • Next by thread: Re: Limits to Det Function