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