<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
<br>
<br>
On 12/10/2010 06:30 PM, Jed Brown wrote:
<blockquote
cite="mid:AANLkTikxBg2adVCbSnWsLqBwJYyhYE3Y=+s3kyFBUWCY@mail.gmail.com"
type="cite">
<div class="gmail_quote">On Sat, Dec 11, 2010 at 00:03, Luke Bloy
<span dir="ltr"><<a moz-do-not-send="true"
href="mailto:luke.bloy@gmail.com">luke.bloy@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt
0.8ex; border-left: 1px solid rgb(204, 204, 204);
padding-left: 1ex;">
<div bgcolor="#ffffff" text="#000000">I'm solving a diffusion
problem. essentially I have 2,000,000 possible states for my
system to be in. The system evolves based on a markov matrix
M, which describes the probability the system moves from one
state to another. This matrix is extremely sparse on the
< 100,000,000 nonzero elements. The problem is to pump
mass/energy into the system at certain states. What I'm
interested in is the steady state behavior of the system.<br>
<br>
basically the dynamics can be summarized as <br>
<br>
d_{t+1} = M d_{t} + d_i<br>
<br>
Where d_t is the state vector at time t and d_i shows the
states I am pumping energy into. I want to find d_t as t
goes to infinity.<br>
<br>
My current approach is to solve the following system.<br>
<br>
(I-M) d = d_i<br>
</div>
</blockquote>
<div><br>
</div>
<div>So you want to do this for some 500,000 d_i? What problem
are you really trying to solve? Is it really to just
brute-force compute states for all these inputs? What are you
doing with the resulting 500k states (all 8 terabytes of it)?
Are you, for example, looking for some d_i that would change
the steady state d in a certain way?</div>
<div><br>
</div>
</div>
</blockquote>
Yes I'd like do do this for roughly 500,000 d_i. I'm solving a
diffusion problem, I only have local measures of the diffusion
process which is what i use to determine that matrix M. Now the
500,000 d_i are the boundaries to my diffusion problem, what i need
to know is who much of what gets pumped in though a given boundary
state exits the system through the other boundaries. Do i really
need to do all 500,000 Probably not. this is the highest resolution
mesh of the boundary i can compute from my data. A lower res mesh
would probably be sufficient. But I wont know until i do it either
way I'd like to use the highest res mesh that I can. If you can
suggest an alternative approach I am all ears.<br>
<br>
Luke <br>
<br>
<blockquote
cite="mid:AANLkTikxBg2adVCbSnWsLqBwJYyhYE3Y=+s3kyFBUWCY@mail.gmail.com"
type="cite">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt
0.8ex; border-left: 1px solid rgb(204, 204, 204);
padding-left: 1ex;">
<div bgcolor="#ffffff" text="#000000">
<div class="im">
<blockquote type="cite">
<div>2. If you can afford the memory, a direct solve
probably makes sense.</div>
</blockquote>
<br>
</div>
My understanding is the inverses would generally be dense. I
certainly don't have any memory to hold a 2 million by 2
million dense matrix, I have about 40G to play with. So
perhaps a decomposition might work? Which might you suggest?</div>
</blockquote>
</div>
<br>
<div>While inverses are almost always dense, sparse factorization
is far from dense. For PDE problems factored in an optimal
ordering, the memory asymptotics are n*log n in 2D and n^{4/3}
in 3D. The time asymptotics are n^{3/2} and n^2 respectively.
Compare to n^2 memory, n^3 time for dense.</div>
<div><br>
</div>
<div>Jed</div>
</blockquote>
</body>
</html>