AF: Small: Efficient Exact/Certified Symbolic Computation By Hybrid Symbolic-Numeric and Parallel Methods

符号计算问题的求解至少可以通过两种方式来加速：一种是在标量上积分有限精度的浮点运算，另一种是使用并行处理。我们建议研究实代数优化和精确线性代数中的这些方法。半定数值优化产生多项式不等式的平方和表示，它表示全局最优性。但这些表示是数值的和近似的，并且通过精确的符号方法导出了关于这些不等式的精确有理证书，从而导致了真正的符号-数值混合算法。当浮点运算和随机化相结合时，分析随机中间问题的期望条件数可以保证成功。我们建议引入无分数的算法，并分析产生的行列式条件数。LinBox是一个用于精确线性代数的C库。我们建议通过研究内存争用问题和创建交互式符号超级计算环境来参与LinBox库的并行化。计算代数复杂性中的几个相关问题将受到关注：线性代数问题的二次时间证书，多项式的对称线性矩阵形式的行列式表示，以及超解析(空位)有理函数的内插。PI的研究扩展了符号计算的基础设施和对潜在复杂性的理解。除了证明最优外，精确平方和证书还证明了数学、物理和控制理论中的定理。LinBox的一些重要应用是有限域上的稀疏线性代数和用于计算拓扑数据的整数Smith形式。PI使开发的软件免费可用。算法思想和计算已成为现代科学(纯粹的和应用的)和现代生活的基石。符号计算程序如数学、Maple和SAGE平台有许多应用，如丰田和壳牌石油的符号表达式数据集建模、信号处理程序生成以及程序和协议验证。

The solution of symbolic computation problems can be accelerated in at least two ways: one is to integrate limited precision floating point arithmetic on the scalars, and the other is to use parallel processes. We propose to investigate those approaches on problems in real algebraic optimization and exact linear algebra.Semidefinite numerical optimization produces sum-of-squares representations for polynomial inequalities, which express global optimality. But the representations are numeric and approximate, and exact rational certificates for the inequalities are derived via exact symbolic means, thus leading to truly hybrid symbolic-numeric algorithms. When combining floating point arithmetic and randomization, analysis of the expected condition numbers of the random intermediate problems can guarantee success. We propose to introduce fraction-free algorithms and analyze the arising determinantal condition numbers.LinBox is a C++ library for exact linear algebra. We propose to participate in the parallelization of the LinBox library by investigating problems with memory contention and by creating interactive symbolic supercomputing environments. Several related problems in computational algebraic complexity that will receive attention are: quadratic-time certificates for linear algebra problems, determinantal representation of polynomials by symmetric linear matrix forms, and interpolation of supersparse (lacunary) rational functions.The PI's research expands the infrastructure in symbolic computation and the understanding of the underlying complexity. Aside from certifying optima, exact sums-of-squares certificates have proved theorems in mathematics, physics and control theory. Some of the important applications of LinBox are sparse linear algebra over finite fields and integer Smith forms for computational topology data. The PI is making the developed software freely available.Algorithmic thinking and computation have become a cornerstone of modern science (pure and applied) and modern life. Symbolic computation programs, such as Mathematica, Maple, and the SAGE platform, have many applications, such as modeling data sets by symbolic expression for Toyota and Shell Oil, generating programs for signal processing, and program and protocol verification.