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

AF：小型：通过混合符号数字和并行方法进行高效精确/认证符号计算

• 批准号: 1115772
• 负责人: Erich Kaltofen
• 金额: $ 42.5万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-01 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115772&HistoricalAwards=false
• 关键词: AF; Small; Efficient; Exact; Certified

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.

符号计算问题的解决方案至少可以通过两种方式加速：一种是在标量上整合有限的精度浮点算术算术，另一个是使用并行过程。我们建议研究这些方法有关实际代数优化和精确线性代数的问题。SemideFinite数值优化产生了表达全局最佳性的多项式不平等的平方总和表示。 但是这些表示是数字且近似的，并且不等式的确切理性证书是通过精确的符号均值得出的，因此导致真正的混合符号数字算法。 在结合浮点算术和随机化时，对随机中间问题的预期状况数量的分析可以保证成功。 我们建议引入无分数算法并分析出现的确定条件数字。Linbox是精确线性代数的C ++库。 我们建议通过调查内存争论问题并创建交互式符号超级计算环境来参与LINBOX库的并行化。 将受到关注的计算代数复杂性中的几个相关问题是：线性代数问题的二次时间证书，通过对称线性矩阵形式对多项式的确定表示，以及supersparse（lacunary）的插值。计算和对潜在复杂性的理解。 除了认证Optima外，确切的方格证书还证明了数学，物理和控制理论的定理。 LINBOX的一些重要应用是有限字段上的稀疏线性代数和用于计算拓扑数据的整数史密斯形式。 PI可以免费提供开发的软件。Algorithmic的思维和计算已成为现代科学（纯净和应用）和现代生活的基石。 符号计算程序，例如Mathematica，Maple和Sage平台，都有许多应用程序，例如通过符号表达式对Toyota和Shell Oil的符号表达式建模数据集，生成信号处理程序以及程序和协议验证。