Optimization, Randomization, and Generalization in Symbolic Computation

符号计算中的优化、随机化和泛化

• 批准号: 9988177
• 负责人: Erich Kaltofen
• 金额: $ 26.22万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-06-01 至 2003-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9988177&HistoricalAwards=false
• 关键词: Optimization; Randomization; Generalization; Symbolic; Computation

Erich Kaltofen proposes to study mathematical optimization techniques on problem formulations that are imprecise due to numerical data; randomization techniques that are the power tools in the design of fast algorithms with exact arithmetic on black box matrices; and generalization of the computer programs that implement these algorithms to multiple domains with methodologies such as generic, reusable programming and interface protocols. A difficulty in the symbolic/numeric area is that inputs with imprecise coefficients as a result of a physical measurement or a numerical computation can lack a known property that is of interest. For example, instead of a double real root, a polynomial has two conjugate complex roots that are very close together. The optimization problem is to compute efficiently the nearest input that has the desired singularity.Our focus will be on the nearest pair of polynomials with a common root under coefficient-wise change (infinity norm), the nearest singular Toeplitz matrix, and the nearest bi-variate complex polynomial that factors over the complex numbers, the latter two under any reasonable norm. A black box matrix is stored as a function that performs the matrix-times vector product. Efficient algorithms for performing linear algebra computations with exact field arithmetic, such as solving a linearsystem with a black box coefficient matrix, are based on the Lanczos/Wiedemann approach.Randomization techniques, for instance, matrix pre-conditioning and Krylov sub-spacing with random projections, avoid self-orthogonality when the coefficients are from a finite field and general algorithmicbreak-down due to certain invariant factors of the matrix. We propose to investigate how the different linear algebra problems are interelated, for example if the computation of a solution of an inhomogeneous black box linear system can be efficiently reduced to the computation of a column dependency of a black box matrix. Generic programming is a software design technique that generalizes a program so that it can be used with more than one underlying domain. The proposed implementation of our black box algorithms notonly permits the plug-in of a black box matrix over a native coefficient field, but the code also imports internally needed operations like polynomial and vector operations from expertly fine-tuned existing packages across generic interfaces. Our library's application program interface provides a serialization mechanism for black box objects that is compliant with the MathML/OpenMath philosophy and that allowsInternet communication. Finally, we propose research on two classical problems. First, the polynomial-time computation of dense, low-degree factors of high-degree sparse multi-variate polynomials with rational coefficients, which would generalize a recent related result by Hendrik W. Lenstra, Jr. Second, a time- and space-efficient realization of the transposition principle for transforming a matrix-times-vector function to the transpose vector-times-matrix operation.

Erich Kaltofen 提议研究因数值数据而不精确的问题表述的数学优化技术；随机化技术是设计快速算法的强大工具，对黑盒矩阵进行精确算术；以及使用通用、可重用编程和接口协议等方法将这些算法实现到多个领域的计算机程序的泛化。 符号/数字领域的困难在于，由于物理测量或数值计算而导致的具有不精确系数的输入可能缺乏感兴趣的已知属性。例如，多项式具有两个非常接近的共轭复根，而不是双实根。 优化问题是有效地计算具有所需奇异性的最近输入。我们的重点将是在系数变化（无穷范数）下具有公共根的最近的多项式对、最近的奇异 Toeplitz 矩阵和最近的 bi -对复数进行因式分解的变量复多项式，后两者在任何合理的范数下。 黑盒矩阵存储为执行矩阵乘向量乘积的函数。 使用精确域算术执行线性代数计算的高效算法（例如使用黑盒系数矩阵求解线性系统）基于 Lanczos/Wiedemann 方法。随机化技术，例如矩阵预处理和随机 Krylov 子间距投影，避免当系数来自有限域时的自正交性以及由于矩阵的某些不变因素而导致的一般算法崩溃。我们建议研究不同的线性代数问题如何相互关联，例如，非齐次黑盒线性系统的解的计算是否可以有效地简化为黑盒矩阵的列依赖性的计算。 通用编程是一种软件设计技术，它概括了一个程序，以便它可以用于多个底层领域。 我们所提出的黑盒算法的实现不仅允许在本机系数域上插入黑盒矩阵，而且代码还可以跨通用接口从经过专业微调的现有包中导入内部所需的操作，例如多项式和向量运算。我们库的应用程序接口为黑盒对象提供了一种序列化机制，该机制符合 MathML/OpenMath 哲学并允许互联网通信。 最后，我们提出对两个经典问题的研究。首先，具有有理系数的高次稀疏多元多项式的稠密、低次因子的多项式时间计算，这将概括 Hendrik W. Lenstra, Jr. 最近的相关结果。其次，时间和空间-有效实现将矩阵乘向量函数转换为转置向量乘矩阵运算的转置原理。