<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Dear Jed<br>
<br>
Thanks. Non-iterative or direct substructuring is my understanding
as well. You said this is the same as multifrontal factorization
as well. Could you point me to some source where I can see the
parallels? Maybe this is obvious for people who have grown up with
solving sparse systems, but not for me :)<br>
<br>
I will have to spend some more time to find out about the other
hints you gave. <br>
<br>
Best regards<br>
Stefan<br>
<br>
Am 29.12.2012 19:59, schrieb Jed Brown:<br>
</div>
<blockquote
cite="mid:CAM9tzS=1xu1CWTUEygOiZMitQz3JQ2dEm3=ABd9sfSJkGE36Wg@mail.gmail.com"
type="cite">
<div dir="ltr">Sorry for the slow reply. What you are describing
_is_ multifrontal factorization, or alternatively,
(non-iterative) substructuring. It is a direct solve and boils
down to a few large dense direct solves. Incomplete
factorization is one way of preventing the Schur complements
from getting too dense, but it's not very reliable.<br>
<div class="gmail_extra"><br>
</div>
<div class="gmail_extra">There are many other ways of retaining
structure in the supernodes (i.e., avoid unstructured dense
matrices), at the expense of some error. These methods
"compress" the Schur complement using low-rank representations
for long-range interaction. These are typically combined with
an iterative method.<br>
<br>
Multigrid and multilevel DD methods can be thought of as an
alternate way to compress (approximately) the long-range
interaction coming from inexact elimination (dimensional
reduction of interfaces).<br>
<br>
<div class="gmail_quote">
On Wed, Dec 19, 2012 at 10:25 AM, Stefan Kurzbach <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:stefan.kurzbach@tuhh.de" target="_blank">stefan.kurzbach@tuhh.de</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div link="blue" vlink="purple" lang="DE">
<div>
<p class="MsoNormal"><span lang="EN-US">Hello
everybody,</span></p>
<p class="MsoNormal"><span lang="EN-US"> </span></p>
<p class="MsoNormal"><span lang="EN-US">in my recent
research on parallelization of a 2D unstructured
flow model code I came upon a question on domain
decomposition techniques in “grids”. Maybe someone
knows of any previous results on this?</span></p>
<p class="MsoNormal"><span lang="EN-US"> </span></p>
<p class="MsoNormal"><span lang="EN-US">Typically,
when doing large simulations with many unknowns,
the problem is distributed to many computer nodes
and solved in parallel by some iterative method.
Many of these iterative methods boil down to a
large number of distributed matrix-vector
multiplications (in the order of the number of
iterations). This means there are many
synchronization points in the algorithms, which
makes them tightly coupled. This has been found to
work well on clusters with fast networks.</span></p>
<p class="MsoNormal"><span lang="EN-US"> </span></p>
<p class="MsoNormal"><span lang="EN-US">Now my
question:</span></p>
<p class="MsoNormal"><span lang="EN-US">What if there
is a small number of very powerful nodes (say less
than 10), which are connected by a slow network,
e.g. several computer clusters connected over the
internet (some people call this “grid computing”).
I expect that the traditional iterative methods
will not be as efficient here (any references?).</span></p>
<p class="MsoNormal"><span lang="EN-US"> </span></p>
<p class="MsoNormal"><span lang="EN-US">My guess is
that a solution method with fewer synchronization
points will work better, even though that method
may be computationally more expensive than
traditional methods. An example would be a domain
composition approach with direct solution of the
Schur complement on the interface. This requires
that the interface size has to be small compared
to the subdomain size. As this algorithm basically
works in three decoupled phases (solve the
subdomains for several right hand sides, assemble
and solve the Schur complement system, correct the
subdomain results) it should be suited well, but I
have no idea how to test or otherwise prove it.
Has anybody made any thoughts on this before,
possibly dating back to the 80ies and 90ies, where
slow networks were more common?</span></p>
<p class="MsoNormal"><span lang="EN-US"> </span></p>
<p class="MsoNormal"><span lang="EN-US">Best regards<span
class="HOEnZb"></span></span></p>
<span class="HOEnZb"><font color="#888888">
<p class="MsoNormal">
<span lang="EN-US">Stefan</span></p>
<p class="MsoNormal"><span lang="EN-US"> </span></p>
<p class="MsoNormal"><span lang="EN-US"> </span></p>
</font></span></div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
</blockquote>
<br>
</body>
</html>