Parallel Algorithms for Polynomials

多项式的并行算法

• 批准号: RGPIN-2014-04238
• 负责人: Monagan, Michael
• 金额: $ 2.33万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=660055
• 关键词: Parallel; Algorithms; Polynomials

This research proposal is about designing and implementing algorithms for computing with mathematical formulas.*It focusses on computing with large polynomials in more than one variable and with large formulas involving algebraic*numbers like sqrt(2) and algebraic functions and sqrt(1+y^2).*Such formulas arise in many applications in Science, Engineering and Mathematics.**This research is part of a field known as Computer Algebra. It is also known as Symbolic Computation.*Researchers in this field design algorithms and software systems, called Computer Algebra Systems,*for doing algebra and calculus on the computer. Computer Algebra Systems like Maple and Mathematica are used by*Scientists, Engineers and Mathematicians in both industry and academia for their work. The researcher on this*proposal has been and continues to be involved with the design and development of Maple which is a Canadian product.**A focus of the proposal is the development and implementation of parallel algorithms.*This is because today's laptops, desktops and servers are all multi-core computers and*the only way now to improve performance of software is to exploit their multi-core*processing capability. We propose to use Cilk for implementing parallel algorithms.*Cilk was developed at MIT and has now been adopted by Intel. We also propose to begin*experimenting with using Graphics Processing Units (GPUs) for implementing algorithms.**A second focus of the research is how to interpolate, that is, how to reconstruct*polynomials and rational functions in more than one variable from their values.*Often formulas involving many variables are sparse and have structure.*We propose to try to automate the detection of this structure so we can interpolate them rapidly.**Some of the software we develop in this research will be written in Maple and some will be written in C and/or Cilk.*We do plan to make it available to the Maple user community so that Scientists, Engineers and Mathematicians can use it.*For the students working on these projects, it is very encouraging for them to see other people using their software.**Students who work on the research projects in this proposal will learn how to design and implement algorithms*for solving various problems in computational mathematics like factoring polynomials and fast algorithms for solving*problems involving matrices. They will learn how to design and implement parallel algorithms using Cilk.*They will be learning mathematics (e.g. about algebraic numbers) and computer science*(e.g. how to analyze the efficiency of algorithms.)

本研究计划是关于设计和实现使用数学公式进行计算的算法。它专注于计算多个变量的大型多项式和涉及代数 * 数的大型公式，如sqrt（2）和代数函数和sqrt（1+y^2）。这样的公式在科学、工程和数学中有许多应用。这项研究是计算机代数领域的一部分。 它也被称为符号计算。该领域的研究人员设计算法和软件系统，称为计算机代数系统 *，用于在计算机上进行代数和微积分。 像Maple和Mathematica这样的计算机代数系统被工业界和学术界的科学家、工程师和数学家用于他们的工作。 这项建议的研究人员一直并将继续参与加拿大产品Maple的设计和开发。该提案的重点是并行算法的开发和实现。*这是因为今天的笔记本电脑、台式机和服务器都是多核计算机，* 现在提高软件性能的唯一方法就是利用它们的多核 * 处理能力。 我们建议使用Cilk来实现并行算法。Cilk是在麻省理工学院开发的，现在已经被英特尔采用。 我们还建议开始 * 试验使用图形处理器（GPU）实现算法。**研究的第二个焦点是如何插值，即如何从多项式和有理函数的值重构多个变量的多项式和有理函数。通常，涉及许多变量的公式是稀疏的，并且具有结构。我们建议尝试自动检测这种结构，以便我们可以快速插入它们。我们在这项研究中开发的一些软件将用Maple编写，一些将用C和/或Cilk编写。我们确实计划将其提供给Maple用户社区，以便科学家、工程师和数学家可以使用它。*对于从事这些项目的学生来说，看到其他人使用他们的软件对他们来说是非常鼓舞人心的。谁在这个建议的研究项目工作的学生将学习如何设计和实现算法 * 解决计算数学中的各种问题，如分解多项式和快速算法解决 * 涉及矩阵的问题。 他们将学习如何使用Cilk设计和实现并行算法。*他们将学习数学（例如代数数）和计算机科学（例如如何分析算法的效率）。