MathGroup Archive 2007

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

Search the Archive

Re: Re: How much memory is needed?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg82078] Re: [mg82042] Re: How much memory is needed?
  • From: DrMajorBob <drmajorbob at bigfoot.com>
  • Date: Thu, 11 Oct 2007 00:24:03 -0400 (EDT)
  • References: <fefijg$jn7$1@smc.vnet.net> <20377801.1192047100955.JavaMail.root@m35>
  • Reply-to: drmajorbob at bigfoot.com

Symbolic matrix inverses actually grow FASTER than exponential, I think.

Clear[bytes]
bytes[n_] := bytes[n] = ByteCount@Inverse@Array[Unique[] &, {n, n}]
bytes /@ Range[9]

{96, 896, 4664, 26824, 202640, 1713072, 15994768, 164526584, \
1850928968}

(I used Unique[]& because it got me one more term before running out of 
patience.)

1./Divide @@@ Partition[bytes /@ Range[9], 2, 1]
-Subtract @@@ Partition[%, 2, 1]

{9.33333, 5.20536, 5.75129, 7.55443, 8.45377, 9.33689, 10.2863, \
11.25}

{-4.12798, 0.545929, 1.80314, 0.899341, 0.883122, 0.949383, 0.963755}

The ratio of the n+1 term to the nth term is growing linearly (or worse) ,  

so the byte count grows like a factorial, not an exponential. Here's a  
linear projection of the ratio:

ratio = Interpolation[
    1./Divide @@@ Partition[bytes /@ Range[9], 2, 1],
    InterpolationOrder -> 1];
Plot[Quiet@ratio[x], {x, 1, 50}]

and here's an extrapolation for the byte count, for 50 to 60 rows:

Clear[extrapolate]
extrapolate[k_] /; 1 <= k <= 9 := bytes[k]
extrapolate[k_?Positive] :=
  extrapolate[k] = Quiet@ratio[k - 1] extrapolate[k - 1]

Table[extrapolate[x], {x, 50, 60}]

{2.2532*10^69, 1.16553*10^71, 6.14134*10^72, 3.29515*10^74,
  1.79978*10^76, 1.00037*10^78, 5.65672*10^79, 3.25319*10^81,
  1.90227*10^83, 1.13067*10^85, 6.82941*10^86}

The truth is probably even a bit worse, more like this:

Clear[extrapolate]
ratio = Interpolation[
    1./Divide @@@ Partition[bytes /@ Range[9], 2, 1],
    InterpolationOrder -> 2];
extrapolate[k_] /; 1 <= k <= 9 := bytes[k]
extrapolate[k_?Positive] :=
  extrapolate[k] = Quiet@ratio[k - 1] extrapolate[k - 1]

tbl = Table[extrapolate[x], {x, 50, 60}]

{1.50389*10^71, 9.73096*10^72, 6.45035*10^74, 4.37868*10^76,
  3.0429*10^78, 2.16405*10^80, 1.57451*10^82, 1.17161*10^84,
  8.91348*10^85, 6.93124*10^87, 5.50742*10^89}

a 9x9 inverse is already

bytes[9]/2^30 // N

1.72381 (gigabytes)

and a 10x10 inverse will be larger than any of our machines can handle:

extrapolate[10]/2^30 // N

21.079 (gigabytes)

Bobby

On Wed, 10 Oct 2007 03:27:34 -0500, Yaroslav Bulatov  
<yaroslavvb at gmail.com> wrote:

> On Oct 9, 2:45 am, "George Soklis" <g... at panteion.gr> wrote:
>> Hi everyone,
>>
>> I am trying to inverse a 60x60 symbolic matrix.
>>
>> Is anybody aware of what memory is needed for this calculation?
>>
>> Thanks in advance!
>>
>> George
>
> Size of Inverse output seems to exponentially with number of rows.
> Fitting an exponential to first 7 sizes and extrapolating, you get
> something around 6*10^56 bytes for 50x50 matrix
>
> counts = (ByteCount[Inverse[#]] &@Array[x, {#, #}]) & /@ Range[7]
> (counts[[# + 1]]/counts[[#]]) & /@ Range[Length[counts] - 1] // N
> Exp[50 a] /. FindFit[counts, Exp[a x], a, x]
>
>
>



-- 

DrMajorBob at bigfoot.com


  • Prev by Date: Re: "dereference" variable
  • Next by Date: Re: "dereference" variable
  • Previous by thread: Re: How much memory is needed?
  • Next by thread: Reproducible crash on startup when opening empty text file