Parallel Algorithms for Polynomials

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

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.)