The Exact Solution of Linear Equation Systems on a

TheExactSolutionofLinearEquat[e-mail]@risc.uni-linz.ac.atResearchInstituteforSymbolicComputation(RISC-Linz)JohannesKeplerUniversity,A-4040Linz,AustriaTel.+437236323166;Fax:[phone]November1992AbstractWedescribethedesignofaparallelalgorithmfortheexactsolutionoflinearequa-tionsystemswithintegercoecientsandtheimplementationofthisalgorithmonasharedmemorymultiprocessor.Anecientsolutionoftheoriginalproblemisdi-cultsincethecoecientsgrowduringthecomputationandarithmeticbecomesverytime-consuming.Thereforewetransformtheproblemintoaproblemofdeterminantcomputationandapplyamodularapproach:thesystemismappedintoseveralniteeldswherethedeterminantscanbeecientlycomputed.Thesubresultsarecom-binedtoyieldtheoriginaldeterminantsandtocomputethesolutionsofthesystem.Severalparallelversionsofthisalgorithmhavebeendevelopedandimplementedonasharedmemorymultiprocessor.Theprogramsareappliedtoequationsystemsofdierentcharacteristicsandtheresultsareanalyzedandcompared.Keywords:Parallelalgorithms,scienticcomputing,computeralgebra,sharedmemorymachines.FundedbytheAustrianResearchAgencyFWFintheframeoftheprojectS5302-PHY\ParallelSymbolicComputation.01INTRODUCTION11IntroductionInscienticcomputing,muchresearchhasbeendevotedtotheparallelizationofnumeri-calalgorithms.Sincethesemethodsoperatewithecientnite-precision(oatingpoint)arithmetic,theyyieldfastapproximativesolutionsofscienticproblems.However,some-timesitisalsoimportanttodeterminetheexactsolutionsofsuchproblems.Thisisinparticularthecaseifnumericalmethods,bytheaccumulationofapproximationerrors,mayyieldqualitativelywronganswers.Computeralgebraisthatbranchofcomputersciencethataimstoprovideexactsolu-tionsofscienticproblems.Researchresultsofthisareaaree.g.algorithmsforsymbolicintegration,polynomialfactorizationortheexactsolutionofalgebraicequationsandin-equalities[2].Allthesealgorithmshavetooperatewitharbitraryprecisionarithmetic;theyarethereforemuchmoreexpensivewithrespecttotimeandspacethanthecorre-spondingnumericalmethods.ThustheparallelcomputationgroupatRISC-LinzhasstartedaprojectthatpursuesthedevelopmentofPaclib,alibraryofparallelalgorithmsbasedonthecomputeral-gebralibrarySaclib[4].PaclibhasbeenimplementedintheClanguageontopofaruntimekernelthatsupportsanecientandhigh-levelparallelprogrammingmodel[8].ThePaclibkernel[9]wasimplementedona20processorSequentSymmetry,aMIMDcomputerwithsharedmemory,butisinprincipleportabletoanyUNIXmachine.InthispaperwediscussthePaclibapproachtooneofthebasicproblemsincomputeralgebra:theexactsolutionofsystemsoflinearequationswitharbitrarilylargeintegercoecients.Theproblemitselfisnotofparticularinterest;however,itssolutionisthemainconstituentofgeneralizedinterpolationalgorithmsthatareusedfortheformalma-nipulationofmulti-variatepolynomials(e.g.forfactorizationandresultantcomputation).Handlingsuchpolynomialsisofextremeimportanceinseveralpracticalapplications,e.g.ingeometricmodelling[7]orinthestabilityanalysisofcontrolsystems[6].Inthiscontext,itisunsafetoapproximatethesolutionsbynumericalmethods[5],sincetheproblemsarehighlynon-linear:Numericalerrors,eveniftheyareinitiallyextremelysmall,growverymuchduringthecomputationandmaye.g.letalltheoriginalrootsofapolynomialdisappear[11].Hence,werequiremethodsforndingtheexactsolutionsoflinearequationsystems.Currently,the(bothasymptoticallyandpractically)mostecientsequentialalgorithmforthisproblemisbasedonamodularmethodandacombinationofCramer’sRulewithGaussianelimination[12].However,thealgorithmisstillverytime-consumingandevenwithfastcomputersonlysmallsystemscanbehandled.Extendingtheapplicationrangeofthemethodisthereforeofextremeimportanceforscienticcomputation.WehaveanalyzedtheproblemandcreatedseveralPaclibversionsofthemodularmethod.Thispaperdescribesourresultsinthefollowingfashion:Afterashortdiscussionofthemodularmethod,theparallelprogrammingmodelofPaclibissketched.Thenwegrad-uallydevelopseveralparallelversionsofthealgorithmandcomparetheresultingPaclibprogramswithrespecttotheirdynamicbehavior.Runtimebenchmarksareperformedonequationsystemswithdierentcharacteristicsandtheachievedresultsarediscussed.2THEMODULARMETHOD22TheModularMethodTheproblemweconsideristhefollowing:LetAbearegularnnmatrixoverZandbavectoroflengthnoverZ.WewanttondthatvectorxoflengthnoverQsuchthatAx=bSuchanxexistsandisuniquesinceweassumethatAisregular.Inotherwords,wewanttosolveasystemofnlinearequationswithnvariableswherethecoecientsoftheequationsaredenotedbyAandtherighthandsidesoftheequationsbyb,respectively.Pleasenotethat1.Aandbcontainarbitraryintegernumberswhosesizesarenotlimitedbythewordlengthofanycomputer.2.Wewanttondaresultvectorxofrationalnumbersthataretheexactsolutionsofthegivenequationsystem.SincetheinputnumbersarearbitraryelementsofZ,theyhavetoberepresentedbysequencesofcomputerwords.Arithmeticoperationscanthereforenotbeperformedinconstanttimebuttheircomplexitydependsonthelengthoftheinvolvedintegers,i.e.thenumberofcomputerwordsrequiredfortheir