INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENG

INTERNATIONALJOURNALFORNUMERICALMETHODSINENGINEERINGInt.J.Numer.Meth.Engng2002;00:1{27Preparedusingnmeauth.cls[Version:2000/01/19v2.0]Iterativesolutionoflargelinearsystemswithnon{smoothsubmatricesusingpartialwavelettransformsandsplit{matrixmatrix{vectormultiplicationPatriciaGonzalezy,JoseC.CabaleiroandTomasF.PenaDept.ElectronicsandComputerScience.Univ.SantiagodeCompostela.15782SantiagodeCompostela,Spain,fcaba,[e-mail]~na.15071ACoru~na,Spain,[e-mail]utionoflargelinearsystemswithhighlyirregularmatricescannotbeacceleratedbywavelettransformationandsubsequentsparsicationifthetransformedmatrixisstillhighlyirregular.Inthispaperweshowthatiftheirregularityoftheoriginalmatrixislimitedtoarelativelysmallknownsetofrowsorcolumns(asisthecaseinsignicantapplications),thenaccelerationcanbeachievedbyamixedapproachinwhichonlythe\smoothsubmatrixistransformedanditerativesolutionisimplementedusinganovel\split{matrixformofmatrix-vectormultiplication.Copyrightc2002JohnWiley&Sons,Ltd.Correspondenceto:TomasF.Pena,Dept.ElectronicaeComputacion,Univ.SantiagodeCompostela,15782SantiagodeCompostela,Spain,[e-mail]/grantsponsor:MinisteriodeCienciayTecnologa;contract/grantnumber:TIC2001-3694-C02-01Copyrightc2002JohnWiley&Sons,Ltd.2P.GONZALEZ,J.C.CABALEIROANDT.F.PENAkeywords:denselinearsystems,boundaryelementmethod,wavelettransforms,liftingscheme,iterativesolvers,GMRES.1.INTRODUCTIONAsiswellknown,ageneralsystemAx=b(1)ofnlinearequationsinnunknownscanbesolvedinO(n3)operationsbydirectmethodsbasedonLUfactorization.Thisissatisfactoryenoughifnissmall,especiallyif,inthecontextofabroaderproblem,assemblyofthesystemtobesolvedtakessignicantlylongerthansolutionofthesystem,butiterativemethodsemployingO(n2)operationsperiterationbecomemoreecientasproblemsizeincreases;currently,forexample,itiscommontoemployaKrylovsubspacemethod.TheconvergenceofsuchprocessescanoftenbeenhancedbysubjectingthematrixAtoappropriatepreconditioning.Amoreradicalapproachtosolutionaccelerationistore{expresstheproblemofequation(1)relativetoabasissuchthatthetransformedmatrixWA=WAW1,whereWisthetransformationmatrix,hasrelativelyfewelementsthatdiersignicantlyfromzero.Inthissituation,settingthenear{zeroelementsofWAtozero(\thresholding)oftenallowsasolutionoftheproblemtobeobtained,withoutsignicantlossofaccuracy,byapplyingfastsparse{systemtechniquestotheresultingsystem~AWx=Wb(2)where~AistheresultofsparsifyingWAbythresholding,Wx=WxandWb=Wb.ThespeedupCopyrightc2002JohnWiley&Sons,Ltd.Int.J.Numer.Meth.Engng2002;00:1{27Preparedusingnmeauth.clsIT.SOL.OFLARGELINEARSYSTEMSWITHNON{SMOOTHSUBMATRICESUSING...3achievedbybeingabletousesparse{systemtechniques,whichtypicallyinvolveO(nlogn)operationsperiteration,canfaroutweighthecostofthetransformationA!WA,whichlikethecostperiterationwithouttransformationandthresholdingisO(n2)[2,3].Quantitaveanalysisin[11,8,26,10]showthatwithappropiatewavelets,adensesystemofequationscanbecompressedtoasparseone,whoseresolutionsavesoperationswhereastheorderoftheconvergenceismaintained.Onekindoftasktowhichtheabove\transformationplusthresholdingapproachhasbeensuccessfullyappliedisthesolutionoflinearsystemsarisingfromapplicationoftheboundaryelementmethod(BEM)toboundaryvalueproblems[4,9,18].Recently,in[6]anewapproachtoapplyingwaveletsforthesolutionofsystemsofequationsgeneratedbyBEMproblemswasrecentlyproposed.SincethematrixAinBEMproblemsismadeupfromtermsforseparateintegralsHandG,applyingthewavelettransformtotheHandGmatricesbeforeassemblyintoAgivesbetterperformance.Inthispaperwefocusonageneralapproachappliedtoanymatrix{vectormultiplicationinvolvingadensematrixA,butthisapproachcanbealsoappliedtopreviousmatricesHandGonthoseproblems.Goodresultshavebeenachievedbytransformingtowaveletbases[7],whichallowextremelyecientencodingofmanypatternsofvariationbecausetheirbasisvectorsarerelativelylocalizedinboththespaceandfrequencydomains.However,whentheproblemstackledinvolveveryirregularboundariesand/ormixedboundaryconditions,thecorrespondingirregularityofthematricesAwhichencodethemmaypersistinthetransformedmatrixWA,makingthresholdingimpossible.Forexample,Figure1illustratestheuntransformedmatrixarisingfromapplicationofthedualBEMtoahollowcylinderwithacrackatitsinsidesurface[17];thesubarraycorrespondingtothecrackisclearlydistinguishedbyitsmanylargeelementsCopyrightc2002JohnWiley&Sons,Ltd.Int.J.Numer.Meth.Engng2002;00:1{27Preparedusingnmeauth.cls4P.GONZALEZ,J.C.CABALEIROANDT.F.PENA020406080100050100−1−0.500.511.5x104(a)01020300102030−0.2−0.100.10.20.3(b)Figure1.a)MatrixarisingfromapplicationofthedualBEMtoahollowcylinderwithacrackatitsinsidesurface.b)Magniedviewofpartofthesmoothregion.andgreatirregularity(Figure1(a)).Thresholdingcanachieveonlylimitedsparsicationofthecorrespondingtransformedmatrixwithouttotallyannullingthesubarraycorrespondingtotheregularboundaryofthephysicalsystem(Figure1(b)showsadetailofthisareaoftheoriginalmatrix;notethechangeinverticalscale);andtheeliminationofinformationcaused