fundamental problems in algorithmic algebra - chee keng yap

《fundamental problems in algorithmic algebra - chee keng yap》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、FundamentalProblemsinAlgorithmicAlgebraCheeKengYapCourantInstituteofMathematicalSciencesNewYorkUniversity251MercerStreetNewYork,NY10012September8,1993TOBEPUBLISHEDBYPRINCETONUNIVERSITYPRESSCopyrightReserve:Thispreliminaryversionmaybecopied,inpartorwholly

2、,forprivateuseprovidedthiscopyrightpageiskeptintactwitheachpartialorwholecopy.Forclassroomdistribution,pleaserequestpermis-sion.Contacttheauthorattheaboveaddressfortheon-goingchangestothemanuscript.Thereaderiskindlyrequestedtoinformtheauthorofanyerrors,t

3、ypographicalorotherwise.Allsuggestionswelcome.Electronicmail:yap@cs.nyu.edu.
cChee-KengYapSeptember8,1993Contents0.IntroductionI.BasicArithmeticII.TheGCDIII.SubresultantsIV.ModularTechniques:ChineseRemainderV.FundamentalTheoremofAlgebraVI.RootsofPolynomi

4、alsVII.SturmTheoryVIII.GaussianLatticeReductionIX.LatticesandPolynomialFactorizationX.EliminationTheoryXI.Gr¨obnerBasesXII.ContinuedFractions
cChee-KengYapSeptember8,1993PREFACEThesenoteswerefirstwrittenforacourseonAlgebraicComputing:SolvingSystemsofPoly-

5、nomialEquations,givenintheSpringSemesterof1989attheFreeUniversityofBerlin.TheywerethoroughlyrevisedfollowingasimilarcourseattheCourantInstituteintheSpringof1992.Prerequisitesareanundergraduatecourseinalgebraandagraduatecourseinalgorithmics.Iregardthiscou

6、rseasanintroductiontocomputeralgebra.Thesubjectmatter(‘startingfromtheFundamentalTheoremofAlgebra’)isasclassicalasonegetsintheoreticalcomputerscience,andyetitisrefreshinglycontemporaryininterest.Thisisbecausethecomplexityviewpointexposesmanyclassicalques

7、tionstonewlight.Thereisacommonmisunderstandingthatequatescomputationalmathematicswithnumericalanalysis.Infact,itseemstomethattheoldernameof“symbolicmanipulation”giventoourfieldaroseasadirectcontrastto“numericalcomputation”.Thepreferrednametodayis“computer

8、algebra”,althoughIfeelthat“algorithmicalgebra”givesabetteremphasistothefundamentalnatureofthesubject.Inanycase,computeralgebrausesquitedistincttechniques,andsatisfiesrequirementsdistinctfromthatinnumericalanalysis.Inmanyare