您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 公司方案 > 1 Templates for Linear Algebra Problems
1TemplatesforLinearAlgebraProblemsZhaojunBaiUniversityofKentuckyDavidDayUniversityofKentuckyJamesDemmelUniversityofCalifornia-BerkeleyJackDongarraUniversityofTennesseeandOakRidgeNationalLaboratoryMingGuUniversityofCalifornia-BerkeleyAxelRuheChalmersUniversityofTechnology,G oteborgandHenkvanderVorstUtrechtUniversityAbstract.Theincreasingavailabilityofadvanced-architecturecomputersishavingaverysigni cante ectonallspheresofscienti ccomputation,includingalgorithmresearchandsoftwaredevelopmentinnumericallinearalgebra.Linearalgebra{inparticular,thesolutionoflinearsystemsofequationsandeigenvalueproblems{liesattheheartofmostcalculationsinscienti ccomputing.Thischapterdiscussessomeoftherecentdevelopmentsinlinearalgebradesignedtohelptheuseronadvanced-architecturecomputers.Muchoftheworkindevelopinglinearalgebrasoftwareforadvanced-architecturecomputersismotivatedbytheneedtosolvelargeproblemsonthefastestcomputersavailable.Inthischapter,wefocusonfourbasicissues:(1)themotivationforthework;(2)thedevelopmentofstandardsforuseinlinearalgebraandthebuildingblocksforalibrary;(3)aspectsoftemplatesforthesolutionoflargesparsesystemsoflinearalgorithm;and(4)templatesforthesolutionoflargesparseeigenvalueproblems.Thislastprojectisunderdevelopmentandwewillpaymoreattentiontoitinthischapter.1IntroductionandMotivationLargescaleproblemsofengineeringandscienti ccomputingoftenrequiresolutionsoflinearalgebraproblems,suchassystemsoflinearequations,leastsquaresproblems,oreigenvalueproblems.Thereisavastamountofmaterialavailableonsolvingsuchproblems,inbooks,injournalarticles,andassoftware.Thissoftwareconsistsofwell-maintainedlibrariesavailablecommerciallyorelectronicallyinthepublic-domain,otherlibrariesdistributedwithtextsorotherbooks,individualsubroutinestestedandpublishedbyorganizationsliketheACM,andyetmoresoftwareavailablefromindividualsorelectronicsourceslikeNetlib[21],whichmaybehardto ndorcomewithoutsupport.Soalthoughmanychallengingnumericallinearalgebraproblemsstillawaitsatisfactorysolutions,manyexcellentmethodsexistfromaplethoraofsources.?ThisworkwasmadepossibleinpartbygrantsfromtheDefenseAdvancedResearchProjectsAgencyundercontractDAAL03-91-C-0047administeredbytheArmyResearchO ce,theO ceofScienti cComputingU.S.DepartmentofEnergyunderContractDE-AC05-84OR21400,theNationalScienceFoundationSci-enceandTechnologyCenterCooperativeAgreementNo.CCR-8809615,andNationalScienceFoundationGrantNo.ASC-9005933.Butthesheernumberofalgorithmsandtheirimplementationsmakesithardevenforexperts,letalonegeneralusers,to ndthebestsolutionforagivenproblem.Thishasledtothedevelopmentofvariouson-linesearchfacilitiesfornumericalsoftware.OnehasbeendevelopedbyNIST(NationalInstituteofStandardsandTechnology),andiscalledGAMS(GuidetoAvailableMathematicalSoftware)[7];anotherispartofNetlib[21].Thesefacilitiespermitsearchbasedonlibrarynames,subroutinesnames,keywords,andataxonomyoftopicsinnumericalcomputing.Butforthegeneraluserinsearchofadviceastowhichalgorithmorwhichsubroutinetouseforherparticularproblem,theyo errelativelylittleadvice.Furthermore,manychallengingproblemscannotbesolvedwithexisting\black-boxsoftwarepackagesinareasonabletimeorspace.Thismeansthatmorespecialpurposemethodsmustbeused,andtunedfortheproblemathand.Thistuningisthegreatestchallenge,sincetherearealargenumberoftuningoptionsavailable,andformanyproblemsitisachallengetogetanyacceptableansweratall,orhavecon denceinwhatiscomputed.Theexpertiseregardingwhichoptions,orcombinationsofoptions,islikelytoworkinaspeci capplicationarea,iswidelydistributed.Thus,thereisaneedfortoolstohelpuserspickthebestalgorithmandimplementationfortheirnumericalproblems,aswellasexpertadviceonhowtotunethem.Infact,weseethreepotentialusercommunitiesforsuchtools:{The\HPCC(HighPerformanceComputingandCommunication)communityconsistsofthosescientiststryingtosolvethelargest,hardestapplicationsintheir elds.Theydesirehighspeed,accesstoalgorithmicdetailsforperformancetuning,andreliabilityfortheirproblem.{Engineersandscientistsgenerallydesireeasy-to-use,reliablesoftware,thatisalsoreasonablye cient.{Studentsandteacherswantsimplebutgenerallye ectivealgorithms,whichareeasytoexplainandunderstand.Itmayseemdi culttoaddresstheneedsofsuchdiversecommunitieswithasingledocument.Nevertheless,webelievethisispossibleintheformoftemplates.Atemplateforanalgorithmincludes1.Ahigh-leveldescriptionofthealgorithm.2.Adescriptionofwhenitise ective,includingconditionsontheinput,andestimatesofthetime,spaceorotherresourcesrequired.Iftherearenaturalcompetitors,theywillbereferenced.3.Adescriptionofavailablere nementsanduser-tunableparameters,aswellasadviceonwhentousethem.4.Pointerstocompleteorpartialimplementations,perhapsinseverallanguagesorforseveralarchitectures(eachparallelarchitecture).Theseimplementationexposethosedetailssuitableforuser-tuning,andhidetheothers.5.Numericalexamples,onacommonsetofexamples,illustratingbotheasycasesanddi cultcases.6.Troubleshootingadvice.7.Pointerstotextsorjournalarticlesforfurtherinformation.Inadditiontoindividualtemplates,therewillbeadecisiontreetohe
本文标题:1 Templates for Linear Algebra Problems
链接地址:https://www.777doc.com/doc-3324956 .html