Solving linear systems through通过求解性系统

《Solving linear systems through通过求解性系统》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SolvinglinearsystemsthroughnesteddissectionNogaAlonRaphaelYusteryAbstractThegeneralizednesteddissectionmethod,developedbyLipton,Rose,andTarjan,isaseminalmethodforsolvingalinearsystemAx=bwhereAisasymmetricpositivedenitematrix.Themethodrunsextremelyfastwhene

2、verAisawell-separablematrix(suchasmatriceswhoseunderlyingsupportisplanaroravoidsaxedminor).Inthisworkweextendthenesteddissectionmethodtoapplytoanynon-singularwell-separablematrixoveranyeld.Therunningtimesweobtainessentiallymatchthoseofthenesteddissectionme

3、thod.Keywords.Gaussianelimination,linearsystem,nesteddissection.AMSsubjectclassications.68W30,15A15,05C501IntroductionSolvingalinearsystemisthemostbasic,andperhapsthemostimportantproblemincomputationallinearalgebra.Considerableeorthasbeendevotedtoobtaining

4、algorithmsthatsolvealinearsystemfasterthanthenaivecubicimplementationofGaussianelimination.FortherestofthisintroductionweassumethatthesystemisgivenbyAx=b,whereAisanon-singularnnmatrixoveraeld,bisann-vectoroverthateld,andxT=(x1;:::;xn)isthevectorofvariable

5、s.ThefastestgeneralalgorithmforsolvingAx=bwasobtainedbyBunchandHopcroft[2],andbyIbarra,Moran,andHui[10].ThealgebraiccomplexityofbothofthesealgorithmsisO(n!),where!<2:376isthematrixmultiplicationexponent[3].IfAissparseandhasonlymn2non-zeroentries,fasteralgor

6、ithmsexist.AnimportantresultofWiedemann[22]assertsthatifm=O(n)thenasolutionofAx=bcanbecomputedinO~(n2)timeoverniteelds.Wenotethatsolvingsparselinearsystemsoverniteeldshasimportantapplicationsincryptography(see,e.g.,[8]).Eberlyetal.[4]solveAx=bwhereAisany

7、non-singularmatrixwithO(n)nonzeroboundedintegerentriesinbitcomplexityO~(n2:5).SpielmanandTeng[19]obtainedanalmostlineartime1algorithmforapproximatelysolvingsparsesymmetricdiagonally-dominantlinearsystems.DepartmentofMathematics,TelAvivUniversity,TelAviv6997

8、8,Israel.E{mail:nogaa@post.tau.ac.il.ResearchsupportedinpartbyanERCadvancedgrantandbytheHermannMinkowskiMinervaCenterforGeometryatTelAvivUniversity.yDepartmentofMathematics,UniversityofHaifa,Hai