Grant: Discovery Grants Program - Individual
Simon Fraser University
$32,000.00
Parallel Algorithms for Polynomials
FY 2017-18
Summary
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 algebraicnumbers 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 byScientists, Engineers and Mathematicians in both industry and academia for their work. The researcher on thisproposal 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 andthe only way now to improve performance of software is to exploit their multi-coreprocessing 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 beginexperimenting with using Graphics Processing Units (GPUs) for implementing algorithms.A second focus of the research is how to interpolate, that is, how to reconstructpolynomials 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 algorithmsfor solving various problems in computational mathematics like factoring polynomials and fast algorithms for solvingproblems 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.)
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2014-04238
Name nom
Monagan, Michael
Department département
Mathematics
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2014
Award amount
32000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2704
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Distributed and parallel processing
Research subject fr
Traitement réparti et simultané
Partie
4
Nb partie
5
Application title
Parallel Algorithms for Polynomials
Keyword
NSERC
Application summary
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 algebraicnumbers 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 byScientists, Engineers and Mathematicians in both industry and academia for their work. The researcher on thisproposal 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 andthe only way now to improve performance of software is to exploit their multi-coreprocessing 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 beginexperimenting with using Graphics Processing Units (GPUs) for implementing algorithms.A second focus of the research is how to interpolate, that is, how to reconstructpolynomials 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 algorithmsfor solving various problems in computational mathematics like factoring polynomials and fast algorithms for solvingproblems 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.)