Path: utzoo!utgpu!watmath!iuvax!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!uxe.cso.uiuc.edu!mcdonald
From: mcdonald@uxe.cso.uiuc.edu
Newsgroups: comp.arch
Subject: Re: 1000000x1000000 Matrix (was: li
Message-ID: <46500084@uxe.cso.uiuc.edu>
Date: 23 Oct 89 01:36:00 GMT
References: <9118@batcomputer.tn.cornell.edu>
Lines: 57
Nf-ID: #R:batcomputer.tn.cornell.edu:9118:uxe.cso.uiuc.edu:46500084:000:2675
Nf-From: uxe.cso.uiuc.edu!mcdonald    Oct 22 20:36:00 1989


In article <46500082@uxe.cso.uiuc.edu> mcdonald@uxe.cso.uiuc.edu writes:
>I heartily agree with that: I have two projects that I tried on 
>a big supercomputer: one diagonalized zillions of 20x20 matrices,
>the other wants to diagonalize a single 1000000x1000000 matrix.
>Neither was suitable for a Cray!
Somebody replies:

>Perhaps you could use a different algorithm to diagonalize
>many 20x20 matrices.  It sounds like the kind of thing that
>could be re-written with significant improvement.  

The Cray does this just fine. It is just that cheaper computers are more
cost effective (even with the Cray doing the vectorizable part
efficiently) - but, at the present time, the more important reason
snot to use the Cray for things like this is accessibility ,
which is better for lesser machines.

>But that's not really the point of this posting!!   My real question is:

>1) Is your 1000000x1000000 matrix dense?  If not, how sparse is it?
It is dense. Totally dense. No element is (in principle) zero.

>2) How did you solve it?
Are you kidding? All I get is uproarious laughter. But, now
and then, it begins to look like hope in the next few years!

On the other  hand, we have a theoretician here who works on
equally large, but very sparse (I don't know how "very") matrices. These
he does just fine. I don't really know how, as he is rather secretive,
but he does say that the methods are well known ones for sparse
matrices.

>3) On what machine did you solve it?
The guy with the sparse one does fine on Vaxes, Crays, and Mipss.

>4) What is the application?  (Its not a complex matrix, is it?!)
Mine is quantum mechanics of vibrations. No, it is real symmetric.
But I need at least some of the eigenvectors, though the eigenvalues
would be good enough to start with. Actually, generating the elements
is a worse problem than the diagonalization, as it requires
doing as many multidimensional integrals as there are independent
matrix elements. I have done it up to 1000x1000, but the results
are too coarse grained to be comparable to experiments.

I used to do the same problem in classical mechanics. Now THERE
is a good problem for parallel computers: doing many systems
of differential equations in parallel - you get as many sets of data
as one wants, all executing the same instructions at the same time.
In other words, one would have say 100 or more different initial
conditions, all running the same set of 20-50 simultaneous 
first order linear equations. This was done way back when, 1973-1975,
on the Illiac IV, which suited it perfectly. Only problem
was, the results only proved that classical mechanics won't
give correct results.

Doug McDonald