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矩阵和最接近的双变量复杂的复杂的复杂的复杂多物质该因素超过了构件，而后两种合理的范围则是任何合理的范围。 将黑匣子矩阵作为执行矩阵矢量产品的函数存储。 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由于矩阵的某些不变因素，算法破坏了算法。我们建议研究如何相互关联的不同线性代数问题，例如，是否可以将不均匀黑框线性系统的解决方案有效地降低为黑匣子矩阵的列依赖关系的计算。 通用编程是一种软件设计技术，可以概括一个程序，以便可以与多个基础域一起使用。 我们的黑匣子算法的拟议实现允许在本机系数字段上插入黑匣子矩阵的插件，但是该代码还从跨通用接口的熟悉现有的现有软件包中导入内部需要的操作，例如多项式和向量操作。我们的图书馆的应用程序界面为黑匣子对象提供了一种符合MathML/OpenMath Pholicephone的序列化机制，并且可以允许使用通信。 最后，我们建议对两个经典问题进行研究。首先，具有合理系数的高度稀疏多变量多项式的密集，低度因素的多项式计算，这将概括亨德里克·兰斯特拉（Hendrik W.