Model Discovery and Verification With Symbolic, Hybrid Symbolic-Numeric and Parallel Computation

点击翻译按钮获取中文摘要

ABSTRACT:A mathematical model for a natural (e.g., the heart beat of ahuman) or man-made process (e.g., the radio wave of a wirelesssignal) is a mathematical expression or an algorithm that onevaluation of system parameters (such as a point in time) yieldsa model value (e.g., the amplitude of a wave). Models arecreated by understanding the process, which suggests the formof the expression, and by observing and measuring an actualprocess. From those data points the best model is fitted bya computation. Erich Kaltofen studies both how to fit to datacertain models, such as fractions of sparse polynomials, andthen how to certify that the computation has produced the bestpossible model. The algorithms for creation of best fits andsubsequent certification of optimality can be compute-intensiveand require multi-processor computing environments.Erich Kaltofen and his students and collaborators will designalgorithms for symbolic models such as sparse multivariaterational functions and formulas with very large and evenparametric exponents. Our algorithms can work with both exactand approximate data, the latter by hybrid symbolic/numerictechniques. Computation with floating point scalars requiresa new kind of probabilistic analysis when randomization isapplied, and we will make use of recent results on estimatingthe spectra and condition numbers of random matrices. Oneapplication of such randomization is the efficient solutionof highly under- and overdetermined dense linear systems.A new alternative to error analysis is the exact validation viasymbolic computation of the global optimality of our approximatesolutions. Semidefinite programming and Newton refinementare used to compute a numerical sum-of-squares representation,which is converted to an exact rational identity for a nearbyrational lower bound. Since the exact certificates leave nodoubt, the numeric heuristics need not be fully analyzed.We will search for rationalizations that can validate verylarge sums-of-squares and hence apply to large inputs. We willdevelop parallel and distribute computing tools for the arisingsymbolic and hybrid symbolic-numeric computation tasks.