[petsc-users] Direct Schur complement domain decomposition

[Jed Brown]

You should be able to look at any of the standard references on
multifrontal methods, e.g., by Liu, Davis, Gupta, or Duff.

Substructuring as a mesh-based procedure has fallen out of favor because
multifrontal does the same thing in more reusable code (purely algebraic;
no reference to a mesh) with fine performance.


On Tue, Jan 1, 2013 at 6:35 AM, Stefan Kurzbach <
stefan.kurzbach at tu-harburg.de> wrote:

>  Dear Jed
>
> 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 :)
>
> I will have to spend some more time to find out about the other hints you
> gave.
>
> Best regards
> Stefan
>
> Am 29.12.2012 19:59, schrieb Jed Brown:
>
> 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.
>
>  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.
>
> 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).
>
>  On Wed, Dec 19, 2012 at 10:25 AM, Stefan Kurzbach <
> stefan.kurzbach at tuhh.de> wrote:
>
>>  Hello everybody,
>>
>>
>>
>> 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?
>>
>>
>>
>> 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.
>>
>>
>>
>> Now my question:
>>
>> 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?).
>>
>>
>>
>> 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?
>>
>>
>>
>> Best regards
>>
>> Stefan
>>
>>
>>
>>
>>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20130101/d54e924b/attachment.html>