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

摘要：一个自然（例如，人的心跳）或人造过程（例如，无线信号的无线电波）是在评估系统参数（诸如时间点）时产生模型值的数学表达式或算法（例如，波的振幅）。 模型是通过对过程的理解，即对表达形式的理解，以及对实际过程的观察和测量而建立起来的。 从这些数据点，最好的模型是通过计算拟合。 Erich Kaltofen研究了如何拟合某些模型，例如稀疏多项式的分数，然后如何证明计算产生了最佳模型。 创建最佳拟合和随后的最优性验证的算法可能是计算密集型的，需要多处理器计算环境。Erich Kaltofen和他的学生以及合作者将为符号模型设计算法，例如稀疏多变量有理函数和具有非常大和均匀参数指数的公式。 我们的算法可以与精确和近似的数据，后者通过混合符号/numerictechniques。 当随机化被应用时，浮点标量计算需要一种新的概率分析，我们将利用最近的结果估计随机矩阵的谱和条件数。 这种随机化的一个应用是高度欠定和超定稠密线性系统的有效解。误差分析的一个新的替代方法是通过符号计算精确验证我们的近似解的全局最优性。 半定规划和牛顿加细被用来计算一个数值平方和表示，它被转换为一个精确的合理的身份附近的合理的下限。 由于确切的证明是毫无疑问的，因此不需要完全分析数字逻辑，我们将寻找可以验证非常大的平方和并因此适用于大输入的合理化。 我们将开发并行和分布式计算工具，用于并行符号和混合符号-数值计算任务。

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.