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@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.