fundamental problems in algorithmic algebra 1993 yap

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

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

2、ightpageiskeptintactwitheachpartialorwholecopy.Forclassroomdistribution,pleaserequestpermis-sion.Contacttheauthorattheaboveaddressfortheon-goingchangestothemanuscript.Thereaderiskindlyrequestedtoinformtheauthorofanyerrors,typographicalorotherwise.Allsuggestionswelcome.Electronicmail:y

3、ap@cs.nyu.edu.
cChee-KengYapSeptember8,1993Contents0.IntroductionI.BasicArithmeticII.TheGCDIII.SubresultantsIV.ModularTechniques:ChineseRemainderV.FundamentalTheoremofAlgebraVI.RootsofPolynomialsVII.SturmTheoryVIII.GaussianLatticeReductionIX.LatticesandPolynomialFactorizationX.Elimina

4、tionTheoryXI.Gr¨obnerBasesXII.ContinuedFractions
cChee-KengYapSeptember8,1993PREFACEThesenoteswerefirstwrittenforacourseonAlgebraicComputing:SolvingSystemsofPoly-nomialEquations,givenintheSpringSemesterof1989attheFreeUniversityofBerlin.Theywerethoroughlyrevisedfollowingasimilarcourseat

5、theCourantInstituteintheSpringof1992.Prerequisitesareanundergraduatecourseinalgebraandagraduatecourseinalgorithmics.Iregardthiscourseasanintroductiontocomputeralgebra.Thesubjectmatter(‘startingfromtheFundamentalTheoremofAlgebra’)isasclassicalasonegetsintheoreticalcomputerscience,andye

6、titisrefreshinglycontemporaryininterest.Thisisbecausethecomplexityviewpointexposesmanyclassicalquestionstonewlight.Thereisacommonmisunderstandingthatequatescomputationalmathematicswithnumericalanalysis.Infact,itseemstomethattheoldernameof“symbolicmanipulation”giventoourfieldaroseasadir

7、ectcontrastto“numericalcomputation”.Thepreferrednametodayis“computeralgebra”,althoughIfeelthat“algorithmicalgebra”givesabetteremphasistothefundamentalnatureofthesubject.Inanycase,computeralgebrausesquitedistincttechniques,andsatisfiesrequirementsdistinctfromthatinnumericalanalysis.Inma

8、nyare