zbMATH — the first resource for mathematics

Early termination in sparse interpolation algorithms. (English) Zbl 1074.68080
Summary: A probabilistic strategy, early termination, enables different interpolation algorithms to adapt to the degree or the number of terms in the target polynomial when neither is supplied in the input. In addition to dense algorithms, we implement this strategy in sparse interpolation algorithms. Based on early termination, racing algorithms execute simultaneously dense and sparse algorithms. The racing algorithms can be embedded as the univariate interpolation substep within Zippel’s multivariate method. In addition, we experimentally verify some heuristics of early termination, which make use of thresholds and post-verification.

MSC:
 68W30 Symbolic computation and algebraic computation 13P05 Polynomials, factorization in commutative rings
Software:
Dagwood; ffmodstd; FOXBOX
Full Text:
References:
 [1] Ben-Or, M.; Tiwari, P., A deterministic algorithm for sparse multivariate polynomial interpolation, (), 301-309 [2] Delsarte, P.; Genin, Y.V.; Kamp, Y.G., A generalization of the Levinson algorithm for Hermitian Toeplitz matrices with any rank profile, IEEE trans. acoustics speech signal process, \scassp-33, 4, 964-971, (1985) [3] DeMillo, R.A.; Lipton, R.J., A probabilistic remark on algebraic program testing, Inform. process. lett., 7, 4, 193-195, (1978) · Zbl 0397.68011 [4] Dı́az, A.; Kaltofen, E., \scfoxbox a system for manipulating symbolic objects in black box representation, (), 30-37 · Zbl 0918.68049 [5] Dress, A.; Grabmeier, J., The interpolation problem for k-sparse polynomial and character sums, Adv. appl. math., 12, 57-75, (1991) · Zbl 0735.11066 [6] Emiris, I.Z., A complete implementation for computing general dimensional convex hulls, Int. J. comput. geom. appl., 8, 2, 223-254, (1998) · Zbl 1035.68529 [7] Freeman, T.S.; Imirzian, G.; Kaltofen, E.; Lakshman Yagati, \scdagwood A system for manipulating polynomials given by straight-line programs, ACM trans. math. software, 14, 3, 218-240, (1988) · Zbl 0825.68435 [8] Gantmacher, F.R., The theory of matrices, vol. 1, (1977), Chelsea publishing company · Zbl 0085.01001 [9] Giesbrecht, M.; Kaltofen, E.; Lee, W.-s, Algorithms for computing sparsest shifts of polynomials in power, Chebychev, and Pochhammer bases, J. symbolic comput., (2003), (to appear 27 pages). In the special issues on papers of the 2003 Internat. Symp. Symbolic Algebraic Comput. (doi: 10.1016/S0747-7171(03)00087-7) [10] Giesbrecht, M.; Kaltofen, E.; Lee, W.-s., Algorithms for computing the sparsest shifts for polynomials via the berlekamp/Massey algorithm, (), 101-108 · Zbl 1072.68669 [11] Gohberg, I.; Koltracht, I., Efficient algorithm for Toeplitz plus Hankel matrices, Integral equations operator theory, 12, 136-142, (1989) · Zbl 0671.65020 [12] Grigoriev, D.Y.; Karpinski, M.; Singer, M.F., Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM J. comput., 19, 6, 1059-1063, (1990) · Zbl 0711.68059 [13] Grigoriev, D.Y.; Karpinski, M.; Singer, M.F., The interpolation problem for k-sparse sums of eigenfunctions of operators, Adv. appl. math., 12, 76-81, (1991) · Zbl 0785.12004 [14] Grigoriev, D.Y.; Karpinski, M.; Singer, M.F., Computational complexity of sparse rational function interpolation, SIAM J. comput., 23, 1-11, (1994) · Zbl 0802.68060 [15] Hardy, G.H.; Wright, E.M., An introduction to the theory of numbers, (1979), Oxford University Press Oxford · Zbl 0423.10001 [16] Kaltofen, E.; Lakshman, Y.N.; Wiley, J.M., Modular rational sparse multivariate polynomial interpolation, (), 135-139 [17] Kaltofen, E.; Lakshman Yagati, Improved sparse multivariate polynomial interpolation algorithms, (), 467-474 [18] Kaltofen, E.; Lee, W.-s.; Lobo, A.A., Early termination in ben-or/tiwari sparse interpolation and a hybrid of zippel’s algorithm, (), 192-201 · Zbl 1326.68358 [19] Kaltofen, E.; Lobo, A., On rank properties of Toeplitz matrices over finite fields, (), 241-249 · Zbl 0914.65039 [20] Kaltofen, E.; Trager, B., Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, J. symbolic comput., 9, 3, 301-320, (1990) · Zbl 0712.12001 [21] Lakshman, Y.N.; Saunders, B.D., Sparse polynomial interpolation in non-standard bases, SIAM J. comput., 24, 2, 387-397, (1995) · Zbl 0827.68058 [22] Lee, W., 2001. Early termination strategies in sparse interpolation algorithms. Ph.D. Thesis. North Carolina State University, Raleigh, North Carolina, USA, p. 107 [23] Massey, J.L., Shift-register synthesis and BCH decoding, IEEE trans. inform. theory, \scit-15, 122-127, (1969) · Zbl 0167.18101 [24] Prony, R., Floréal et Prairial III (1795). Essai expérimental et analytique sur les lois de la Dilatabilité des fluides élastiques et sur celles de la Force expansive de la vapeur de l’eau et de la vapeur de l’alkool, à différentes températures. J. de l’École Polytechnique 1, 24-76, R. Prony is Gaspard(-Clair-François-Marie) Riche, baron de Prony [25] Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 701-717, (1980) · Zbl 0452.68050 [26] Wiedemann, D., Solving sparse linear equations over finite fields, IEEE trans. inform. theory, \scit 32, 54-62, (1986) · Zbl 0607.65015 [27] Zilic, Z.; Radecka, K., On feasible multivariate polynomial interpolations over arbitrary fields, (), 67-74 [28] Zippel, R.E., Probabilistic algorithms for sparse polynomials, (), 216-226 [29] Zippel, R.E., 1979b. Probabilistic algorithms for sparse polynomials. Ph.D. Thesis. Massachusetts Institute of Technology, Cambridge, USA · Zbl 0418.68040 [30] Zippel, R.E., Interpolating polynomials from their values, J. symbolic comput., 9, 3, 375-403, (1990) · Zbl 0702.65011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.