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

符号计算问题的解决至少可以通过两种方式来加速：一种是在标量上集成有限精度浮点运算，另一种是使用并行处理。我们提出了研究真实的代数优化和精确线性代数问题的方法。半定数值优化产生多项式不等式的平方和表示，表示全局最优性。 但表示是数值和近似的，并且通过精确的符号手段导出不等式的精确有理证明，从而导致真正的混合符号-数值算法。 当浮点运算和随机化相结合时，分析随机中间问题的期望条件数可以保证成功。 我们建议引入分数自由算法，并分析所产生的行列式条件数。LinBox是一个C++库的精确线性代数。 我们建议通过调查内存争用问题和创建交互式符号超级计算环境来参与LinBox库的并行化。 计算代数复杂性中的几个相关问题将受到关注：线性代数问题的二次时间证书，对称线性矩阵形式的多项式行列式表示，以及超解析（缺项）有理函数的插值。PI的研究扩展了符号计算的基础设施和对潜在复杂性的理解。 除了证明最优值，精确平方和证书还证明了数学、物理和控制理论中的定理。 LinBox的一些重要应用是有限域上的稀疏线性代数和计算拓扑数据的整数Smith形式。 数学思维和计算已经成为现代科学（纯科学和应用科学）和现代生活的基石。 Mathematica、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.