Parallel Algorithms for Polynomials

多项式的并行算法

• 批准号: RGPIN-2014-04238
• 负责人: Monagan, Michael
• 金额: $ 2.33万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=610915
• 关键词: 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和数学，由 工业界和学术界的科学家、工程师和数学家对他们的工作表示感谢。这方面的研究人员 Proposal一直并将继续参与加拿大产品Maple的设计和开发。 该提案的一个重点是并行算法的开发和实施。 这是因为今天的笔记本、台式机和服务器都是多核计算机，并且 现在提高软件性能的唯一方法是利用他们的多核 处理能力。我们建议使用CILK来实现并行算法。 Cilk是由麻省理工学院开发的，现在已被英特尔采用。我们还提议开始 尝试使用图形处理器(GPU)实现算法。 研究的第二个重点是如何进行插补，即如何重建 多项式和有理函数从它们的值到一个以上的变量。 通常，涉及多个变量的公式是稀疏的，并且具有结构。 我们建议尝试自动检测这种结构，这样我们就可以快速地对它们进行内插。 我们在这项研究中开发的一些软件将用Maple编写，另一些将用C和/或Cilk编写。 我们确实计划将它提供给Maple用户社区，这样科学家、工程师和数学家就可以使用它。 对于从事这些项目的学生来说，看到其他人使用他们的软件对他们来说是非常令人鼓舞的。 参与本提案中研究项目的学生将学习如何设计和实现算法 用于解决计算数学中的各种问题，如因式分解多项式和快速求解算法 涉及矩阵的问题。他们将学习如何使用Cilk设计和实现并行算法。 他们将学习数学(例如关于代数数)和计算机科学 (例如，如何分析算法的效率。)