logo

SCIENTIA SINICA Mathematica, https://doi.org/10.1360/SSM-2019-0336

On zero-error computation

More info
  • ReceivedDec 31, 2019
  • AcceptedApr 13, 2020
  • PublishedJul 9, 2020

Abstract

It is important both in theory and in practice to study how to obtain exact results via numeric computation, which we call zero-error computation.In this paper, we firstly indicate which kind of numbers are suitable for zero-error computation: One can compute the exact value from its approximate values for every element in a uniformly discrete set, in which there exists a nonzero separation bound between two distinct elements. Based on this observation, we give such a separation bound for algebraic numbers, which can be seen as a necessary condition on error control for zero-error computation of algebraic numbers. However, this condition may not be sufficient, depending on different algorithms. For the PSLQ (partial-sum-LQ-decompsition)-based algorithm, we give a sufficient condition on the precision that is quasi-linear in the degree of the algebraic number to be recovered, while the corresponding condition for the LLL (Lenstra-Lenstra-Lovász)-based algorithm is quadratic. We also suggest several potential research areas in the future.


Funded by

国家自然科学基金(11671377,11501540和11771421)

中国科学院青年创新促进会


Acknowledgment

感谢吴文渊研究员和两位匿名审稿人对本文提出的有益建议.


References

[1] 夏道行, 吴卓人, 严邵宗, 等. 实变函数论与泛函分析 (下册), 第二版修订版. 北京: 高等教育出版社, 2010. Google Scholar

[2] Zhang J, Feng Y. Obtaining exact value by approximate computations. Sci China Ser A, 2007, 50: 1361-1368 CrossRef Google Scholar

[3] Feng Y, Chen J, Wu W. The PSLQ algorithm for empirical data. Math Comp, 2019, 88: 1479-1501 CrossRef Google Scholar

[4] Lehmer D H. Euclid's algorithm for large numbers. Amer Math Monthly, 1938, 45: 227-233 CrossRef Google Scholar

[5] Knuth D. The analysis of algorithms. In: Actes Congrès International des Mathématiciens. Paris: Gauthier-Villars, 1970, 269--274. Google Scholar

[6] Sch\"onhage A. Schnelle Berechnung von Kettenbruchentwicklungen. Acta Inform, 1971, 1: 139-144 CrossRef Google Scholar

[7] Wang X, Pan V Y. Acceleration of Euclidean algorithm and rational number reconstruction. SIAM J Comput, 2003, 32: 548-556 CrossRef Google Scholar

[8] Pan V Y, Wang X. On rational number reconstruction and approximation. SIAM J Comput, 2004, 33: 502-503 CrossRef Google Scholar

[9] Mishra B. Algorithmic Algebra. New York: Springer, 1993. Google Scholar

