A mathematical model for a natural (e.g., the heart beat of a human) or man-made process (e.g., the radio wave of a wireless signal) is a mathematical expression or an algorithm that on evaluation of system parameters (such as a point in time) yields a model value (e.g., the amplitude of a wave). Models are created by understanding the process, which suggests the form of the expression, and by observing and measuring an actual process. From those data points the best model is fitted by a computation. Erich Kaltofen studies both how to fit to data certain models, such as fractions of sparse polynomials, and then how to certify that the computation has produced the best possible model. The algorithms for creation of best fits and subsequent certification of optimality can be compute-intensive and require multi-processor computing environments.
Erich Kaltofen and his students and collaborators will design algorithms for symbolic models such as sparse multivariate rational functions and formulas with very large and even parametric exponents. Our algorithms can work with both exact and approximate data, the latter by hybrid symbolic/numeric techniques. Computation with floating point scalars requires a new kind of probabilistic analysis when randomization is applied, and we will make use of recent results on estimating the spectra and condition numbers of random matrices. One application of such randomization is the efficient solution of highly under- and overdetermined dense linear systems. A new alternative to error analysis is the exact validation via symbolic computation of the global optimality of our approximate solutions. Semidefinite programming and Newton refinement are used to compute a numerical sum-of-squares representation, which is converted to an exact rational identity for a nearby rational lower bound. Since the exact certificates leave no doubt, the numeric heuristics need not be fully analyzed. We will search for rationalizations that can validate very large sums-of-squares and hence apply to large inputs. We will develop parallel and distribute computing tools for the arising symbolic and hybrid symbolic-numeric computation tasks.
