论文标题
准确整合等级-1晶格和应用的快速概率组成部分结构
A fast probabilistic component-by-component construction of exactly integrating rank-1 lattices and applications
论文作者
论文摘要
在过去的几十年中，开发了一些越来越有效的组件（CBC）构造。一方面，存在基于最小化某些错误函数的结构。另一方面，有可能构造等级-1晶格的相应立方规则准确地整合了多元三角多项式空间内的所有元素。 在本文中，我们专注于第二种方法，即等级-1晶格规则的精确性。主要的贡献是对一种已知的算法的概率版本的分析，该算法实现了CBC构造这种等级-1晶格。事实证明，通过简单的随机化，可以平均改善已知的确定性算法的计算工作。此外，我们对一定的故障概率进行了详细的计算成本分析，然后导致概率CBC算法的发展。特别是，提出的方法将对构建所谓的重建等级-1晶格非常有益，这些晶格实际上与功能近似相关。在对所提出的CBC算法进行严格分析之后，我们提出了一种算法，该算法确定重建合理晶格尺寸的等级-1晶格具有很高的可能性。我们提供对发生故障概率的产生晶格大小和边界的估计。此外，我们讨论了提出的算法的计算复杂性。 各种数值测试说明了提出的算法的效率。除其他外，我们演示了如何利用算法的效率，即使是构建精确整合等级-1晶格的效率，但只要知道已知的三角多项式处理空间的某些特性。
Several more and more efficient component--by--component (CBC) constructions for suitable rank-1 lattices were developed during the last decades. On the one hand, there exist constructions that are based on minimizing some error functional. On the other hand, there is the possibility to construct rank-1 lattices whose corresponding cubature rule exactly integrates all elements within a space of multivariate trigonometric polynomials. In this paper, we focus on the second approach, i.e., the exactness of rank-1 lattice rules. The main contribution is the analysis of a probabilistic version of an already known algorithm that realizes a CBC construction of such rank-1 lattices. It turns out that the computational effort of the known deterministic algorithm can be considerably improved in average by means of a simple randomization. Moreover, we give a detailed analysis of the computational costs with respect to a certain failure probability, which then leads to the development of a probabilistic CBC algorithm. In particular, the presented approach will be highly beneficial for the construction of so-called reconstructing rank-1 lattices, that are practically relevant for function approximation. Subsequent to the rigorous analysis of the presented CBC algorithms, we present an algorithm that determines reconstructing rank-1 lattices of reasonable lattice sizes with high probability. We provide estimates on the resulting lattice sizes and bounds on the occurring failure probability. Furthermore, we discuss the computational complexity of the presented algorithm. Various numerical tests illustrate the efficiency of the presented algorithms. Among others, we demonstrate how to exploit the efficiency of our algorithm even for the construction of exactly integrating rank-1 lattices, provided that a certain property of the treated space of trigonometric polynomials is known.
