High Performance Algorithms for Sparse and Structured Symbolic Computations

该提案描述了一个全面的研究计划，旨在设计，分析和实现符号数学计算中基础问题的算法。这些算法使Maple和Mathematica等商业数学软件得以运行。它们使我们能够精确地操纵和求解大型复杂的方程组，即使某些量是未知的，并作为变量。我的研究将集中在四个具体领域：稀疏多项式算法，近似多项式计算，符号稀疏线性代数，以及微分和差分算子矩阵的算法。所描述的项目的一个共同点是专注于利用稀疏性，即大量零或“洞”的存在。换句话说，如果我们希望解决的一个非常大的问题有一个非常简洁的描述，我们希望利用它来使我们的算法运行得更快，我们的算法和软件将帮助计算机处理现在在符号数学计算及其许多应用中挑战我们的巨大方程。它们将使我们能够以一种稳健和可验证的方式处理噪声和近似数据，并发现和表示底层结构。他们还将扩展Maple等符号计算软件的应用范围，以解决最困难和最重要的工业、科学和数学问题。这些项目都涉及广泛的合作和培训，为学生将来在学术界和工业界的职位提供培训。算法的进步将在顶级科学场所发表，并在Maple，SAGE和LinBox等符号代数软件中实现，并将向所有人开放。

This proposal describes a comprehensive program of research into the design, analysis and implementation of algorithms for foundational problems in symbolic mathematical computation. These are the algorithms that make commercial mathematical software like Maple and Mathematica run. They allow us to manipulate and solve large and complex sets of equations exactly, even when some quantities are unknown and left as variables.My research will centre on four specific areas: algorithms for sparse polynomials, approximate polynomial computation, symbolic sparse linear algebra, and algorithms for matrices of differential and difference operators. A common thread of the described projects is a focus on exploiting sparsity, the existence of lots of zeros or "holes". In other words, if a very large problem we wish to solve has a very succinct description, we want to use this to make our algorithms run more quickly.Our algorithms and software will help computers treat the enormous equations that now challenge us in symbolic mathematical computation and its many applications. They will allow us to handle noisy and approximate data in a robust and verifiable way, and to discover and represent the underlying structure. And they will extend the reach of symbolic computing software, like Maple, to address the most difficult and important industrial, scientific and mathematical problems.The projects all involve extensive collaboration and training of students for future positions in academia and industry. The algorithmic advances will be published in top scientific venues and implemented in symbolic algebra software such as Maple, SAGE and LinBox, and will be openly available for all.