...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of complexity >Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points
【24h】

Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points

机译：具有非素数点的等级1晶格规则的快速逐组分构造

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

摘要

The component-by-component construction algorithm constructs the generating vector for a rank-1 lattice one component at a time by minimizing the worst-case error in each step. This algorithm can be formulated elegantly as a repeated matrix-vector product, where the matrix-vector product expresses the calculation of the worst-case error in that step. As was shown in an earlier paper, this matrix-vector product can be done in time O(n log (n)) and with memory O(n) when the number of points n is prime. Here we extend this result to general n to obtain a total construction cost of O(sn log (n)) and memory of O(n) for a rank-1 lattice in s dimensions with n points. We thus obtain the same big-Oh result as for n prime. As was the case for n prime, the main calculation cost is significantly reduced by using fast Fourier transforms in the matrix-vector calculation. The number of fast Fourier transforms is dependent on the number of divisors of n and the number of prime factors of n. It is believed that the intrinsic structure present in rank-1 lattices and exploited by this fast construction method will deliver new insights in the applicability of these lattices.
机译：逐组件构造算法通过最小化每个步骤中的最坏情况误差，一次构造一个1级晶格的生成向量。可以将该算法优雅地表述为重复的矩阵向量乘积，其中矩阵向量乘积表示该步骤中最坏情况误差的计算。如先前的论文所示，当点数n为质数时，可以在时间O（n log（n））和内存O（n）中完成矩阵向量乘积。在这里，我们将此结果扩展到一般的n以获得O（sn log（n））的总构造成本和s维数为n点的1级晶格的O（n）记忆。因此，我们获得与n个素数相同的big-Oh结果。像n个质数一样，通过在矩阵矢量计算中使用快速傅里叶变换，显着降低了主要计算成本。快速傅里叶变换的数量取决于n的除数和n的素数的数量。可以相信，存在于1级晶格中并被这种快速构造方法利用的本征结构将为这些晶格的适用性提供新的见解。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号