Parallel Algorithms for 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.)