A distributed, scaleable simplex method
A distributed, scaleable simplex method
复制标题
DOI：
10.1007/s11227-008-0253-6
复制
发表时间：
2009-09
期刊：
影响因子：
--
通讯作者：
Gavriel Yarmish;R. V. Slyke
中科院分区：
文献类型：
--
作者：
Gavriel Yarmish;R. V. Slyke
我们提出了一个简单的，可扩展的，分布式的大型线性规划的单纯形实现。它是为粗粒度计算而设计的，特别是现成的工作站网络。可扩展性是通过使用标准形式的单纯形，而不是修订的方法。实际上，所有重要的实现都是基于修改后的方法，因为它对于最常见的稀疏LP来说要快得多。然而，标准方法也有优点。首先，标准方法对于稠密问题是有效的。虽然稠密性问题在一般情况下并不常见，但它们经常出现在一些重要的应用中，如小波分解、数字滤波器设计、文本分类和图像处理。第二，标准方法可以很容易地和有效地扩展到粗粒度，分布式算法。这里介绍这样的实现。实验和分析证明了该方法的有效性。
We present a simple, scaleable, distributed simplex implementation for large linear programs. It is designed for coarse-grained computation, particularly, readily available networks of workstations. Scalability is achieved by using the standard form of the simplex rather than the revised method. Virtually all serious implementations are based on the revised method because it is much faster for sparse LPs, which are most common. However, there are advantages to the standard method as well. First, the standard method is effective for dense problems. Although dense problems are uncommon in general, they occur frequently in some important applications such as wavelet decomposition, digital filter design, text categorization, and image processing. Second, the standard method can be easily and effectively extended to a coarse grained, distributed algorithm. Such an implementation is presented here. The effectiveness of the approach is supported by experiment and analysis.