High Performance Algorithms for Sparse and Structured Symbolic Computations

点击翻译按钮获取中文摘要

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.