Efficiency, Structure and Robustness in Algebraic Computation

代数计算的效率、结构和鲁棒性

• 批准号: RGPIN-2018-04950
• 负责人: Giesbrecht, Mark
• 金额: $ 2.99万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=651851
• 关键词: Efficiency; Structure; Robustness; Algebraic; Computation

This proposal describes a comprehensive program of research into the design, analysis and implementation of algorithms for foundational problems in symbolic mathematical computation. My work will both explore fundamental scientific problems and allow commercial software like Maple and Mathematica to address new applications at a scale beyond their current reach. It will allow computers 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 three specific areas: algorithms for sparse polynomials, symbolic and exact linear algebra with sparse matrices, and symbolic-numeric algorithms for approximate polynomials and matrices. A common thread in my projects is a focus on exploiting sparsity (many zeros or “gaps” in the descriptions of data) and succinct representations. We will develop faster methods to solve key mathematical problems with sparse data representations, explore the underlying computational complexities, and provide fast implementations which can be applied to huge problem instances arising in data science, cryptography and control systems.******Polynomials are a key tool for describing simple but fundamental mathematical functions. Discovering sparse representations, where terms with a coefficient of zero are not represented, is the classical problem of sparse interpolation. Methods have been known for 300 years, but there is still much room for improvement. Other operations with sparse polynomials such as factorization and decomposition live on the frontier of what is practical and what is intractable. Our goal is to reduce costs for sparse interpolation to near optimal, and to design efficient algorithms for manipulating sparse polynomials.******Methods for finding exact solutions to huge systems of sparse linear equations are becoming central tools for symbolic computation, and many applications are now reduced to this. We will seek new algorithms that are provably faster than any previously known, for both solving systems and classifying all possible solutions through diagonalization (Smith form).******We will address symbolic-numeric problems, allowing for inexact data and solutions in sparse interpolation and linear systems of polynomial equations. We will combine modern computer algebra methods with recent advances in sparse reconstruction and optimization to achieve faster and provably robust algorithms for problems at the nexus of scientific computing and computational algebra. ******I will continue my record over the past decade of training exceptionally talented and highly qualified personnel at the Master's and PhD level, who go on to top-level positions in academia and industry. Our 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等商业软件以超出其当前范围的规模解决新的应用程序。 它将允许计算机精确地操纵和求解大型复杂的方程组，即使某些量是未知的，并作为变量。我的研究将集中在三个具体领域：算法稀疏多项式，符号和精确线性代数稀疏矩阵，符号数值算法近似多项式和矩阵。 在我的项目中，一个共同的思路是专注于利用稀疏性（数据描述中的许多零或“间隙”）和简洁的表示。 我们将开发更快的方法来解决具有稀疏数据表示的关键数学问题，探索潜在的计算复杂性，并提供可应用于数据科学，密码学和控制系统中出现的巨大问题实例的快速实现。多项式是描述简单但基本的数学函数的关键工具。 发现稀疏表示，其中系数为零的项不表示，是稀疏插值的经典问题。 这些方法已经有300年的历史了，但仍有很大的改进空间。 稀疏多项式的其他操作，如因式分解和分解，都处于实用和棘手的前沿。 我们的目标是将稀疏插值的成本降低到接近最优，并设计有效的算法来操作稀疏多项式。寻找稀疏线性方程组的精确解的方法正在成为符号计算的核心工具，现在许多应用都归结于此。 我们将寻求新的算法，可以证明比以前任何已知的算法都快，用于解决系统并通过对角化（史密斯形式）对所有可能的解决方案进行分类。我们将解决符号-数值问题，允许稀疏插值和多项式方程线性系统中的不精确数据和解决方案。 我们将结合联合收割机现代计算机代数方法与稀疏重建和优化的最新进展，以实现更快和可证明的强大算法的科学计算和计算代数的关系的问题。****** 我将继续我在过去十年中培养硕士和博士水平的杰出人才和高素质人才的记录，这些人才将继续在学术界和工业界担任顶级职位。 我们的算法进步将在顶级科学场所发表，并在Maple，SAGE和LinBox等符号代数软件中实现，并将向所有人开放。