A frequency-domain method for finite element solut

AFREQUENCY{DOMAINMETHODFORFINITEELEMENTSOLUTIONSOFPARABOLICPROBLEMSCHANG-OCKLEE,JONGWOOLEE,ANDDONGWOOSHEENAbstract.Weintroduceandanalyzeafrequency-domainmethodforpar-abolicpartialdierentialequations.Themethodisnaturallyparallelizable.AftertakingtheFouriertransformationofgivensourcesinthespace-timedo-mainintothespace-frequencydomain,weproposetosolveanindenite,com-plexellipticproblemforeachfrequency.Fourierinversionwillthenrecoverthesolutioninthespace-timedomain.Existenceanduniquenessaswellaserrorestimatesaregiven.Fourierinvertibilityisalsoexamined.Numericalexperimentsarepresented.1.IntroductionLetbeanopenboundedLipschitzdomaininRN,N=2;3,J=[0;1),and=@.Weareinterestedinanumericalmethodforthefollowingparabolicproblem:1utr(ru)=f;J;(1.1a)u=0;J;(1.1b)u(x;0)=0;x2;(1.1c)where2L2()and2H1()arepositivefunctionsofxdenedon,whichsatisfy,,jrj,where;;;arepositiveconstants.Inthispaper,insteadofsolvingProblem(1.1)inthespace-timedomain,weanalyzetheFourier-transformedproblemsofProblem(1.1),andproposeanat-urallyparallelizablealgorithmbysolvingtheFourier-transformedproblems.RecallrstthattheFouriertransformbv(;!)ofafunctionv(;t)intimeisdenedbybv(;!)=Z11v(;t)ei!tdtDate:September1,1997.1991MathematicsSubjectClassication.Primary65N30;Secondary35K20.Keywordsandphrases.parabolicproblems,niteelementmethods,parallelalgorithm,Four-iertransform.TheresearchwassupportedinpartbyKOSEF961-0106-039-2,GARCandBSRI-MOE-97.12CHANG-OCKLEE,JONGWOOLEE,ANDDONGWOOSHEENandtheFourierinversionformulaisgivenbyv(;t)=12Z11bv(;!)ei!td!:Weextendfandubyzerotot0andtransformthespace-timeformulationoftheequations(1.1)toaspace-frequencyformulationbytakingtheFouriertransformof(1.1)intime.Wethenobtainasetofthefollowingellipticproblemsdependingon!:i!1bur(rbu)=bf;x2;(1.2a)bu=0;x2:(1.2b)Notethatifv(x;t)isarealfunction,itsFouriertransformsatisestheconjugaterelation:bv(x;!)=bv(x;!);!2R:Then,theFourierinversionformulatakestheformv(x;t)=1ReZ10bv(x;!)ei!td!:(1.3)Here,weexplainbrieythereasonwhyweconsiderProblem(1.2)insteadofProblem(1.1).Ourprimaryinterestliesinproposingandanalyzinganatur-allyparallelizablealgorithmwithwhichonemayuseparallelmachinestosolveProblem(1.1)asecientlyaspossible.Themostpopularstrategytogetnumericalsolutionsof(1.1)istosolvetheprobleminthespace-timedomainbyusingamarchingalgorithmsuchasbackward-EulerorCrank-Nicolsonmethods.Suchmethodshaveproventosolveeectivelymanypracticalproblems.Inordertoadvancetonexttimestepswhenoneusesamarchingalgorithm,oneneedstosolveellipticproblemsusinginformationsonspacegridsatthecurrentand/orprevioustimesteps.Therecouldbetwoapproachestoparallelizationinsolvingparabolicproblemsinawidesense.Onedirectionmaybetousetheideaofdomaindecomposi-tionmethodstodecomposethespacedomainintosubdomainsinsolvingeachellipticproblemcorrespondingtoeachxedtimestep.Forsuchadirection,werefer[4,5,14,15,18,19,25]andrecentpublicationsinmajornumericalana-lysisjournals.However,thesemethodsrequireheavycommunicationcostamongprocessorsinordertopassinformationsbetweenneighboringsubdomains.Theotherdirectionmaybeattemptstodeviseandimplementparallelalgorithmsinthemarchingaxes,thatis,thetimeaxis.However,thenatureofevolutionmakesitdiculttondanaturallyparallelizablealgorithmwhichdoesnotspendtoomuchcommunicationtimeamongprocessors.Inthissense,bothapproachesfor-mulatedinthespace-timedomainarenotnaturallyparallelizable.Inthispaper,weproposeanalternativemethodbytakingtheFouriertrans-formationofProblem(1.1)toobtainasetofellipticproblems(1.2)fordiscreteFREQUENCY{DOMAINMETHODFORPARABOLICPROBLEMS3numberoffrequency!’sofinterest.Thisformulationisbasedontheobservationthatthesetofellipticproblems(1.2)dependingontheparameter!iscompletelyindependent.Wearethusabletosolvethesetofellipticproblems(1.2),byassigningeachsuchproblemtoeachprocessor.Independenceofeachproblemguaranteesnocommunicationcostamongprocessors.Thenournumericalsolu-tionsineachtimeisrecoveredbyadiscreteinverseFouriertransform.Theaboveprocedurehasbeenproventobeveryecientforsolvingwavepropagationswithabsorbingboundaryconditionsinaparallelmachine[9,10].WaveequationsbecomesHelmholtz-typeequationsinthespace-frequencydo-main,whichhaveeigensolutionswithDirichletorNeumannboundaryconditions.Thisisnotthecasewithabsorbingboundaryconditions;withabsorbingboundaryconditionstheHelmholtz-typeequationsareuniquelysolvable,andthusanaturalparallelizationispossiblebysimultaneouslysolvingFourier-transformedproblemswithdierent!’sindierentprocessors;fordetails,see[9,10,12,20].Indeed,itturnsoutthatsolvingwavepropagationismoresubtlethansolvingparabolicproblems.ButitisworthytostressthatparabolicproblemswithDirichletandNeumannboundaryconditionscanbesolvedinanaturalparallelizableway.Seealso[21]forananalysisofalinearizedNavier-Stokesequations,whereasimilartreatmentfortheDirichletboundaryconditionhasbeendoneto(1.1)or(1.2).Thispaperisorganizedasfollows.Inx2,weshowthattheequation(1.2)hastheuniquesolutionbu(;!)for!0,andregularityandstabilityresultsareprovedforsuchsolutions.I