On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms

ABSTRACT

Algebraic randomization techniques can be applied to hybrid symbolic-numeric algorithms. Here we consider the problem of interpolating a sparse rational function from noisy values. We develop a new hybrid algorithm based on Zippel's original sparse polynomial interpolation technique. We show experimentally that our algorithm can handle sparse polynomials with large degrees. We also give a (partial) mathematical justification why the Zippel's algebraic randomization technique can be used with our approximate data: the randomly generated non-zero values are expected to be bounded away from zero. We show that the random Fourier-like matrices arising in our algorithm, have the desired rank property in the exact case, and appear usable numerically.

Algebraic randomization techniques can be applied to hybrid symbolic-numeric algorithms. Here we consider the problem of interpolating a sparse rational function from noisy values. We develop a new hybrid algorithm based on Zippel's original sparse polynomial interpolation technique. We show experimentally that our algorithm can handle sparse polynomials with large degrees. We also give a (partial) mathematical justification why the Zippel's algebraic randomization technique can be used with our approximate data: the randomly generated non-zero values are expected to be bounded away from zero. We show that the random Fourier-like matrices arising in our algorithm, have the desired rank property in the exact case, and appear usable numerically.

REFERENCES

• 1: Bharucha-Reid, A. T., and Sambandham, M. Random Polynomials Academic Press, INC, London, England, 1986.
• 2: Chen, L., Eberly, W., Kaltofen, E., Saunders, B. D., Turner, W. J., and Villard, G. Efficient matrix preconditioners for black box linear algebra. Linear Algebra and Applications 343--344 (2002), 119--146. Special issue on Structured and Infinite Systems of Linear Equations edited by P. Dewilde, V. Olshevsky and A. H. Sayed.
• 3: Zizhong Chen , Jack J. Dongarra, Condition Numbers of Gaussian Random Matrices, SIAM Journal on Matrix Analysis and Applications, v.27 n.3, p.603-620, July 2005 [doi>10.1137/040616413]
• 4: Robert M. Corless , Patrizia M. Gianni , Barry M. Trager , Stephen M. Watt, The singular value decomposition for polynomial systems, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.195-207, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220371]
• 5: Corless, R. M., Watt, S. M., and Zhi, L. QR factoring to compute the GCD of univariate approximate polynomials. IEEE Transactions on Signal Processing 52 (Dec. 2004), 3394--3402.
• 6: DeMillo, R. A., and Lipton, R. J. probabilistic remark on algebraic program testing. Information Process. Letters 7 4 (1978), 193--195.
• 7: Dumas, J.-G. Ed. ISSAC MMVI Proc. 2006 Internat. Symp. Symbolic Algebraic Comput. (New York, N.Y., 2006), ACM Press.
• 8: Dunaway, D. K. Calculation of zeros of a real polynomial through factorization using Euclid's algorithm. SIAM J. Numer. Anal. 11 6 (1974), 1087--1104.
• 9: Edelman, A., and Kostlan, E. How many zeros of a random polynomial are real. Bulletin of the American Mathematical Society 32 1 (1995), 1--37.
• 10: Farahmand, K. Algebraic polynomials with random coefficients. Journal of Applied Mathematics and Stochastic Analysis 15 1 (2002), 83--88.
• 11: Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Mathematics of Computation, v.72 n.242, p.801-822, 1 April 2003 [doi>10.1090/S0025-5718-02-01428-X]
• 12: Shuhong Gao , Erich Kaltofen , John May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials via differential equations, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.167-174, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005311]
• 13: Joachim von zur Gathen, Irreducibility of multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.225-264, Sept. 1985 [doi>10.1016/0022-0000(85)90043-1]
• 14: Mark Giesbrecht , George Labahn , Wen-shin Lee, Symbolic-numeric sparse interpolation of multivariate polynomials, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145792]
• 15: Marc Giusti , Éric Schost, Solving some overdetermined polynomial systems, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.1-8, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309838]
• 16: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 17: Joos Heintz , Teresa Krick , Susana Puddu , Juan Sabia , Ariel Waissbein, Deformation techniques for efficient polynomial equation solving, Journal of Complexity, v.16 n.1, p.70-109, March 2000 [doi>10.1006/jcom.1999.0529]
• 18: Kac, M. On the average number of real roots of a random algebraic equation. Bulletin of the American Mathematical Society 49 (1943), 314--320.
• 19: Kai, H. Rational interpolation and its ill-conditioned property. In Wang and Zhi {41}, pp. 47--53.
• 20: Kaltofen, E. Effective Hilbert irreducibility. Information and Control 66 (1985), 123--137.
• 21: Erich Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM (JACM), v.35 n.1, p.231-264, Jan. 1988 [doi>10.1145/42267.45069]
• 22: Kaltofen, E. Factorization of polynomials given by straight-line programs. In Randomness and Computation S. Micali, Ed., vol. 5 of Advances in Computing Research JAI Press Inc., Greenwhich, Connecticut, 1989, pp. 375--412.
• 23: Erich Kaltofen, Asymptotically fast solution of Toeplitz-like singular linear systems, Proceedings of the international symposium on Symbolic and algebraic computation, p.297-304, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190431]
• 24: Erich Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, v.64 n.210, p.777-806, April 1995 [doi>10.2307/2153451]
• 25: Erich Kaltofen, Effective Noether irreducibility forms and applications, Journal of Computer and System Sciences, v.50 n.2, p.274-295, April 1995
• 26: Kaltofen, E., May, J., Yang, Z., and Zhi, L. Approximate factorization of multivariate polynomials using singular value decomposition. Manuscript, 22 pages. Submitted, Jan. 2006.
• 27: Erich Kaltofen , B. David Saunders, On Wiedemann's Method of Solving Sparse Linear Systems, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.29-38, October 07-11, 1991
• 28: Erich Kaltofen , Gilles Villard, On the complexity of computing determinants, Computational Complexity, v.13 n.3-4, p.91-130, February 2005 [doi>10.1007/s00037-004-0185-3]
• 29: Erich Kaltofen , Zhengfeng Yang, On exact and approximate interpolation of sparse rational functions, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277577]
• 30: Erich Kaltofen , Zhengfeng Yang , Lihong Zhi, Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145799]
• 31: Kaltofen, E., Yang, Z., and Zhi, L. Structured low rank approximation of a Sylvester matrix. In Wang and Zhi {41}, pp. 69--83.
• 32: Lemmerling, P., Mastronardi, N., and Van Huffel, S. Fast algorithm for solving the Hankel/Toeplitz Structured Total Least Squares problem. Numerical Algorithms 23 (2000), 371--392.
• 33: Bernard Mourrain , Philippe Trebuchet, Generalized normal forms and polynomial system solving, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.253-260, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073920]
• 34: Park, H., Zhang, L., and Rosen, J. B. Low rank approximation of a Hankel matrix by structured total least norm. BIT 39 4 (1999), 757--779.
• 35: Reid, G., and Zhi, L. Solving nonlinear polynomial system via symbolic-numeric elimination method. In Proceedings of the International Conference on Polynomial System Solving (Paris, France, 2004).
• 36: T. Sasaki , M. Noda, Approximate square-free decomposition and root-finding of lll-conditioned algebraic equations, Journal of Information Processing, v.12 n.2, p.159-168, Jan. 1989
• 37: Sasaki, T., Suzuki, M., Kolář, M., and Sasaki, M. Approximate factorization of multivariate polynomials and absolute irreducibility testing. Japan J. of Industrial and Applied Mathem. 8 3 (Oct. 1991), 357--375.
• 38: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 39: Van H. Vu , Terence Tao, The condition number of a randomly perturbed matrix, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250828]
• 40: Šparo, D. I., and Šur, M. G. On the distribution of roots of random polynomials. Vestn. Mosk. Univ., Ser. 1: Mat., Mekh. (1962), 40--53.
• 41: Dongming Wang , Li-Hong Zhi, Symbolic-Numeric Computation (Trends in Mathematics), Birkhäuser Basel, 2007
• 42: D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]
• 43: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
• 44: Richard Zippel, Interpolating polynomials from their values, Journal of Symbolic Computation, v.9 n.3, p.375-403, March 1990 [doi>10.1016/S0747-7171(08)80018-1]
• 45: Zippel, R. E. Probabilistic algorithms for sparse polynomials PhD thesis, Massachusetts Inst. of Technology, Cambridge, USA, Sept. 1979.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

General Terms:
Algorithms, Experimentation, Theory

Keywords:
condition number, interpolation, multivariate rational function, probabilistic analysis, random matrix, sparse polynomial, structured matrix, symbolic/numeric hybrid method