zbMATH — the first resource for mathematics

Symbolic-numeric sparse interpolation of multivariate polynomials. (English) Zbl 1167.65003
Prony’s and other methods are used for symbolic interpolation using multivariate polynomials. The work includes an error analysis and an analysis of both the stability and the sensitivity of the process with the use of bounds on generalized eigenvalues. This is all for floating-point arithmetic and fixed precision. The discussions of the sensitivity and stability, as well as the conditioning of the interpolation problem, are based on probability estimates. Algorithms and examples for the application of the analysis are presented too.

65D05 Numerical interpolation
74A05 Kinematics of deformation
41A63 Multidimensional problems (should also be assigned at least one other classification number from Section 41-XX)
68W30 Symbolic computation and algebraic computation
FOXBOX; mctoolbox
Full Text: DOI
[1] Bazán, F.S.V., Conditioning of rectangular Vandermonde matrices with nodes in the unit disk, SIAM J. matrix anal. appl., 21, 2, 679-693, (2000) · Zbl 0952.15006
[2] Beckermann, B., The condition number of real Vandermonde, Krylov and positive definite Hankel matrices, Numer. math., 85, 553-577, (2000) · Zbl 0965.15003
[3] Beckermann, B.; Golub, G.H.; Labahn, G., On the numerical condition of a generalized Hankel eigenvalue problem, Numer. math., 106, 1, 41-68, (2007) · Zbl 1121.65036
[4] Ben-Or, M.; Tiwari, P., A deterministic algorithm for sparse multivariate polynomial interpolation, (), 301-309
[5] Cabay, S.; Meleshko, R., A weakly stable algorithm for Padé approximants and the inversion of Hankel matrices, SIAM J. matrix anal. appl., 14, 3, 735-765, (1993) · Zbl 0779.65009
[6] Córdova, A.; Gautschi, W.; Ruscheweyh, S., Vandermonde matrices on the circle: spectral properties and conditioning, Numer. math., 57, 577-591, (1990) · Zbl 0728.15003
[7] Corless, R.M.; Galligo, A.; Kotsireas, I.S.; Watt, S.M., A geometric – numeric algorithm for absolute factorization of multivariate polynomials, (), 37-45 · Zbl 1072.68658
[8] Corless, R.M., Gianni, P.M., Trager, B.M., Watt, S.M., 1995. The singular value decomposition for polynomial systems, In: Proc. 1995 Internat. Symp. Symbolic Algebraic Comput., ISSAC’95, pp. 96-103 · Zbl 0920.65034
[9] Corless, R.M.; Giesbrecht, M.; Kotsireas, I.; Watt, S.M., Numerical implicitization of parametric hypersurfaces with linear algebra, (), 174-183 · Zbl 1042.65020
[10] Corless, R.M.; Rezvani, N.; Amiraslani, A., Pseudospectra of matrix polynomials that are expressed in alternative bases, Math. comput. sci., 1, 2, 353-374, (2007) · Zbl 1136.15012
[11] Díaz, A., Kaltofen, E., 1998. \scFoxBox a system for manipulating symbolic objects in black box representation. In: Proc. 1998 Internat. Symp. Symbolic Algebraic Comput., ISSAC’98, pp. 30-37 · Zbl 0918.68049
[12] Gao, S., Kaltofen, E., May, J., Yang, Z., Zhi, L., 2004. Approximate factorization of multivariate polynomials via differential equations. In: Proc. 2004 Internat. Symp. Symbolic Algebraic Comput., ISSAC’04, pp. 167-174 · Zbl 1134.65346
[13] Gasca, M.; Sauer, T., On the history of multivariate polynomial interpolation, J. comput. appl. math., 122, 23-35, (2000) · Zbl 0968.65008
[14] Gautschi, W., Norm estimates for inverses of Vandermonde matrices, Numer. math., 23, 337-347, (1975) · Zbl 0304.65031
[15] Gautschi, W.; Inglese, G., Lower bounds for the condition numbers of Vandermonde matrices, Numer. math., 52, 241-250, (1988) · Zbl 0646.15003
[16] Geddes, K.O.; Czapor, S.R.; Labahn, G., Algorithms for computer algebra, (1992), Kluwer Academic Publ. Boston, MA, USA · Zbl 0805.68072
[17] Giesbrecht, M., Labahn, G., Lee, W.-s., 2006. Symbolic – numeric sparse interpolation of multivariate polynomials. In: Proc. 2006 Internat. Symp. Symbolic Algebraic Comput., ISSAC’06, pp. 116-123 · Zbl 1356.65032
[18] Golub, G.H.; Milanfar, P.; Varah, J., A stable numerical method for inverting shape from moments, SIAM J. sci. comput., 21, 4, 1222-1243, (1999) · Zbl 0956.65030
[19] Golub, G.H.; Van Loan, C.F., Matrix computations, (1996), Johns Hopkins University Press Baltimore, MD · Zbl 0865.65009
[20] Grigoriev, D.Yu.; 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
[21] Higham, N.J., Accuracy and stability of numerical algorithms, (2002), Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1011.65010
[22] Kaltofen, E.; Lee, W.-s., Early termination in sparse interpolation algorithms, J. symbolic comput., 36, 3-4, 365-400, (2003) · Zbl 1074.68080
[23] 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
[24] Kaltofen, E., Yang, Z., Zhi, L., 2007. On probabilistic analysis of randomization in hybrid symbolic – numeric algorithms. In: Proc. Internat. Workshop on Symbolic-Numeric Comput., SNC’07, pp. 11-17
[25] Kaltofen, E., Yagati, Lakshman, 1988, Improved sparse multivariate polynomial interpolation algorithms. In: Proc. 1988 Internat. Symp. Symbolic Algebraic Comput., ISSAC’88, pp. 467-474
[26] Kronecker, L.; Hensel, H.; Kroneckers Werke, L., Über einige interpolationsformeln für ganze funktionen mehrerer variabeln, lecture at the Academy of sciences, December 21, 1865, vol. I, (1895), Teubner Stuttgart, Reprinted by Chelsea, New York, 1968
[27] Lorentz, R., Multivariate Hermite interpolation by algebraic polynomials: A survey, J. comput. appl. math., 122, 167-201, (2000) · Zbl 0967.65008
[28] Mansour, Y., Randomized approximation and interpolation of sparse polynomials, SIAM J. comput., 24, 2, 357-368, (1995) · Zbl 0826.65005
[29] Milanfar, P.; Verghese, G.C.; Karl, W.C.; Wilsky, A.S., Reconstructing polygons from moments with connections to array processing, IEEE trans. signal process., 43, 2, 432-443, (1995)
[30] Riche, Gaspard Clair François Marie, Baron de prony. essai expérimental et analytique sur LES lois de la dilatabilité des fluides élastique 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, (1795)
[31] Sommese, A.; Verschelde, J.; Wampler, C., Numerical factorization of multivariate complex polynomials, Theoret. comput. sci., 315, 2-3, 651-669, (2004) · Zbl 1147.13302
[32] Sommese, A.; Verschelde, J.; Wampler, C., Introduction to numerical algebraic geometry, (), 339-392
[33] Sommese, A.J.; Verschelde, J.; Wampler, C.W., Numerical decomposition of the solution sets of polynomial systems into irreducible components, SIAM J. numer. anal., 38, 6, 2022-2046, (2001) · Zbl 1002.65060
[34] Wilkinson, J.H., Rounding errors in algebraic processes, (1963), Prentice-Hall Englewood Cliffs, NJ · Zbl 0868.65027
[35] Zilic, Z., Radecka, K., 1999. On feasible multivariate polynomial interpolations over arbitrary fields. In: Proc. 1999 Internat. Symp. Symbolic Algebraic Comput., ISSAC’99, pp. 67-74
[36] Zippel, R., Probabilistic algorithms for sparse polynomials, (), 216-226
[37] Zippel, R., 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.