• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Symbolic and Algebraic Computation Aug 3-6, 2003 Philadelphia, Pennsylvania, USA >Memory-Based and Disk-Based Algorithms for Very High Degree Permutation Groups
【24h】

Memory-Based and Disk-Based Algorithms for Very High Degree Permutation Groups

机译：高度排列组的基于内存和基于磁盘的算法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Group membership is a fundamental algorithm, upon which most other algorithms of computational group theory depend. Until now, group membership for permutation groups has been limited to ten million points or less. We extend the applicability of group membership algorithms to permutation groups acting on more than 100,000,000 points. As an example, we experimentally construct a group membership data structure for Thompson's group, acting on 143,127,000 points, in 36 minutes. More significantly, we require approximately 10 GB of RAM for the computation ― even though a single permutation of Thompson's group already requires half a gigabyte of storage. In addition, we propose a disk-based group membership algorithm with the promise of extending group membership to well over one billion (1,000,000,000) points. Such a disk-based algorithm has formerly been impossible, due in part to the lack of a practical disk-based algorithm for multiplying and taking inverses of such large permutations. Random access to disk is prohibitively expensive. We demonstrate the first practical disk-based implementation of the basic permutation operations. We also propose a disk-based architecture for group membership data structures.
机译：组成员资格是基本的算法，计算组理论的大多数其他算法都依赖于该算法。到目前为止，排列组的组成员资格被限制在1000万点或更少。我们将组成员资格算法的适用性扩展到作用于超过100,000,000点的置换组。例如，我们通过实验构造了汤普森小组的小组成员数据结构，该小组成员在36分钟内作用于143,127,000点。更重要的是，我们需要大约10 GB的RAM进行计算-即使Thompson小组的单个排列已经需要半GB的存储空间。此外，我们提出了一种基于磁盘的组成员资格算法，有望将组成员资格扩展到超过十亿（1,000,000,000）点。这种基于磁盘的算法以前是不可能的，部分原因是缺乏一种实用的基于磁盘的算法来对如此大的排列进行乘法和求逆。随机访问磁盘非常昂贵。我们演示了基本排列操作的第一个实用的基于磁盘的实现。我们还为组成员资格数据结构提出了基于磁盘的体系结构。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号