J Syst Sci Complex (2011) 24: 803–815

OBTAINING EXACT INTERPOLATION

MULTIVARIATE POLYNOMIAL BY

APPROXIMATION∗

Yong FENG · Xiaolin QIN · Jingzhong ZHANG · Xun YUAN

DOI: 10.1007/s11424-011-8312-0

Received: 4 September 2008 / Revised: 25 June 2009 c©The Editorial Office of JSSC & Springer-Verlag Berlin Heidelberg 2011

Abstract In some fields such as Mathematics Mechanization, automated reasoning and Trustworthy

Computing, etc., exact results are needed. Symbolic computations are used to obtain the exact results.

Symbolic computations are of high complexity. In order to improve the situation, exact interpolating methods are often proposed for the exact results and approximate interpolating methods for the approximate ones. In this paper, the authors study how to obtain exact interpolation polynomial with rational coefficients by approximate interpolating methods.

Key words Continued fraction, multivariate interpolation, numerical approximate computation, symbolic-numerical computation, Vandermonde determinant. 1 Introduction

Some fields such as automated reasoning and trustworthy computing, etc., need exact results, and symbolic computations are used to obtain the exact results. Symbolic computations are principally exact and stable. However, they have the disadvantage of intermediate expression swell. Numerical computations do not have the problem, however only give approximate results. In recent two decades, numerical methods are applied in the field of symbolic computations. In 1985, Kaltofen presented an algorithm for performing the absolute irreducible factorization, and suggested to perform his algorithm by floating-point numbers, then the factor obtained is an approximate one. After then, numerical methods have been studied to get

Yong FENG

Laboratory of Computer Reasoning and Trustworthy Computation, University of Electronic Science and Technology of China, Chengdu 611731, China.

Xiaolin QIN (Corresponding author)

Laboratory for Automated Reasoning and Programming, Chengdu Institute of Computer Applications, Chinese

Academy of Sciences, Chengdu 610041, China; Graduate University of Chinese Academy of Sciences, Beijing 100049, China. Email: qinxl@casit.ac.cn

Jingzhong ZHANG

Laboratory of Computer Reasoning and Trustworthy Computation, University of Electronic Science and Technology of China, Chengdu 611731, China.

Xun YUAN

Laboratory for Automated Reasoning and Programming, Chengdu Institute of Computer Applications, Chinese

Academy of Sciences, Chengdu 610041, China. ∗This research is supported by China 973 Program 2011CB302402, the Knowledge Innovation Program of the

Chinese Academy of Sciences (KJCX2-YW-S02), the National Natural Science Foundation of China (10771205), and the West Light Foundation of the Chinese Academy of Sciences. This paper was recommended for publication by Editor Ziming LI. 804 YONG FENG, et al. approximate factors of a polynomial[1−6]. In the meantime, numerical methods are applied to get approximate greatest common divisors of approximate polynomials[7−10], to compute functional decompositions[11], to test primality[12] and to find zeroes of a polynomial[13]. Corless, et al.[14] applied numerical methods in implicitization of parametric curves, surfaces and hypersurfaces, and the resulting implicit equation is still an approximate one. Che`ze, et al.[15] discussed how to obtain an exact absolute polynomial factorization from its approximate one, which only involves recovering an integral coefficient from its approximation.

Interpolation methods as an efficient numerical method have been proverbially used to compute resultants and determinants, etc. And approximate interpolation methods are still used to get the approximate ones[16−18]. In order to obtain exact results, people usually use exact interpolation methods to meliorate intermediate expression swell problem arising from symbolic computations[19−23]. In fact, these are not approximate numerical computations but big number computations, which are also exact computations and only improve intermediate expression swell problem. Recently, Zhang, et al.[24] proposed an algorithm to recover the exact rational number from its approximation, and built a bridge by which exact results can be obtained by numerical approximate computations. In this paper, we discuss how the errors of support points affect those of coefficients of the interpolating polynomial, thereby present an algorithm to use approximate methods to get exact interpolation multivariate polynomial.

The algorithm can be carried out in parallel computers. Compared with exact interpolation method, the efficiency of the our algorithm is higher when the scale of problem is larger. This paper provides a way to obtain exact results by numerical computations.

The remainder of the paper is organized as follows. Section 2 gives a review of modified continued fraction method, by which an exact rational number can be obtained from its approximation, and gives a review of Kronecker product of two matrices. Section 3 first proposes an estimation of the error to ensure the exact interpolation polynomial to be obtained, and then presents an algorithm to obtain an exact polynomial from its approximation for univariate and multivariate polynomial over rational number field, respectively. Section 4 gives some experimental results. Section 5 makes conclusions. 2 Preliminaries

In general, obtaining exact polynomial by approximate computations consists of two steps.

First, compute approximate polynomial within an error control by approximate numerical methods, and then recover the exact coefficients of the approximate polynomial by continued fraction method. In this section, we review the main results to be used in this paper.

A continued fraction representation of a real number x is one of the forms: a0 + 1 a1 + 1 a2 + 1 a3 + · · · , (1) where a0 is an integer and a1, a2, a3, · · · are positive integers. One can abbreviate the above continued fraction as [a0; a1, a2, · · · ]. Truncating the above continued fraction representation of a number x early yields a rational number which is in a certain sense the best possible rational approximation. We call [a0; a1, · · · , an] the n-th convergent of [a0; a1, a2, · · · ]. By continued fraction representation, the relation between a rational number and its approximation was disclosed as follows[24].