[10] Kannan R, Lenstra A K, Lov{ász L. Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. Math Comp, 1988, 50: 235-250 CrossRef Google Scholar

[11] Mignotte M. Some useful bounds. In: Computer Algebra: Symbolic and Algebraic Computation. Heidelberg: Springer, 1982, 259--263. Google Scholar

[12] Lenstra A K, Lenstra Jr H W, Lovász L. Factoring polynomials with rational coefficients. Math Ann, 1982, 261: 515-534 CrossRef Google Scholar

[13] Chang X W, Stehlé D, Villard G. Perturbation analysis of the QR factor R in the context of LLL lattice basis reduction. Math Comp, 2012, 81: 1487-1511 CrossRef Google Scholar

[14] Nguyen P Q, Stehlé D. Floating-point LLL revisited. In: Advances in Cryptology---Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2005, 215--233. Google Scholar

[15] Morel I, Stehlé D, Villard G. H-LLL: Using Householder inside LLL In: Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation. New York: ACM, 2009, 271--278. Google Scholar

[16] van Hoeij M, Novocin A. Gradual sub-lattice reduction and a new complexity for factoring polynomials. In: Proceedings of the Latin American Symposium on Theoretical Informatics 2010 Heidelberg: Springer, 2010, 539--553. Google Scholar

[17] Novocin A, Stehlé D, Villard G. An LLL-reduction algorithm with quasi-linear time complexity: Extended abstract. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing. New York: ACM, 2011, 403--412. Google Scholar

[18] Ferguson H R P, Bailey D H, Arno S. Analysis of PSLQ, an integer relation finding algorithm. Math Comp, 1999, 68: 351-369 CrossRef Google Scholar

[19] Bergman G M. Notes on Ferguson and Forcade's generalized Euclidean algorithm. http://math.berkeley.edu/~gbergman/papers/unpub/FF_Euc.pdf 1980. Google Scholar

[20] Bailey D H. Integer relation detection. Comput Sci Eng, 2000, 2: 24-28 CrossRef Google Scholar

[21] Borwein J M, Lisoněk P. Applications of integer relation algorithms. Discrete Math, 2000, 217: 65-82 CrossRef Google Scholar

[22] 陈经纬, 冯勇, 秦小林, 等. 代数数极小多项式的近似重构. 系统科学与数学, 2011, 31: 903--912. Google Scholar

[23] Feng Y, Chen J, Wu W. Incremental PSLQ with application to algebraic number reconstruction. ACM Commun Comput Algebra, 2014, 47: 112-113 CrossRef Google Scholar

[24] Bailey D H, Broadhurst D J. Parallel integer relation detection: Techniques and applications. Math Comp, 2001, 70: 1719-1736 CrossRef Google Scholar

[25] Feng Y, Chen J, Wu W. Two variants of HJLS-PSLQ with applications. In: Proceedings of the 2014 Symposium on Symbolic-Numeric Computation. New York: ACM, 2014, 88--96. Google Scholar

[26] Skerritt M P, Vrbik P. Extending the PSLQ algorithm to algebraic integer relations. In: From Analysis to Visualization. Cham: Springer, 2020, 407--421. Google Scholar

[27] Bailey D H, Borwein J M, Kimberley J S. Computer discovery and analysis of large Poisson polynomials. Experiment Math, 2017, 26: 349-363 CrossRef Google Scholar

[28] Chen J, Stehlé D, Villard G. A new view on HJLS and PSLQ: Sums and projections of lattices. In: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation. New York: ACM, 2013, 149--156. Google Scholar

[29] Chen J, Feng Y, Wu W. Reducing lattice bases with Bergman exchange. In: Proceedings of the IEEE 9th International Conference on Communication Software and Networks (ICCSN), Volume II. Piscataway: IEEE, 2017, 630--634. Google Scholar

[30] Chen J, Stehlé D, Villard G. Computing an LLL-reduced basis of the orthogonal lattice. In: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation. New York: ACM, 2018, 127--133. Google Scholar

[31] B{\"o}hm J, Decker W, Fieker C. The use of bad primes in rational reconstruction. Math Comp, 2015, 84: 3013-3027 CrossRef Google Scholar

[32] Abbott J. Fault-tolerant modular reconstruction of rational numbers. J Symbolic Comput, 2017, 80: 707-718 CrossRef Google Scholar

[33] Olesh Z, Storjohann A. The vector rational function reconstruction problem. In: Computer Algebra 2006: Latest Advances in Symbolic Algorithms. Singapore: World Scientific, 2007, 137--149. Google Scholar

[34] Bright C, Storjohann A. Vector rational number reconstruction. In: Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. New York: ACM, 2011, 51--58. Google Scholar

[35] Kaltofen E L, Li B, Yang Z. Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients. J Symbolic Comput, 2012, 47: 1-15 CrossRef Google Scholar

[36] Moreno C J. The zeros of exponential polynomials (I). Compos Math, 1973, 26: 69--78. Google Scholar

[37] Bailey D H. Numerical results on the transcendence of constants involving $\pi,$ e, and Euler's constant. Math Comp, 1988, 50: 275-281 CrossRef Google Scholar

[38] Bailey D H, Borwein J M, Calkin N J, et al. Experimental Mathematics in Action. New York: CRC Press, 2007. Google Scholar

[39] Bailey D H, Borwein J M. Exploratory experimentation and computation. Notices Amer Math Soc, 2011, 58: 1410--1419 (探索性实验和计算. 陆汝钤,译. 数学译林, 2012, 31: 1--14). Google Scholar

[40] Zhi L. Symbolic-numeric algorithms for computing validated results. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. New York: ACM, 2014, 25--26. Google Scholar

  •   

    Algorithm 1 有理数恢复

    Require:正整数 $N$ 和一个浮点数 $r\in(0,~1)$.

    Output:一个有理数 $b$.

    令 $t$ 为 $r$ 的有理数表示, $h_0~:=~0$, $h_1~:=~1$, $k_0~:=~1$, $k_1~:=~0$; $a~:=~\lfloor~t\rfloor$, $b:=~t~-~a$; $k_2~:=~a\cdot~k_1~+~k_0$.

    while $k_2\le~N$ do

    $\binom{h_2}{k_2}~:=~a\cdot\binom{h_1}{k_1}~+\binom{h_0}{k_0}$, $\binom{h_0}{h_1}~:=\binom{h_1}{h_2}$, $\binom{k_0}{k_1}~:=\binom{k_1}{k_2}$.

    if $b~=~0$ then

    $k_2~:=~N+1$.

    else

    更新 $t~:=~\frac{1}{b}$, $a~:=~\lfloor~t\rfloor$, $b:=~t~-~a$.

    end if

    end while

    return $b~:=~h_0/k_0$.

  • Table 1   基于浮点 LLL 算法的代数数极小多项式重构复杂度上界
    算法 比特复杂度上界
    L$^2$ (参见文献[-1])/H-LLL (参见文献[-1]) $\CO(d^{7+\varepsilon}~+~d^{6+\varepsilon}\log~N~+~n^{5+\varepsilon}\log^2N)$
    渐近 LLL (参见文献[-1]) $\CO(d^{6+\varepsilon}~+~d^{4+\varepsilon}\log^2N)$
    L$^1$ (参见文献[-1]) $\CO(d^{6+\varepsilon}~+~d^{5+\varepsilon}\log~N~+ d^{\omega+1+\varepsilon}{\log^{1+\varepsilon}N})$
  • Table 2   代数数 bm$\alpha~=~{1}/(\sqrt[r]{2}+\sqrt[s]{3})$ 极小多项式近似重构中的误差控制 (bm$n$ 为次数, bm$N$ 为高度)
    $r$ $s$ $n$ $N$ (11) 中的输入误差 (18) 中的输入误差
    $2$ $4$ $8$ $104$ $3.9537\times~10^{-67}$ $7.2936\times~10^{-48}$
    $2$ $6$ $12$ $552$ $~7.6741\times~10^{-134}$ $5.2144\times~10^{-88}$
    $4$ $6$ $24$ $32364$ $~1.0465\times~10^{-445}$ $~1.9748\times~10^{-260}$
    $4$ $8$ $32$ $823984$ $~1.2404\times~10^{-765}$ $~2.8489\times~10^{-438}$
    $6$ $8$ $48$ $400286016$ $~~1.7439\times~10^{-1647}$ $~5.8168\times~10^{-919}$
  •   

    Algorithm 2 基于 LLL 算法重构模不大于 $1$ 的代数数的极小多项式

    Require:代数数次数的上界 $d$, 高度的上界 $N$, LLL 约化基合法参数 $\Xi$, 使得 (10) 成立的最小正整数 $s$, 以及满足 \begin{align} |\alpha-\bar{\alpha}|<\frac{1}{2^{s+2}d} \tag{11} \end{align} 的代数数的近似值 $\bar{\alpha}$.

    Output:代数数 $\alpha$ 的极小多项式 $P_\alpha(X)$.

    对 $i=1,\ldots,~d$ 计算 $\bar{\alpha}_i$ 使其满足 $\abs{\bar{\alpha}^i~-\bar{\alpha}_i}<2^{-s-1/2}$.

    for $n$ from $1$ to $d$

    构造格 $L_s$.

    stp:lll 调用任一 LLL 算法计算格 $L_s$ 的一组 LLL 约化基, 基中的第一个向量记为 $\tilde{\boldsymbol{v}}$.

    if $\norm{\tilde{\boldsymbol{v}}}<2^{d/2}(d+1)N$ then

    return $\tilde{\boldsymbol{v}}$ 对应的多项式 $v(X)$.

    end if

    end for

  •   

    Algorithm 3 基于 $\PSLQ_{\varepsilon}$ 算法重构模不大于 $1$ 的代数数的极小多项式

    Require:代数数次数的上界 $d$, 高度的上界 $N$, 满足 \begin{align} |\alpha-\bar{\alpha}|< \frac{1}{128(d+1)^{d+11/2}N^{2d}} \tag{18} \end{align} 的代数数的近似值 $\bar{\alpha}$.

    Output:代数数 $\alpha$ 的极小多项式 $P_\alpha(X)$.

    for $n$ from $1$ to $d$

    令 $\bar{\boldsymbol{\alpha}}:=(\bar{\alpha}^n,~\bar{\alpha}^{n-1},~\ldots,~1)$, 并令 $\bar{\boldsymbol{x}}~:=~\bar{\boldsymbol{\alpha}}/{\norm{\bar{\boldsymbol{\alpha}}}}$.

    按 (12) 构造 $\bar{\boldsymbol{x}}$ 的超平面矩阵 $H:=H_{\bar{\boldsymbol~x}}$.

    按 (17) 设置 $\varepsilon_2$ 的值, 并以 $\abs{h_{n,~n}}<\varepsilon_2$ 为终止条件调用 $\PSLQ_{\varepsilon}$ 算法 (参见文献[3]) 返回非零整向量 $\boldsymbol{m}\in\integer^{n+1}$.

    if $\norm{\boldsymbol{m}}<N$ then

    return $\boldsymbol{m}$ 对应的多项式 $m(X)=\sum_{i=0}^nm_iX^{n-i}$.

    end if

    end for

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号