Re: Open letter: Who steals memory? :-)
- To: mathgroup at smc.vnet.net
- Subject: [mg47355] Re: [mg47311] Open letter: Who steals memory? :-)
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Tue, 6 Apr 2004 06:36:49 -0400 (EDT)
- References: <200404050922.FAA21808@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Derov Alexey wrote:
> Who steals memory? OR Is it possible to use Mathematica for
> Technical Computations YES or NOT?
>
> Dear colleagues, once again I want to consider one aged problem. Who
> steals memory? (I am far from idea that the corporation Wolfram Res.
> steals memory :- ) on my computer), but some problem in this field
> disturbs me. For example we shall consider a problem of linear
> equations systems solution
>
> A . x = b, were A - matrix, b - vector, x - required vector
>
> Let's try to solve the given system by method of Gauss elimination
> (LU-factorization). Well-known, that this method does not demand too
> much additional memory. But that we see
>
> n = 1024;
> A = Table[Random[],{n},{n}];
> b = Table[Random[],{n}];
>
> MaxMemoryUsed[ ]/(1024*1024.) - - - > 10.0353
> ByteCount[A]/(1024*1024.) - - - > 8.000
>
> x1 = LinearSolve[A,b,Method->OneStepRowReduction];
> MaxMemoryUsed[ ]/(1024*1024.) - - - > 70.206
>
> But other method gives more well result
>
> x2 = LinearSolve[A,b];
> MaxMemoryUsed[]/(1024*1024.) - - -> 18.0844
>
> The "Mathematica" is demanded so many memory, In my modest opinion it
> is too much memory.
> But there can be I have not understood options:
>
> Method -> OneStepRowReduction
>
> Then I offer one more way, Let's write the program to solution of
> linear equations systems independently. We use the same method of
> Gauss elimination. In our notations:
>
> A = g[[All,Range[1,n]]];
> b = g[[All,n+1]];
>
> Realization of the given algorithm on any the programming language
> FORTRAN or C will not use additional memory. But, "Mathematica"
> demands too much again:
>
>
> n = 1024;
> g = Table[Random[],{n},{n+1}];
> MaxMemoryUsed[ ]/(1024*1024.) - - - > 10.03
>
> Do[ g[[i,All]] /= g[[i,i]];
> Do[ g[[j,All]]-=g[[j,i]]*g[[i,All]]
> ,{ j,i+1,n}]; ,{i,1,n}];
> x=Table[0,{n}];
> Do[
> x[[i]]+=g[[i,n+1]];
> x[[i]]-=g[[i,Range[i+1,n]]]. x[[Range[i+1,n]]]
> ,{i,n,1,-1}];
> MaxMemoryUsed[ ]/(1024*1024.) - - - > 18.1024
>
> WHO STEALS MEMORY? :-)
> My problem has arisen as follows. I solve the system A .x = b, the
> matrix - A is located in memory well, but I don't solve this problem
> memory does not suffice!
>
> Is it possible to use "Mathematica" for heavy computations YES or
> NOT?,
> This question to have to consider.
> COLLEAGUES, ARE YOU AGREE WITH ME?
>
> Derov Alex
>
I have some trouble following this post but I will address what I think
are some the issues raised.
(1) If we do
n = 1024;
A = Table[Random[],{n},{n}];
b = Table[Random[],{n}];
In[4]:= ByteCount[A]/(1024*1024.)
Out[4]= 8.00006
In[5]:= MaxMemoryUsed[ ]/(1024*1024.)
Out[5]= 10.1692
I'm sure Out[4] is no surprise (8 bytes per double) and Out[5] indicates
that at present most of the memory used is tied up in matrix A. Now do
x2 = LinearSolve[A,b];
In[7]:= MaxMemoryUsed[]/(1024*1024.)
Out[7]= 18.2101
What this indicates is we are using another 8*1024^2 bytes. No surprise
if you stop to consider that A is still around in its original form, and
we used a matrix of the same size to form the LU factorization.
(2) As for using LinearSolve[...,Method->OneStepRowReduction, that is
really meant for handling symbolic matrices. It does not surprise me
that it eats up memory in this setting; it has substantial overhead and
is attempting to cut back on what is called intermediate swell (which is
the primary consumer of memory in symbolic matrix manipulation). I
should also mention that it is most likely doing nothing more
substantial than working with the matrix in unpacked format, possibly
making three copies along the way (I agree this is not ideal but it is
also not horrendous; I think it would be difficult to avoid having two
copies in any case).
(3) The excess memory consumption from alterning g in place is due to
storage of Out[2]. If you precede your computation with
$HistoryLength = 0;
then you will instead obtain:
In[9]:= MaxMemoryUsed[]/N[n^2]
Out[9]= 10.2035
Daniel Lichtblau
Wolfram Research
- References:
- Open letter: Who steals memory? :-)
- From: derov@rambler.ru (Derov Alexey)
- Open letter: Who steals memory? :-)