High Performance Algorithms for Sparse and Structured Symbolic Computations

用于稀疏和结构化符号计算的高性能算法

• 批准号: 155376-2013
• 负责人: Giesbrecht, Mark
• 金额: $ 2.62万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634918
• 关键词: Performance; Algorithms; Sparse; Structured; Symbolic

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.

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