MITACS Seminar Series on Mathematics of Computer Algebra and Analysis
On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms.
Zhengfeng Yang, Department of Mathematics and Computing Science, NCSU
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 for why 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.