Analysis of PSLQ, an integer relation finding algorithm期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Analysis of PSLQ, an integer relation finding algorithm

Authors:	Helaman R P Ferguson David H Bailey Steve Arno

Institution:	Center for Computing Sciences, 17100 Science Drive, Bowie, MD 20715-4300 ; Lawrence Berkeley Lab, Mail Stop 50B-2239, Berkeley, CA 94720 ; Center for Computing Sciences, 17100 Science Drive, Bowie, MD 20715-4300

Abstract:	Let ${\mathbb{K}}$ be either the real, complex, or quaternion number system and let ${\mathbb{O}}({\mathbb{K}})$ be the corresponding integers. Let $x = (x_{1}, \hdots , x_{n})$ be a vector in ${\mathbb{K}}^{n}$ . The vector has an integer relation if there exists a vector $m = (m_{1}, \hdots , m_{n}) \in {\mathbb{O}}({\mathbb{K}})^{n}$ , $m \ne 0$ , such that $m_{1} x_{1} + m_{2} x_{2} + \ldots + m_{n} x_{n} = 0$ . In this paper we define the parameterized integer relation construction algorithm PSLQ $(\tau )$ , where the parameter $\tau$ can be freely chosen in a certain interval. Beginning with an arbitrary vector $x = (x_{1}, \hdots , x_{n}) \in {\mathbb{K}}^{n}$ , iterations of PSLQ $(\tau )$ will produce lower bounds on the norm of any possible relation for . Thus PSLQ $(\tau )$ can be used to prove that there are no relations for of norm less than a given size. Let $M_{x}$ be the smallest norm of any relation for . For the real and complex case and each fixed parameter $\tau$ in a certain interval, we prove that PSLQ $(\tau )$ constructs a relation in less than $O(n^{3} + n^{2} \log M_{x})$ iterations.

Keywords:	Euclidean algorithm integer relation finding algorithm Gaussian integer Hamiltonian integer polynomial time

	点击此处可从《Mathematics of Computation》浏览原始摘要信息
	点击此处可从《Mathematics of Computation》下载免费的PDF全文

设为首页 | 免责声明 | 关于勤云 | 加入收藏