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

[Ron Boisvert <boisvert@nist.gov>]

Sender: "G. W. (Pete) Stewart" <stewart@cs.umd.edu>
Subject: Re: improved Matrix.times()



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