[PPL-devel] merging hulls

[Enea Zaffanella]

On 06/04/2015 12:49 AM, Rick Sprague wrote:
> Not sure if the mailing list got my first message, but here goes...
>
> I have an input that's a set of generators/vertices.  I'd like to 
> split the input in two and compute hyper planes for each half. How can 
> I merge the two constraint systems to get a final set of minimized 
> constraints?
>
> Do I have to basically processes the whole input at once?  Or point me 
> to some literature that may address this (if it's actually possible)? 
> I was hoping for a divide and conquer type approach to computing 
> constraints.
>
> Thanks,
>
> M
>
>
> _______________________________________________
> PPL-devel mailing list
> PPL-devel at cs.unipr.it
> http://www.cs.unipr.it/mailman/listinfo/ppl-devel

Hello Rick.

Not completely sure regarding what you want to do here ...

Anyway, if what you want is a divide&conquer algorithm for the DD 
method, you can find some proposals in the literature. For instance:

Jevremovi ́c, D., Boley, D., Sosa, C.P.
Divide-and-conquer approach to the parallel computation of elementary 
flux modes in metabolic networks.
In Parallel and Distributed Processing Workshops and Phd Forum, 2011

At present, the PPL has no implementation of these algorithms. Also, it 
is unclear whether or not these are able to obtain significant 
performance gains for "common cases". You may want to have a look to 
Chapter 7 of the disseration of Blagoy Genov:

The Convex Hull Problem in Practice : Improving the Running Time of the 
Double Description Method
http://elib.suub.uni-bremen.de/edocs/00104422-1.pdf

http://elib.suub.uni-bremen.de/peid=D00104422

Regards,
Enea Zaffanella.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.cs.unipr.it/pipermail/ppl-devel/attachments/20150604/66730b42/attachment.htm>