[Fwd: Re: improved Matrix.times()]

[Ron Boisvert <boisvert@nist.gov>]

Sender: nxo@Cs.Nott.AC.UK
Subject: Re: improved Matrix.times()


Thank you for the explanation.

Nas.


On May 22 2008, G. W. (Pete) Stewart wrote:

> It's time for a reality check.  Although the SVD is an iterative
> algorithm and has no fixed operation count, a timing of Cn^3 is a
> good approximation when the SVD algorithm is run on comparable
> matrices.  In Matlab, I ran the statements
> 
> >> A = randn(n); tic; [U,V,D]=svd(A); toc;
> 
> on my workstation for n=500 and n=1000.  Both runs gave C
> approximately 2e-8.  Using this value of C, we can predict that for
> n=100,000=1e5 the time to compute a complete SVD on my workstation
> will be at least
> 
> 2e7 sec = 5556 hrs = 231 days
> 
> or about 2/3 of a year.
> 
> However, for matrices of this size there may be memory problems.  A
> matrix or order 1e5 requires 80GB to store in double precision.
> Unless the computer has a very capacious memory, there will be a lot
> of paging during the calculation.
> 
> Special algorithms and advanced architectures may reduce these
> timings.  But probably not for Java platforms.
> 
> Pete Stewart
> 
> 
> 
> On Wed, 21 May 2008 nxo@cs.nott.ac.uk wrote:
> 
> > Date: Wed, 21 May 2008 20:29:22 -0400
> > From: nxo@cs.nott.ac.uk
> > Reply-To: jama@nist.gov
> > To: Multiple recipients of list <jama@nist.gov>
> > Subject: Re: improved Matrix.times()
> >
> > Dear Marcell,
> >
> > I would like to know, can the huge matrices handles 100,000 (of rows and
> > columns) times 100,000 (of rows and columns)?
> >
> > Please, I'm looking for matrices method that can handle Single Value
> > Decomposition a matrix of 100 thousands rows and columns.
> >
> >
> > Many Thanks,
> > Nas.
> >
> >
> >
> > On May 21 2008, Marcell Missura wrote:
> >
> > > After trying to multiply two huge matrices and running out of heap 
> > > memory I suggest to juice up the times(Matrix) method of the Matrix 
> > > class with the following few lines to avoid creating a massive amount 
> > > of garbage on the heap that needs to be collected.
> > >
> > > public Matrix times(Matrix B)
> > > {
> > >         if (B.m != n)
> > >                 throw new IllegalArgumentException("Matrix inner
> > > dimensions must agree.");
> > >
> > >         Matrix C = new Matrix(m, B.n);
> > >
> > >         for (int i = 0; i < m; i++)
> > >                 for (int j = 0; j < B.n; j++)
> > >                         for (int k = 0; k < n; k++)
> > >                                 C.A[i][j] += A[i][k] * B.A[k][j];
> > >
> > >         return C;
> > > }
> > >
> > >
> > >
> > >
> > >
> > >
> >
> > This message has been checked for viruses but the contents of an 
> > attachment may still contain software viruses, which could damage your 
> > computer system: you are advised to perform your own checks. Email 
> > communications with the University of Nottingham may be monitored as 
> > permitted by UK legislation.
> >
> >
> >
> > ----- End forwarded message -----
> >
> >
> >
> 
> 
> 
> 

This message has been checked for viruses but the contents of an attachment
may still contain software viruses, which could damage your computer system:
you are advised to perform your own checks. Email communications with the
University of Nottingham may be monitored as permitted by UK legislation.