close

Вход

Забыли?

вход по аккаунту

?

Mavriplis D. J. Directional Coarsening and Smoothing for Anisotropic Navier-Stokes Problems 1997

код для вставкиСкачать
Electronic Transactions on Numerical Analysis.
Volume 6, pp. 182-197, Decembber 1997.
Copyright©1997, Kent State University.
ISSN 1068-9613.
ETNA
Kent State University etna@mcs.kent.edu
DIRECTIONALCOARSENINGANDSMOOTHINGFORANISOTROPIC
NAVIER-STOKESPROBLEMS
DIMITRIJ.MAVRIPLIS
y
Abstract.Unstructuredmultigridtechniquesforrelievingthestiffnessassociatedwithhigh-Reynoldsnum-
berviscousflowsimulationsonextremelystretchedgridsareinvestigated.Oneapproachconsistsofemployinga
semi-coarseningordirectional-coarseningtechnique,basedonthedirectionsofstrongcouplingwithinthemesh,in
ordertoconstructmoreoptimalcoarsegridlevels.Analternateapproachisdevelopedwhichemploysdirectional
implicitsmoothingwithregularfullycoarsenedmultigridlevels.Thedirectionalimplicitsmoothingisobtainedby
constructingimplicitlinesintheunstructuredmeshbasedonthedirectionsofstrongcoupling.Bothapproaches
yieldlargeincreasesinconvergenceratesoverthetraditionalexplicitfull-coarseningmultigridalgorithm.However,
maximumbenefitsareachievedbycombiningthetwoapproachesinacoupledmannerintoasinglealgorithm.An
orderofmagnitudeincreaseinconvergencerateoverthetraditionalexplicitfull-coarseningalgorithmisdemon-
strated,andconvergenceratesforhigh-Reynoldsnumberviscousflowswhichareindependentofthegridaspect
ratioareobtained.
Keywords.multigird,anisotropic,Navier-Stokes.
AMSsubjectclassification.65B99.
1.Introduction.Multigridmethodshaveproventobeveryeffectivetechniquesfor
acceleratingconvergencetosteadystateofbothellipticandhyperbolicproblems.Forsim-
pleellipticproblems,suchasaPoissonequation,convergenceratesof0.1areachievable,
meaningthatforeachmultigridcycle,thenumericalerrorcanbereducedbyoneorderof
magnitude.
Forhyperbolicproblems,suchastheEulerequationsincomputationalfluiddynam-
ics,thebestratethattheoreticallycanbeachievedforasecondorderdiscretizationis0.75,
accordingtotheanalysisdiscussedbyMulder[25].Indeed,manystructuredaswellasun-
structuredEulersolversachieveconvergenceratescloseto0.75[2,16,26,27,35].However,
forhigh-Reynoldsnumberviscousflowsolutions,multigridNavier-Stokessolversgenerally
resultinconvergencerateswhichareanorderofmagnitudeormoreslowerthanthoseob-
tainedforinviscidflows.Themainreasonforthisbreakdowninefficiencyofthemultigrid
algorithmistheuseofhighlystretchedanisotropicmesheswhicharerequiredtoefficiently
resolveboundarylayerandwakeregionsinviscousflows.Indeed,thehighertheReynolds
number,themoregridstretchingisrequired,andtheworsetheconvergenceratebecomes.
Theclassicmultigridremedyforthisproblemistoresorttosemi-coarsening,ortoem-
ploysmootherswhichareimplicitinthedirectionnormaltothestretching[4].Theidea
ofsemi-coarseningistocoarsenthemeshonlyinthedirectionnormaltothegridstretch-
ing,ratherthaninallcoordinatedirectionssimultaneously.ThisideawasusedbyMulder
[24,25]toovercomethestiffnessassociatedwiththegridalignmentphenomenonforanup-
windschemeonnon-stretchedstructuredmeshes.Sincedifferentregionsoftheflowfield
maycontainanisotropiesindifferingdirections,acompletesequenceofgrids,eachcoars-
enedinasinglecoordinatedirectionisgenerallyrequired.RadespielandSwanson[28]
employedsemi-coarseningtoalleviatethestiffnessduetostretchedmeshesforviscousflow
calculations.Morerecently,Allmaras[1]hasshownhowtheuseofpreconditionerscoupled
withsemi-coarseningcanhelpalleviategridstretchinginducedstiffness.PierceandGiles
[27]havedemonstratedimprovedconvergenceratesforturbulentNavier-Stokesflowsusing
SubmittedMay16,1997.AcceptedforpublicationAugust16,1997.CommunicatedbyI.Yanveh.
y
InstituteforComputerApplicationsinScienceandEngineering(ICASE),NASALangleyResearchCenter,
Hampton,VA23681
182
ETNA
Kent State University etna@mcs.kent.edu
DimitriJ.Mavriplis
183
diagonalpreconditioningcoupledwithaJ-coarseningtechniqueonstructuredgrids,where
thegridisonlycoarsenedintheJ-coordinatedirection,whichisnormaltotheboundarylayer.
Semi-coarseningtechniquescanbegeneralizedtounstructuredmeshesasdirectional
coarseningmethods.Graphalgorithmscanbeconstructedtoremovemeshverticesbasedon
thelocaldegreeanddirectionofanisotropyineitherthegridorthediscretizedequations.
Thisisachievedbybasingpointremovaldecisionsonthevaluesofthediscretestencilcoeffi-
cients.Thisisthebasisforalgebraicmultigridmethods[33],whichoperateonsparsematri-
cesdirectly,ratherthanongeometricmeshes.Thesetechniquesaremoregeneralthanthose
availableforstructuredmeshes,sincetheycandealwithmultipleregionsofanisotropiesin
conflictingdirections.Theyofferthepossibilityofconstructingalgorithmswhichattemptto
generatethe“optimal”coarsegridfortheproblemathand.Moranoetal.[23]havedemon-
stratedhowsuchtechniquescanproducealmostidenticalconvergenceratesforaPoisson
equationonanisotropiccartesianmesh,andahighlystretchedunstructuredmesh.Morere-
cently,Francescatto[7]hasdemonstratedconvergenceimprovementsfortheNavier-Stokes
equationsusingdirectionalcoarseningmultigrid.
Oneofthedrawbacksofsemi-ordirectional-coarseningtechniquesisthattheyresultin
coarsegridsofhighercomplexity.Whileafull-coarseningapproachreducesgridcomplexity
betweensuccessivelycoarserlevelsbyafactorof4in2D,and8in3D,semi-coarsening
techniquesonlyachieveagridcomplexityreductionof2,inboth2Dand3D.Thisincreases
thecostofamultigridV-cycle,andmakestheuseofW-cyclesimpractical.Perhapsmore
importantlyforunstructuredmeshcalculations,theamountofmemoryrequiredtostorethe
coarselevelsisdramaticallyincreased,particularlyin3D.Raw[30]advocatestheuseof
directionalcoarsening,butatafixedcoarseningrateof10to1,inordertoreduceoverheads.
Thisgenerallyresultsintheremovalofmultipleneighboringpointsinthecoarseningprocess,
andthusrequiresastrongersmootherthanasimpleexplicitscheme.Analternativetosemi-
coarseningistousealinesolverinthedirectionnormaltothegridstretchingcoupledwitha
regularfullcoarseningmultigridalgorithm,atleastforstructuredgridproblems[4].
Inthefollowingsections,weexaminethebenefitsobtainedthroughtheuseofdirectional
coarseningandimplicitlinesolvers,andcombinethetwoapproachestoconstructanefficient
ReynoldsaveragedNavier-Stokessolverforveryhighlystretchedmeshes.
2.BaseSolver.TheReynoldsaveragedNavier-Stokesequationsarediscretizedby
afinite-volumetechniqueonmeshesofmixedtriangularandquadrilateralelements.The
governingequationsaregiveninintegralformas:
@
@t
(uV ) +
Z
@Ω
(f:n) dS =
Z
@Ω
(g:n) dS:(2.1)
Thesolutionu isgivenby
u =
0
@
u
j
E
1
A
;(2.2)
andtheithcomponentsoftheconvectiveandviscousfluxvectorsare,respectively:
f
i
=
0
@
u
i
u
i
u
j
+
ij
p
u
i
(E +p)
1
A
g
i
=
0
@
0
ij
u
k
ik
−q
i
1
A
;(2.3)
where isthedensity,u
j
;j = 1;2 representsthexandyvelocitycomponents,E isthetotal
energy,andp isthepressure,whichisrelatedtotheothervariablesbytheperfectgaslaw:
p = (γ −1) (E −
1
2
(u
2
+v
2
));(2.4)
ETNA
Kent State University etna@mcs.kent.edu
184
Directionalcoarseningandsmoothing
whereγ isaconstant.
ij
andq
i
representthestresstensorandtheheatfluxvector.Inthe
thinlayerapproximationtotheNavier-Stokesequations,thesetermscanbetakenas:
ij
= @u
i
@x
j
;q
i
= −
@
p
@x
i
;(2.5)
where and denotethefluidviscosityandthermalconductivity,respectively.Thesevalues
aredeterminedasthesumofthecorrespondingfluidproperties,whicharegiven,andthe
turbulencequantities,whichareobtainedthroughthesolutionofanadditionalturbulence
modelingequation[37].Inthefinitevolumemethod,thevariablesu arestoredatthevertices
ofthemesh,Vrepresentsthevolumeofthecontrolvolumeassociatedwitheachvertex,as
depictedinFigure1,andthefluxintegralsaretakenovertheboundaryofthecontrolvolume,
denotedas@Ω,withn beingthenormalvectoratthecontrolvolumeboundary.
Thesimplestwaytocomputethesefluxintegralsistoprecomputethefluxesatallver-
ticesgiventheu values,andthenintegrateanaverageofthetwofluxesoneithersideofa
control-volumefacewiththefacenormalvector.Thisleadstoacentraldifferencescheme
whichisunstableunlessadditionalartificialdissipationisemployed.Analternativestrategy
istouseanupwindscheme.Theupwindedfluxescanbeconstructedatacontrol-volume
interfaceusinganapproximateRiemannsolver[32]whichcomputesanupwindedconvec-
tivefluxvector,givensolutionvaluesu
left
andu
right
oneithersideofthecontrol-volume
boundary.Ifthesesolutionvaluesatthecontrol-volumeinterfacesaretakenasthevaluesat
thecontrol-volumecenters,afirstorderaccurateschemeisobtained.Toensuresecondorder
accuracy,theinterfacevaluesareextrapolatedfromthecorrespondingvertexvaluesaccord-
ingtoaTayorexpansion,usingacontrol-volumegradientofu computedthroughaGreen-
Gausscontourintegralaboutthecontrolvolumes.Formultigridcalculations,asecond-order
discretizationisemployedfortheconvectivetermsonthefinegrid,whileafirst-orderdis-
cretizationisusedonthecoarsegridlevels.
Inthesimplifiedthin-layerformgivenabove,theviscousfluxesareanalogoustothe
termsofasimplediffusionequation,andarediscretizedbyafinitedifferencescheme.
AsamplemeshisdepictedinFigure2.Isotropictriangularelementsareemployedin
regionsofinviscidflow,andstretchedquadrilateralelementsareusedintheboundarylayer
andwakeregions.Allelementsofthegridarehandledbyasingleunifyingedge-based
data-structureintheflowsolver[19].Triangularelementscouldeasilybeemployedinthe
boundarylayerregionssimplybysplittingeachquadrilateralelementintotwotriangular
elements.
AsshowninFigure1,theresultingcontrol-volumesforquadrilateralelementsproduce
stencilswithstrongcouplinginthedirectionnormaltothegridstretchingandweakcoupling
inthedirectionofstretching.Whentriangularelementsareemployedinregionsofhigh
meshstretching,thestencilsarecomplicatedbythepresenceofdiagonalconnections,anddo
notdecoupleassimplyinthenormalandstretchingdirectionsasforquadrilateralelements.
Therefore,theuseofquadrilateralelementsinregionsofhighmeshstretchingiscentralto
thesolutionalgorithmsdescribedinthispaper.
Thebasictime-steppingschemeisathree-stageexplicitmultistage(Runge-Kutta)scheme
withstagecoefficientsoptimizedforhighfrequencydampingproperties[43],andaCFL
numberof1.8.ConvergenceisacceleratedbyalocalblockJacobipreconditioner,whichin-
volvesinvertinga44 matrixforeachvertexateachstage[22,26,27,31].Inthisapproach,
thetimestept
i
intheoriginalmulti-stagescheme:
u
(k)
i
= u
(0)
i
+ CFL
k
t
i
R
i
(u
(k−1)
)(2.6)
ETNA
Kent State University etna@mcs.kent.edu
DimitriJ.Mavriplis
185
isreplacedbytheinverseofthepoint-wiseJacobian[D]
i
:
u
(k)
i
= u
(0)
i
+ CFL
k
[D]
i
−1
R
i
(u
(k−1)
)(2.7)
whereCFL istheCourant −Friedrichs −Lewy number,
k
isthecoefficientofthek
th
Runge-Kuttastage,andR
i
representsthediscreteresidualatvertexi.Thisapproach,which
caneitherbeinterpretedasapre-conditioner,orasalocalmatrixtime-step[41],hasbeen
showntoproducesuperiorconvergenceratesforupwindschemes.Noothertechniquessuch
asenthalpydampingorresidualsmoothingareemployed[9].
ThesingleequationturbulencemodelofSpalartandAllmaras[37]isutilizedtoaccount
forturbulenceeffects.Thisequationisdiscretizedandsolvedinamannercompletelyanalo-
goustotheflowequations,withtheexceptionthattheconvectivetermsareonlydiscretized
tofirst-orderaccuracy.
3.Directional-Coarsening.Inthecontextofunstructuredmeshes,thereexistsvarious
strategiesforimplementingmultigridtechniques.Twoapproachesthathavebeenexplored
extensivelybytheauthorarethemethodofoversetmeshes,andthemethodofcontrol-volume
agglomeration[12,16,20,36].Intheoverset-meshapproach,asequenceoffineandcoarse
unstructuredmeshesisconstructedeitherbyhand,orinsomeautomatedfashion.These
meshesarethenemployedinthemultigridalgorithm,andvariablesaretransferredbetween
thevariousmeshesofthesequenceusinglinearinterpolation.Intheagglomerationapproach,
coarselevelsareconstructedbyfusingtogetherneighboringfinegridcontrolvolumestoform
asmallernumberoflargerandmorecomplexcontrolvolumesonthecoarsegrid.
Whiledirectionalcoarseningstrategiescanbeemployedinbothmultigridapproaches,
forpracticalreasonswehavechosentoutilizeonlytheoverset-meshmultigridapproachfor
thesepreliminaryinvestigations.Infact,thesamecoarseningalgorithmmaybeusedforboth
approaches.Intheoverset-meshapproach,thegraphcoarseningalgorithmisemployedto
selectasubsetofpointsfromthefinegridfromwhichthecoarsegridwillbeformed.Once
thecoarsegridpointshavebeendetermined,theymustbetriangulatedinordertoforma
consistentcoarsegrid.
Thecoarseningalgorithmisbasedonaweightedgraph.Eachedgeofthemeshisas-
signedaweightwhichrepresentsthedegreeofcouplinginthediscretization.Inthetrue
algebraicmultigridsense,theseweightsshouldbeformedfromthestencilcoefficients.How-
ever,sincetheNavier-Stokesequationsrepresentasystemofequations,multiplecoefficients
existforeachedge.Forsimplicity,theedgeweightsaretakenastheinverseoftheedge
length.Foreachfinegridvertex,theaverageandthemaximumweightofallincidentedges
areprecomputedandstored.Thisratioofmaximumtoaverageweightisanindicationofthe
localanisotropyinthemeshateachvertex.Thecoarseningalgorithmbeginsbychoosingan
initialvertexasacoarsegridpointorseedpoint,andattemptstoremoveneighboringpoints
byexaminingthecorrespondingedgeweights.Iftheratioofmaximumtoaverageweights
attheseedpointisgreaterthan,(usuallytakenas = 4),thenonlytheneighboringvertex
alongtheedgeofmaximumweightisremoved.Otherwise,(i.e.inisotropicregions)all
neighboringedgesareremoved.Thenextseedpointisthentakenfromaprioritylistwhich
containspointswhichareadjacenttopointswhichhavepreviouslybeendeleted.
Inthepresentimplementation,thegraph-basedcoarseningalgorithmisonlyemployedin
theboundary-layerandwakeregions.Oncetheseregionshavebeencoarsened,theremaining
regionsofthedomainareregriddedusingaDelaunayadvancing-fronttechniquewithuser
specifiedresolution.Thisapproachispurelyforconvenience,sincetheoriginalmeshisgen-
eratedbyatwo-stepprocedure,whichemploysanadvancing-layerstechniqueintheregions
ofviscousflow,andanadvancing-frontDelaunaytriangulationinregionsofinviscidflow
ETNA
Kent State University etna@mcs.kent.edu
186
Directionalcoarseningandsmoothing
[17,18].Thefullweighted-graphcoarseningalgorithmwillbeimplementedinthecontextof
agglomerationmultigridinfuturework.
Thefirsttestcaseillustratestheconvergenceratesachievableforisotropicproblemswith
thepresentalgorithm.TheinviscidtransonicflowoveraNACA0012airfoiliscomputedat
aMachnumberof0.73andincidenceof2.31degrees.Themeshcontains5849verticesand
consistsuniquelyofisotropictriangularelements.Theconvergencehistoryisdocumentedin
Figure3.Atotalof5multigridlevelswereemployed,andaresidualreductionof11orders
ofmagnitudeover100multigridW-cycleswasobtained.Theoverallconvergenceratefor
thiscaseis0.77,whichisveryclosetothetheoreticallimitof0.75.
Thesecondtestcaseillustratesthestiffnessinducedbyanisotropy.Theviscousturbulent
flowoverthesamegeometryatthesameconditionswithaReynoldsnumberof5millionis
computedonthemeshdepictedinFigure1.Thismeshcontainsatotalof4880points.The
cellsontheairfoilsurfacehaveaheightof2.e-06chords,andthemaximumcellaspectratio
inthemeshis20,000.Thistypeofmeshisrequiredinordertocapturetheboundarylayer
gradients.ThecomputedMachcontoursattheseconditionsaredisplayedinFigure4.The
convergencerateisdepictedinFigure5,using5multigridlevelswhichwereconstructed
usingtheunweightedorfull-coarseningversionofthecoarseningalgorithm,asdescribed
in[20].Theslowdowninconvergenceovertheinviscidtestcaseisdramatic.Afteran
initialphaseofrapidconvergence,theresidualreductionrateslowsdowntolessthan0.99
permultigridW-cycle.Figure5alsodepictstheconvergencerateofthesamealgorithm
whenasequenceofdirectionallycoarsenedgridsisemployedinthemultigridalgorithm.
Theimprovementissubstantial,yieldingaresidualreductionof0.91permultigridV-cycle.
4.DirectionalImplicitSmoothers.Althoughdirectionalcoarseningstrategiesformulti-
gridcanachievelargeincreasesinconvergencespeed,asdemonstratedinthepreviouscase,
thecoarsegridsaremorecomplexthanthoseobtainedinthefullcoarseningstrategy.Note
forexampleinthepreviouscasethataV-cyclewasrequired,sincetheW-cycleisimpractical
inthiscase.Asmentionedpreviously,theoverheadrequiredtostorethecoarselevelsisalso
greatlyincreasedinsuchcases.
Analternativeapproachistouseadirectionallyimplicitsmootherinconjunctionwith
fullcoarseningmultigrid.Forstructuredgrids,anexampleofadirectionallyimplicitsmoother
isalinesolver.Linesolversareattractivebecausetheyresultinblock-tridiagonalmatrices
whichcanbesolvedveryefficiently.Forunstructuredgrids,predeterminedgridlinesdonot
exist.However,linesolverscanstillbeemployed,providedlinesareartificiallyconstructed
intheunstructuredgrid.Techniquesforconstructinglinesinanunstructuredgridhavepre-
viouslybeendescribedintheliterature[8,14].Inthoseefforts,lineswhichspantheentire
gridwereconstructedusingunweightedgraphtechniques.Inthepresentcontext,therole
ofthelinesolveristorelievethestiffnessinducedbygridanisotropy.Therefore,linesare
desirableonlyinregionsofstronganisotropy,andintheseregionstheymustpropagatealong
thedirectionofstrongcoupling.
Giventheserequirements,analgorithmtobuildlinesinananisotropicmeshcanbe
constructedusingaweightedgraphtechnique,inamanneranalogoustothealgorithmfor
directionalcoarseningdescribedpreviously.Theedgeweightsaredefinedaspreviously,
andtheratioofmaximumtoaverageadjacentedgeweightispre-computedforeverymesh
vertex.Theverticesarethensortedaccordingtothisratio.Thefirstvertexinthisorderedlist
isthenpickedasthestartingpointforaline.Thelineisbuiltbyaddingtotheoriginalvertex
theneighboringvertexwhichismoststronglyconnectedtothecurrentvertex,providedthis
vertexdoesnotalreadybelongtoaline,andprovidedtheratioofmaximumtominimum
ETNA
Kent State University etna@mcs.kent.edu
DimitriJ.Mavriplis
187
edgeweightsforthecurrentvertexisgreaterthan,(using = 4 inallcases).Theline
terminateswhennoadditionalvertexcanbefound.Iftheoriginatingvertexisnotaboundary
pointthentheproceduremustberepeatedbeginningattheoriginalvertex,andproceeding
withthesecondstrongestconnectiontothispoint.Whentheentirelineiscompleted,a
newlineisinitiatedbyproceedingtothenextavailablevertexintheorderedlist.Ordering
oftheinitialvertexlistinthismannerensuresthatlinesoriginateinregionsofmaximum
anisotropy,andterminateinisotropicregionsofthemesh.Thealgorithmresultsinasetof
linesofvariablelength.Inisotropicregions,linescontainingonlyonepointareobtained,
andthepointexplicitschemeisrecovered.
Onvectormachines,theblock-tridiagonallinesolvesmustbevectorizedacrossthelines.
Becausethelineshavevaryinglengths,alllinesmustbemadeofsimilarlengthbypadding
thematricesoftheshorterlineswithzerosontheoff-diagonalsandonesonthediagonal
entries,insuchawaythatzeroadditionalcorrectionsaregeneratedattheselocationsby
theimplicitsolver.Tominimizetheamountofpaddingrequired,thelinesaresortedinto
groups,suchthatwithineachgroup,alllinesarecloseinsizetooneanother.Vectorization
thentakesplaceoverthelineswithineachgroup.Usinggroupsofsize100,theadditional
overheadduetopaddingisoftheorderof10%.Analternativeapproachwouldbetoreplace
thetridiagonalinversionroutinewithacyclicreductionalgorithmwhichcanbevectorized
directly.Thismayhoweverresultinsubstantiallyshortervectorlengths.
Inthecurrentapproach,thesizeofthevectorgroupsalsodeterminestheamountofmem-
oryrequiredforthelinesolves,sincethetridiagonalmatricesareconstructedjustpriorto,
anddiscardedjustafterthelinesaresolved,andalllinesareuncoupled.Forscalarmachines,
linesmaybeprocessedindividually,andthememoryrequirements(i.e.additionalworking
memoryrequiredbytheimplicitsolver)aredeterminedbythelengthofthelongestlinein
thegrid.
Theimplicitsystemgeneratedbythesetoflinescanbeviewedasasimplificationof
thegeneralJacobianobtainedfromalinearizationofabackwardsEulertimediscretization,
wheretheJacobianisthatobtainedfromafirst-orderdiscretization.Forblock-diagonalpre-
conditioning,alloff-diagonalblockentriesaredeleted,whileintheline-implicitmethod,the
blockentriescorrespondingtotheedgeswhichconstitutethelinesarepreserved.Theim-
plicitlinesolverisappliedasapreconditionertothethree-stageexplicitschemedescribed
previously.Ateachstageinthemulti-stagescheme,thecorrectionspreviouslyobtainedby
multiplyingtheresidualvectorbytheinvertedblock-diagonalmatrixarereplacedbycorrec-
tionsobtainedbysolvingtheimplicitsystemofblock-tridiagonalmatricesgeneratedfrom
thesetoflines.Thisimplementationhasthedesirablefeaturethatitreducesexactlytothe
block-diagonalpreconditionedmulti-stageschemewhenthelinelengthbecomesone(i.e.1
vertexandzeroedges),asisthecaseinisotropicregionsofthemesh.
Asanexample,theviscousflowcaseoftheprevioussectionhasbeenrecomputedusing
theline-implicitsolverwithfull-coarseningmultigrid.Thesetoflinesgeneratedinthemesh
ofFigure1aredepictedinFigure6.Thelinesextendthroughtheboundarylayerandwake
regions,andhavemostlyalengthof1(i.e.1vertexandzeroedges)intheregionsofinviscid
flowwherethemeshisisotropic.Atotalof5mesheswasemployedinthemultigridsequence.
TheconvergencerateforthisalgorithmisdepictedinFigure7.Theresidualsarereducedby
over4ordersofmagnitudein100cycles,whichcorrespondstoaresidualreductionrateof
0.92permultigridW-cycle.Thisrateisclosetothatobtainedbythepoint-wiseschemeusing
directionalcoarsening.However,thecoarsegridsareoflowercomplexityinthiscaseanda
W-cyclehasbeenused.
ETNA
Kent State University etna@mcs.kent.edu
188
Directionalcoarseningandsmoothing
5.CombiningDirectionalCoarseningandSmoothing.Thereareobvioussimilari-
tiesbetweenthedirectionalcoarseningalgorithmandthetechniqueusedtoconstructlinesfor
thedirectionalimplicitmethod.Thesetwotechniquescanbecombined,inacoupledmanner,
toproduceamorerobustandefficientoverallalgorithm.Thesimplestwaytocombinethese
techniquesistousethepre-conditionedline-implicitsmootherwithasequenceofdirection-
allycoarsenedcoarsemultigridlevels.Inordertomorecloselycouplethesetwotechniques,
weuseexactlythesamecriteriaforcoarseningandforlineconstruction.Thisensuresthat
coarseningwillproceedinthesamedirectionandalongthelinesdeterminedfortheimplicit
solver.
AnexampleofthiscombinedalgorithmisdepictedbytheconvergenceplotinFigure8.
Inthiscase,thecombineddirectional-implicit-coarseningalgorithmhasbeenusedtosolve
thesameviscousturbulentflowasdescribedintheprevioussections.Thefinemeshforthis
caseissimilartotheonedisplayedinFigure1,butcontains5828points,andthemeshcells
neartheairfoilboundaryhaveaheightof2.e-07chordlengths,andthemaximumaspect-ratio
cellinthemeshis200,000.Thisrepresentsanorderofmagnitudemoreanisotropythanthe
previousmesh.Evenonthisextremelystretchedgrid,theresidualsarereducedbyover4
ordersofmagnitudeover100cycles,whichresultsinaaverageconvergencerateof0.92per
multigridV-cycle.Thisrateiscomparabletothatachievedbyeitheralgorithmseparatelyon
thepreviouscase.However,onthismorehighlystretchedgrid,neitheralgorithmalonecould
deliverthistypeofperformance.
Ontheotherhand,thiscaseisstillplaguedbythehighcoarsegridcomplexitiesofthe
semi-coarseningapproach.However,thesetwotechniques,directionalcoarseninganddirec-
tionalimplicitsmoothing,aretwostrategiesfortreatingthesameproblem.Inthisrespect
theyaremoreoverlappinginnaturethancomplementary,andoneofthesetechniquesmay
berelaxedsomewhat.Wethereforeproposetoperformdirectional-coarseningasdescribed
previously,alongthedirectionoftheimplicitlines,butatafastercoarseningrateof4:1.
Therefore,ratherthanremoveeverysecondpointalongtheimplicitlines,weremovethree
pointsforeverypreservedcoarsegridpointalongtheimplicitlines.Inisotropicregions,the
coarseningalgorithmremainsunchanged.Thishastheeffectofgeneratingasequenceof
coarsegridswhichhasroughlythesamecomplexityasthatobtainedbythefull-coarsening
technique.Toillustratethisapproach,thesamecasehasbeenrecomputedusingtheline-
implicitsmootheranddirectionalcoarseningata4:1rate.Theconvergencerateiscompared
withthatobtainedpreviouslyinFigure8.Theaverageresidualreductionrateforthiscase
is0.88.Thefactthatthisrateisevenfasterthanthatachievedinthepreviousexampleis
attributedtotheuseofW-cyclesinthecurrentcalculation,whichismadepossibleduetothe
lowcomplexityofthecoarsegrids.
Thecombineddirectionalimplicit-coarseningmultigridalgorithmproducesconvergence
rateswhichareinsensitivetothedegreeofgridstretching.Thisisillustratedbycomputing
theflowoveranRAE2822airfoilonthreedifferentgridsofthesamestreamwiseresolution
butwithvaryingnormalwallandwakeresolution.Thefirstgridcontainsanormalwall
spacingof10
−5
chords,andatotalof12,568points,whilethesecondgridcontainsanormal
wallspacingof10
−6
chords,and16,167points,andthethirdgridanormalwallspacing
of10
−7
chords,and19,784points.Thesecondgridcontainswhatisgenerallyregardedas
suitablenormalandstreamwiseresolutionforaccuratecomputationofthistypeofproblem,
whilethefirstandthirdgridsaremostlikelyunder-resolvedandover-resolvedinthedirection
normaltotheboundarylayer,respectively.ThesecondgridisdisplayedinFigure9,while
theMachcontoursofthesolutioncomputedonthisgridaredisplayedinFigure10.Amatrix-
basedartificialdissipationdiscretization[38]isemployedforthesecalculationsratherthan
theupwindschemedescribedpreviously.Thisdiscretizationdeliverssimilaraccuracyasthe
ETNA
Kent State University etna@mcs.kent.edu
DimitriJ.Mavriplis
189
RoeRiemann-solverbasedupwindscheme,butdoesnotrequiretheuseofalimiter,which
mayadverselyaffectconvergencefortransonicflowcases.
TheconvergenceratesobtainedonthesethreegridsaredisplayedinFigure11,using
theoriginalexplicitfull-coarseningmultigridalgorithm,andthenewdirectional-implicit-
coarseningmultigridalgorithm.Theconvergenceoftheoriginalalgorithmdegradesasthe
meshstretchingincreases,whereastheconvergenceofthenewalgorithmisessentiallycon-
stantforallthreemeshes.Consideringthatthesethreemeshesrepresentatwoorderof
magnitudevariationintheamountofmeshstretching,theperformanceofthedirectional-
implicit-coarseningmultigridalgorithmcanbequalifiedasmeshaspect-ratioindependent.
6.ConclusionsandFurtherWork.Intheabovediscussion,thecostofthegraph
algorithmsusedtoconstructthelinesandthecoarsegridlevelsisnotconsidered.Inallcases,
thecostofthispre-processingisnegligiblecomparedtothecostofthemultigridsolution
process.ThepreprocessingrequiresnomorethanseveralsecondsofCPUtime,whilethe
multigridsolutionrequiresoftheorderofoneormorehoursfortheexamplesdescribed
inthispaper.Thisisdespitethefactthattheworstcasecomplexityofthepre-processing
graphalgorithmsisO(NlogN) whichishigherthantheoptimalcomplexityofO(N) forthe
multigridalgorithm.
Thecomparisonsbetweenvariousschemeshaveallbeenmadeonapercyclebasis.
Whilethisisusefulfordeterminingtherelativeeffectivenessofeachtechniqueasamultigrid
smoother,andthedegreetowhichtheoverallalgorithmapproachesthehypothetical“opti-
mal”algorithm,itdoesnotconveytherelativecostsofthesevariousschemes.Oneofthe
reasonsdirectcpucomparisonshavenotbeenmadeisthatthecurrentcodeisnotsufficiently
optimizedtoprovideafaircomparisonwiththebaselinealgorithm.Anotherreason,isthat
thetechniqueusedforcoarsegridconstructionresultsinlessthanoptimalcoarsegridcom-
plexitysincetheinviscidregionsoftheflowareactuallyregridded,ratherthancoarsenedby
pointremoval.(However,theboundarylayerandwakeregionsexhibitoptimalcoarsening).
Theultimategoalofthisworkistoincorporatethesetechniquesintothemorepractical
agglomerationoralgebraicmultigridmethoddescribedin[20,21].Thedevelopmentofan
optimalgridcoarseningschemeforagglomerationmultigridiscurrentlyunderdevelopment.
Figure12illustratesthefirstagglomeratedlevelofastretchedunstructuredgrid,wherethe
agglomerationhasbeenconstrainedtoproceedalongtheimplicit-linesintheboundarylayer
regions,atarateof4:1.Intheisotropicregionsofthemesh,thisalgorithmrevertstothat
developedin[20,21].
Preliminaryresultsusingtheagglomerationmultigridstrategyprovideacomparisonof
theoriginalisotropicexplicitmultigridschemewiththedirectionalimplicitmultigridscheme
basedoncputime,asshowninFigure13.Theexplicitmultigridschemeemploysafivestage
Runge-Kuttasmoother,andaresidualsmoothingtechniqueforconvergenceacceleration[9],
whilethedirectionalimplicitmultigridschemeemploysathree-stageRunge-Kuttasmoother
withlinepreconditioning.Thisrepresentstheempiricallyattainedoptimalstrategiesforboth
typesofmultigridalgorithms.Furtherefficienciesareobtainedinthelattercasebyinverting
thelineJacobiansatthefirststageoftheRunge-Kuttasmoother,andfreezingtheseinverted
Jacobiansfortheremainingstages.Thisresultsinthecostofadirectionalimplicitmultigrid
cyclebeingalmostidenticaltothatachievedbytheexplicitmultigridscheme.Thecom-
parisonbasedonCPUtimeinFigure13isthereforeverysimilartothecomparisonsinthe
previoussectionbasedonmultigridcycles.
ETNA
Kent State University etna@mcs.kent.edu
190
Directionalcoarseningandsmoothing
Althoughtheproposedalgorithmsinthisworkhavedemonstratedconvergenceratesin-
dependentofthedegreeofgridstretching,theconvergenceratesobtainedforviscousflows
arestillsomewhatslowerthanwhatmaybeachievedforsimpleinviscidflowproblems.Ad-
ditionalresearchisrequiredtofurtherreducetheseratesconsistentlyforalltypesofviscous
flowproblems.Perhapsthemostpromisingavenueofresearchistodevelopmoresophis-
ticatedpreconditionersinanefforttoprovideabettermultigridsmootheratlowadditional
cost[13,40].
REFERENCES
[1]S.R.A
LLMARAS
,Analysisofsemi-implicitpreconditionersformultigridsolutionofthe2dcompressible
navier-stokesequations,InProceedingsofthe12thAIAACFDConference,SanDiegoCA,June1995,
AIAAPaper95-1651-CP.
[2]W.K.A
NDERSON
R.R
AUSCHAND
D.B
ONHAUS
,Implicitmultigridalgorithmsforincompressibletur-
bulentflowsonunstructuredgrids,InProceedingsofthe12thAIAACFDConference,SanDiegoCA,
June1995,AIAAPaper95-1740-CP.
[3]T.J.B
ARTHAND
S.W.L
INTON
,Anunstructuredmeshnewtonsolverforcompressiblefluidflowandits
parallelimplementation,AIAApaper95-0221,January1995.
[4]A.B
RANDT
,Multigridtechniqueswithapplicationstofluiddynamics:1984guide,InVKILectureSeries,
pages1–176,March1984.
[5]Y.C
HOIAND
C.M
ERKLE
,Theapplicationofpreconditioningtoviscousflows,J.Comp.Phys.,105(1993),
pp.207-223.
[6]D.L.D
ARMOFALAND
P.J.S
CHMID
,Theimportanceofeigenvectorsforlocalpreconditionersoftheeuler
equations,InProceedingsofthe12thAIAACFDConference,SanDiego,CA,pages102–117,June
1995.AIAAPaper95-1655-CP.
[7]J.F
RANCESCATTO
,R´esolutiondel’´equationdePoissonsurdesmaillages´etir´esparunemethodemultigrille,
INRIAReportNo.2712,November1995.
[8]O.H
ASSAN
,K.M
ORGAN
,
AND
J.P
ERAIRE
,Anadaptiveimplicit/explicitfiniteelementschemeforcom-
pressiblehighspeedflows,AIAAPaper89-0363,January1989.
[9]A.J
AMESON
,W.S
CHMIDT
,
AND
E.T
URKEL
,NumericalsolutionoftheEulerequationsbyfinitevolume
methodsusingRunge-Kuttatimesteppingschemes,AIAAPaper81-1259,1981.
[10]D.J
ESPERSEN
T.P
ULLIAMAND
P.B
UNING
,RecentenhancementstoOVERFLOW,AIAAPaper97-0644,
January1997.
[11]G.K
ARYPISAND
V.K
UMAR
,Afastandhighqualitymultilevelschemeforpartitioningirregulargraphs,
TechnicalReportTechnicalReport95-035,UniversityofMinnesota,1995.Ashortversionappearsin
Intl.Conf.onParallelProcessing1995.
[12]M.L
ALLEMAND
,H.S
TEVE
,
AND
A.D
ERVIEUX
,Unstructuredmultigriddingbyvolumeagglomeration:
Currentstatus,Comput.&Fluids,21(1992),pp.397–433.
[13]J.F.L
YNNAND
B.
VAN
L
EER
,Asemi-coarsenedmultigridsolverfortheeulerandnavier-stokesequations
withlocalpreconditioning,InProceedingsofthe12thAIAACFDConference,SanDiego,CA,pages
242–252,June1995.AIAAPaper95-1667-CP.
[14]D.M
ARTINAND
L
¨
OHNER
,Animplicitlinelet-basedsolverforincompressibleflows,AIAAPaper92-0668,
January1992.
[15]L.M
ARTINELLIAND
A.J
AMESON
,ValidationofamultigridmethodfortheReynolds-averagedNavier-
StokesEquations,AIAAPaper88-0414,January1988.
[16]D.J.M
AVRIPLIS
,Three-dimensionalmultigridfortheEulerequations,AIAAJournal,30(7):1753–1761,
July1992.
[17]
,Anadvancing-frontDelaunaytriangulationalgorithmdesignedforrobustness,AIAApaper93-0671,
January1993.
[18]
,Unstructuredmeshgenerationandadaptivity,In26thVKILectureSeriesonComputationalFluid
Dynamics,LectureSeries1995-02,VonKarmanInstituteforFluidDynamics,RhodeSaintGenese,
Belgium,arch1995.
[19]D.J.M
AVRIPLISAND
V.V
ENKATAKRISHNAN
,AunifiedmultigridsolverfortheNavier-Stokesequations
onmixedelementmeshes,AIAAPaper95-1666,June1995.
[20]
,Agglomerationmultigridfortwodimensionalviscousflows,Comput.&Fluids,24(1995),pp.
553–570.
[21]
,A3DagglomerationmultigridsolverfortheReynolds-averagedNavier-Stokesequationsonunstruc-
turedmeshes,Internat.J.Numer.MethodsFluids,23(1996),pp.527–544.
[22]E.M
ORANOAND
A.D
ERVIEUX
,LookingforO(N)Navier-Stokessolutionsonnon-structuredmeshes,
In6thCopperMountainConf.onMultigridMethods,NASAConferencePublication3224,1993,pp.
ETNA
Kent State University etna@mcs.kent.edu
DimitriJ.Mavriplis
191
449–464.
[23]E.M
ORANO
D.J.M
AVRIPLISAND
V.V
ENKATAKRISHNAN
,Coarseningstrategiesforunstructuredmulti-
gridtechniqueswithapplicationtoanisotropicproblems,In7thCopperMountainConf.onMultigrid
Methods,NASAConferencePublication3339,April1995,pp.591–606.
[24]W.A.M
ULDER
,Anewmultigridapproachtoconvectionproblems,J.Comp.Phys.,83(1989),pp.303–323.
[25]
,AhighresolutionEulersolverbasedonmultigridsemi-coarseninganddefectcorrection,J.Comput.
Phys.,100(1992),pp.91–104.
[26]C.O
LLIVIER
-G
OOCH
,Towardsproblem-independentmultigridcnvergenceratesforunstructuredmesh
methodsi:Inviscidandlaminarflows,InProceedingsofthe6thInternationalSymposiumonCFD,
LakeTahoe,NV,September1995.
[27]N.P
IERCEAND
M.G
ILES
,Preconditioningonstretchedmeshes,AIAApaper96-0889,January1996.
[28]R.R
ADESPIELAND
R.C.S
WANSON
,Progresswithmultigridschemesforhypersonicflowproblems,J.of
Comput.Phys.,116(1995),pp.103–122.
[29]
,Aninvestigationofcell-centeredandcell-vertexmultigridschemesfortheNavier-Stokesequations,
AIAApaper89-053,January1989.
[30]M.R
AW
,RobustnessofcoupledalgebraicmultigridfortheNavier-Stokesequations,AIAApaper96-0297,
January1996.
[31]K.R
IEMSLAGHAND
E.D
ICK
,AmultigridmethodforsteadyEulerequationsonunstructuredadaptive
grids,In6thCopperMountainConf.onMultigridMethods,NASAconferencepublication3224,1993,
pp.527–542.
[32]P.L.R
OE
,ApproximateRiemannsolvers,parametervectorsanddifferenceschemes,J.Comp.Phys.,
43(1981),pp.357–372.
[33]J.W.R
UGEAND
K.S
T
¨
UBEN
,Algebraicmultigrid,InMultigridMethods,S.F.McCormick,ed.,SIAM
FrontiersinAppliedMathematics,Philadelphia,1987,pp.73–131.
[34]Y.S
AADAND
M.H.S
CHULTZ
,GMRES:Ageneralizedminimalresidualalgorithmforsolvingnonsymmetric
linearsystems,SIAMJ.Sci.Stat.Comput.,7(1986),pp.856–869.
[35]D.S
IDILKOVER
,Agenuinelymultidimensionalupwindschemeandefficientmultigridsolverforthecom-
pressibleEulerequations,ICASEReport94-84,October1994.
[36]W.A.S
MITH
,Multigridsolutionoftransonicflowonunstructuredgrids,InRecentAdvancesandAp-
plicationsinComputationalFluidDynamics,ed.,O.Baysal,ProceedingsoftheASMEWinterAnnual
Meeting,November1990.
[37]P.R.S
PALARTAND
S.R.A
LLMARAS
,Aone-equationturbulencemodelforaerodynamicflows,La
RechercheA´erospatiale,1(1994),pp.5–21.
[38]R.C.S
WANSONAND
E.T
URKEL
,Oncentraldifferenceandupwindschemes,J.Comput.Phys.,101(1992),
pp.292–306.
[39]E.T
URKEL
,Preconditioningmethodsforsolvingtheincompressibleandlowspeedcompressibleequations,
J.Comp.Phys.,72(1987),pp.277–298.
[40]E.T
URKEL
V.N.V
ATSAAND
R.R
ADESPIEL
,Preconditioningmethodsforlowspeedflow,AIAAPaper
96-2460,1996.
[41]B.
VAN
L
EER
W.T.L
EEAND
P.R
OE
,Characteristictime-steppingorlocalpreconditioningoftheEuler
equations,InProceedingsofthe10thAIAACFDConference,Honolulu,Hawaii,pages260–282,June
1991.AIAAPaper91-1552-CP.
[42]B.
VAN
L
EER
E.T
URKEL
C.H.T
AIAND
L.M
ESAROS
,Localpreconditioninginastagnationpoint,In
Proceedingsofthe12thAIAACFDConference,SanDiego,CA,pages88–101,June1995.AIAAPaper
95-1654-CP.
[43]B.
VAN
L
EER
,C.H.T
AI
,
AND
K.G.P
OWELL
,Designofoptimally-smoothingmulti-stageschemesforthe
Eulerequations,AIAAPaper89-1933,June1989.
[44]V.V
ENKATAKRISHNAN
,Ontheaccuracyoflimitersandconvergencetosteadystatesolutions,J.Comp.
Phys.,118(1995),pp.120–130.
[45]J.M.W
EISSAND
W.AS
MITH
,Preconditioningappliedtovariableandconstantdensitytime-accurate
flowsonunstructuredmeshes,AIAAPaper94-2209,June1994.
[46]L.B.W
IGTON
N.J.Y
UAND
D.P.Y
OUNG
,GMRESaccelerationofcomputationalfluiddynamiccodes,
InProceedingsofthe7thAIAACFDConference,pages67–74,July1985.AIAAPaper85-1494-CP.
ETNA
Kent State University etna@mcs.kent.edu
192
Directionalcoarseningandsmoothing
F
IG
.2.1.Mediancontrol-volumesforstretchedquadrilateralandtriangularelements
F
IG
.2.2.MixedelementgridusedforviscousflowcalculationsaboutNACA0012airfoil;Numberofvertices
=4880
0
100
200
300
400
500
600
Number of MG Cycles
-12.00
-10.00
-8.00
-6.00
-4.00
-2.00
0.00
2.00
Log (Error)
F
IG
.3.1.MultigridConvergenceRateusingExplicitSmoothingandFull-Coarseningforinviscidflowover
NACA0012airfoil
ETNA
Kent State University etna@mcs.kent.edu
DimitriJ.Mavriplis
193
F
IG
.3.2.ComputedMachcontoursforviscousflowoverNACA0012airfoil
0
100
200
300
400
500
600
Number of MG Cycles
-12.00
-10.00
-8.00
-6.00
-4.00
-2.00
0.00
2.00
Log (Error)
EXPLICIT FULL-COARSENING
EXPLICIT SEMI-COARSENING
F
IG
.3.3.ComparisonofMultigridConvergenceRateusingExplicitSmoothingandFull-Coarseningversus
ExplicitSmoothingandSemi-CoarseningforviscousflowoverNACA0012airfoil
ETNA
Kent State University etna@mcs.kent.edu
194
Directionalcoarseningandsmoothing
F
IG
.4.1.ImplicitlinesproducedbythecurrentalgorithmonthegridofFigure1
0
100
200
300
400
500
600
Number of MG Cycles
-12.00
-10.00
-8.00
-6.00
-4.00
-2.00
0.00
2.00
Log (Error)
EXPLICIT FULL-COARSENING
IMPLICIT FULL-COARSENING
F
IG
.4.2.ComparisonofMultigridConvergenceRateusingExplicitSmoothingandFullCoarseningversus
ImplicitLineSolverandFull-CoarseningforviscousflowoverNACA0012airfoil
ETNA
Kent State University etna@mcs.kent.edu
DimitriJ.Mavriplis
195
0
100
200
300
400
500
600
Number of MG Cycles
-12.00
-10.00
-8.00
-6.00
-4.00
-2.00
0.00
2.00
Log (Error)
2:1 COARSENING, V-CYCLE
4:1 COARSENING, W-CYCLE
F
IG
.5.1.MultigridConvergenceRateusingImplicitLine-SolverandSemi-Coarseningforviscousflowover
NACA0012airfoil
F
IG
.5.2.UnstructuredGridUsedforComputationofTransonicFlowOverRAE2822Airfoil.Numberof
Points=16167,WallResolution=10
−6
chords
ETNA
Kent State University etna@mcs.kent.edu
196
Directionalcoarseningandsmoothing
F
IG
.5.3.ComputedMachContoursonaboveGrid.Mach=0.73,Incidence=2.31degrees,Re=6.5million
0
100
200
300
400
500
600
Number of MG Cycles
-14.00
-12.00
-10.00
-8.00
-6.00
-4.00
-2.00
0.00
Log (Error)
1.e-05 NORMAL SPACING
1.e-06 NORMAL SPACING
1.e-07 NORMAL SPACING
EXPLICIT FULL COARSENING MG
DIRECTIONAL IMPLICIT MG
F
IG
.5.4.Comparisonoforiginalexplicitfullcoarseningmultigridalgorithmandnewdirectional-implicit-
coarseningmultigridalgorithmonmeshesofvaryingdegreesofanisotropy
ETNA
Kent State University etna@mcs.kent.edu
DimitriJ.Mavriplis
197
F
IG
.6.1.ExampleofAgglomeratedGridUsing4:1CoarseningalongLinesinBoundary-LayerRegion
0
1000
2000
3000
4000
CPU SECONDS (SUN ULTRA 170 Mhz)
-14.00
-12.00
-10.00
-8.00
-6.00
-4.00
-2.00
0.00
LOG (Error)
REGULAR EXPLICIT MULTIGRID
DIRECTIONAL IMPLICIT MG
F
IG
.6.2.ComparisonofExplicitIsotropicAgglomerationMultigridwithDirectionalImplicitMultigridfor
ComputationofTransonicFlowonGridofFigure9intermsofCPUTime.
Автор
Redmegaman
Документ
Категория
Другое
Просмотров
41
Размер файла
193 Кб
Теги
Газовая динамика, математические методы, for, гидродинамика, problems, navier, and, stokes, 1997, directional, mavriplis, smoothing, coarsening, anisotropic
1/--страниц
Пожаловаться на содержимое документа