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 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.