1 Templates for Linear Algebra Problems

1TemplatesforLinearAlgebraProblemsZhaojunBaiUniversityofKentuckyDavidDayUniversityofKentuckyJamesDemmelUniversityofCalifornia-BerkeleyJackDongarraUniversityofTennesseeandOakRidgeNationalLaboratoryMingGuUniversityofCalifornia-BerkeleyAxelRuheChalmersUniversityofTechnology,GoteborgandHenkvanderVorstUtrechtUniversityAbstract.Theincreasingavailabilityofadvanced-architecturecomputersishavingaverysignicanteectonallspheresofscienticcomputation,includingalgorithmresearchandsoftwaredevelopmentinnumericallinearalgebra.Linearalgebra{inparticular,thesolutionoflinearsystemsofequationsandeigenvalueproblems{liesattheheartofmostcalculationsinscienticcomputing.Thischapterdiscussessomeoftherecentdevelopmentsinlinearalgebradesignedtohelptheuseronadvanced-architecturecomputers.Muchoftheworkindevelopinglinearalgebrasoftwareforadvanced-architecturecomputersismotivatedbytheneedtosolvelargeproblemsonthefastestcomputersavailable.Inthischapter,wefocusonfourbasicissues:(1)themotivationforthework;(2)thedevelopmentofstandardsforuseinlinearalgebraandthebuildingblocksforalibrary;(3)aspectsoftemplatesforthesolutionoflargesparsesystemsoflinearalgorithm;and(4)templatesforthesolutionoflargesparseeigenvalueproblems.Thislastprojectisunderdevelopmentandwewillpaymoreattentiontoitinthischapter.1IntroductionandMotivationLargescaleproblemsofengineeringandscienticcomputingoftenrequiresolutionsoflinearalgebraproblems,suchassystemsoflinearequations,leastsquaresproblems,oreigenvalueproblems.Thereisavastamountofmaterialavailableonsolvingsuchproblems,inbooks,injournalarticles,andassoftware.Thissoftwareconsistsofwell-maintainedlibrariesavailablecommerciallyorelectronicallyinthepublic-domain,otherlibrariesdistributedwithtextsorotherbooks,individualsubroutinestestedandpublishedbyorganizationsliketheACM,andyetmoresoftwareavailablefromindividualsorelectronicsourceslikeNetlib[21],whichmaybehardtondorcomewithoutsupport.Soalthoughmanychallengingnumericallinearalgebraproblemsstillawaitsatisfactorysolutions,manyexcellentmethodsexistfromaplethoraofsources.?ThisworkwasmadepossibleinpartbygrantsfromtheDefenseAdvancedResearchProjectsAgencyundercontractDAAL03-91-C-0047administeredbytheArmyResearchOce,theOceofScienticComputingU.S.DepartmentofEnergyunderContractDE-AC05-84OR21400,theNationalScienceFoundationSci-enceandTechnologyCenterCooperativeAgreementNo.CCR-8809615,andNationalScienceFoundationGrantNo.ASC-9005933.Butthesheernumberofalgorithmsandtheirimplementationsmakesithardevenforexperts,letalonegeneralusers,tondthebestsolutionforagivenproblem.Thishasledtothedevelopmentofvariouson-linesearchfacilitiesfornumericalsoftware.OnehasbeendevelopedbyNIST(NationalInstituteofStandardsandTechnology),andiscalledGAMS(GuidetoAvailableMathematicalSoftware)[7];anotherispartofNetlib[21].Thesefacilitiespermitsearchbasedonlibrarynames,subroutinesnames,keywords,andataxonomyoftopicsinnumericalcomputing.Butforthegeneraluserinsearchofadviceastowhichalgorithmorwhichsubroutinetouseforherparticularproblem,theyoerrelativelylittleadvice.Furthermore,manychallengingproblemscannotbesolvedwithexisting\black-boxsoftwarepackagesinareasonabletimeorspace.Thismeansthatmorespecialpurposemethodsmustbeused,andtunedfortheproblemathand.Thistuningisthegreatestchallenge,sincetherearealargenumberoftuningoptionsavailable,andformanyproblemsitisachallengetogetanyacceptableansweratall,orhavecondenceinwhatiscomputed.Theexpertiseregardingwhichoptions,orcombinationsofoptions,islikelytoworkinaspecicapplicationarea,iswidelydistributed.Thus,thereisaneedfortoolstohelpuserspickthebestalgorithmandimplementationfortheirnumericalproblems,aswellasexpertadviceonhowtotunethem.Infact,weseethreepotentialusercommunitiesforsuchtools:{The\HPCC(HighPerformanceComputingandCommunication)communityconsistsofthosescientiststryingtosolvethelargest,hardestapplicationsintheirelds.Theydesirehighspeed,accesstoalgorithmicdetailsforperformancetuning,andreliabilityfortheirproblem.{Engineersandscientistsgenerallydesireeasy-to-use,reliablesoftware,thatisalsoreasonablyecient.{Studentsandteacherswantsimplebutgenerallyeectivealgorithms,whichareeasytoexplainandunderstand.Itmayseemdiculttoaddresstheneedsofsuchdiversecommunitieswithasingledocument.Nevertheless,webelievethisispossibleintheformoftemplates.Atemplateforanalgorithmincludes1.Ahigh-leveldescriptionofthealgorithm.2.Adescriptionofwhenitiseective,includingconditionsontheinput,andestimatesofthetime,spaceorotherresourcesrequired.Iftherearenaturalcompetitors,theywillbereferenced.3.Adescriptionofavailablerenementsanduser-tunableparameters,aswellasadviceonwhentousethem.4.Pointerstocompleteorpartialimplementations,perhapsinseverallanguagesorforseveralarchitectures(eachparallelarchitecture).Theseimplementationexposethosedetailssuitableforuser-tuning,andhidetheothers.5.Numericalexamples,onacommonsetofexamples,illustratingbotheasycasesanddicultcases.6.Troubleshootingadvice.7.Pointerstotextsorjournalarticlesforfurtherinformation.Inadditiontoindividualtemplates,therewillbeadecisiontreetohe