Computing Tropical Prevarieties in Parallel
Computing Tropical Prevarieties in Parallel
复制标题
并行计算热带预品种
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
J. Verschelde
中科院分区：
文献类型：
--
作者：
A. Jensen;J. Sommars;J. Verschelde
热带变异的计算是应用多面体方法计算多项式系统正维解集的第一步。特别是，预向性是解的幂级数展开的候选先导指数。只要有一个预向性，幂级数的计算就可以立即开始，因此我们的热带变种的并行计算在流水线求解器中具有应用价值。我们提出了一个动态枚举的并行实现。我们的第一个带有分叉进程的分布式内存实现实现了很好的加速，但是常常导致进程的执行时间有很大的变化。共享内存多线程版本应用工作窃取来减少运行时的可变性。我们的实现应用线程安全的Parma多面体库（PPL），在GNU多精度算术库（GMP）的精确算术中，借助TCMalloc的快速内存分配。我们的并行实现能够计算循环16根问题的热带变种。我们还报道了n体和n涡问题的计算实验；我们的计算结果与Gfan相当。
The computation of the tropical prevariety is the first step in the application of polyhedral methods to compute positive dimensional solution sets of polynomial systems. In particular, pretropisms are candidate leading exponents for the power series developments of the solutions. The computation of the power series may start as soon as one pretropism is available, so our parallel computation of the tropical prevariety has an application in a pipelined solver. We present a parallel implementation of dynamic enumeration. Our first distributed memory implementation with forked processes achieved good speedups, but quite often resulted in large variations in the execution times of the processes. The shared memory multithreaded version applies work stealing to reduce the variability of the run time. Our implementation applies the thread safe Parma Polyhedral Library (PPL), in exact arithmetic with the GNU Multiprecision Arithmetic Library (GMP), aided by the fast memory allocations of TCMalloc. Our parallel implementation is capable of computing the tropical prevariety of the cyclic 16-roots problem. We also report on computational experiments on the n-body and n-vortex problems; our computational results compare favorably with Gfan.