Re: tree/cotree extraction; additional details

 All,

Thanks to those of you who have replied.  I have learned some additional 
detail of
the underlying application, which I quote below.

- David

What I am essentially trying to do is decompose the 
unknowns  into two sets, cotree & tree unknowns. 
So, given a matrix equations from a discretization of
a pde (33 pt in 3d, 7 in 2d), I want to "re-order"
the matrix into tree-tree, cotree-cotree, tree-cotree,
cotree-tree blocks. Then the block diagonal tree-tree
and cotree-cotree matrix is used in a preconditioner.
Apparently, when these blocks are well-conditioned, the
overall solver works. However, when they are not, we get degradation.
Now to guarantee well-conditioning of these blocks,
it seems like the tree-tree sub-block highly depends
on the shape of the tree. According to other researchers,
it has to do with the lengths of the branches of
the tree- balanced or almost equal length branches give good
conditioning.

>
> David Hysom wrote:
>
>> All,
>>
>> A colleague of mine inquired about algorithms for extracting
>> trees and cotrees from a graph.  After some clarification,
>> his conditions and requirements appear to be:
>>
>> 1. the graph results from a finite element dicredtization of a 3D pde;
>>   the graph is irregular---some nodes have more edges connected to
>>   them than others;
>>
>> 2. he's interested in practice, not theory;
>>
>> 3. the tree should have "branches that are about the same size,"
>>   by which I believe he means for any node in the tree, the
>>   subtree rooted at the node's children should contain approximately
>>   the same number of nodes (i.e., balanced tree);
>>
>> 4. he's looking for a sequential algorithm, but will eventually
>>   be interested in a parallel algorithm; at present he's working
>>   with 0.5 billion nodes;
>>
>> 5. there is no restriction on choosing the root node;
>>
>> 6. I'm guessing the tree should be as bushy as possible
>>   so as to minimize the distance from the root to leaf nodes.
>>
>> I immediately thought of breadth first search, but don't know
>> about dealing with requirements (3) and (6).  I suspect one would want
>> to start by finding a "centermost" node and using that as the root.
>>
>> Any thoughts or references on these issues would be greatly appreciated.
>>
>> thanks,
>> David Hysom
>> Center for Advanced Scientific Computing
>> Lawrence Livermore Nat. Lab.
>>
>>
>> _______________________________________________
>> Csc mailing list
>> Csc-lVPF2Jp+hdv2fBVCVOL8/[email protected]
>> http://list.odu.edu/listinfo/csc
>>
>>  
>>
>
> _______________________________________________
> Csc mailing list
> Csc-lVPF2Jp+hdv2fBVCVOL8/[email protected]
> http://list.odu.edu/listinfo/csc