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.

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