A multiscale finite element method for elliptic pro

JOURNALOFCOMPUTATIONALPHYSICS

ARTICLENO

.CP975682

134,169–189(1997)

AMultiscaleFiniteElementMethodforEllipticProblemsin

CompositeMaterialsandPorousMedia

ThomasY.HouandXiao-HuiWu

AppliedMathematics,Caltech,Pasadena,California91125

ReceivedAugust5,1996

Inthispaper,westudyamultiscalefiniteelementmethodfor

solvingaclassofellipticproblemsarisingfromcompositematerials

andflowsinporousmedia,whichcontainmanyspatialscales.The

methodisdesignedtoefficientlycapturethelargescalebehavior

ofthesolutionwithoutresolvingallthesmallscalefeatures.This

isaccomplishedbyconstructingthemultiscalefiniteelementba

functionsthatareadaptivetothelocalpropertyofthedifferential

operator.Ourmethodisapplicabletogeneralmultiple-scaleprob-

lemswithoutrestrictiveassumptions.Theconstructionoftheba

functionsisfullydecoupledfromelementtoelement;thus,the

methodisperfectlyparallelandisnaturallyadaptedtomassively

parallelcomputers.Forthesamereason,themethodhastheability

tohandleextremelylargedegreesoffreedomduetohighlyhetero-

geneousmedia,whichareintractablebyconventionalfiniteelement

(difference)methods.Incontrasttosomeempiricalnumerical

upscalingmethods,themultiscalemethodissystematicandlf-

consistent,whichmakesiteasiertoanalyze.Wegiveabriefanalysis

ofthemethod,withemphasisonthe‘‘resonantsampling’’effect.

Then,wepropoanoversamplingtechniquetoremovethereso-

nanceeffect.Wedemonstratetheaccuracyandefficiencyofour

methodthroughextensivenumericalexperiments,whichinclude

problemswithrandomcoefficientsandproblemswithcontinuous

scales.Parallelimplementationandperformanceofthemethodare

alsoaddresd.

ᮊ1997AcademicPress

1.INTRODUCTION

Manyproblemsoffundamentalandpracticalimpor-

tancehavemultiple-scalesolutions.Compositematerials,

porousmedia,andturbulenttransportinhighReynolds

numberflowsareexamplesofthistype.Acompleteanaly-

sisoftheproblemsisextremelydifficult.Forexample,

thedifficultyinanalyzinggroundwatertransportismainly

caudbytheheterogeneityofsubsurfaceformationsspan-

ningovermanyscales[7].Theheterogeneityisoftenrepre-

ntedbythemultiscalefluctuationsinthepermeability

ofthemedia.Forcompositematerials,thedisperdphas

(particlesorfibers),whichmayberandomlydistributed

inthematrix,giveritofluctuationsinthethermalor

electricalconductivity;moreover,theconductivityisusu-

allydiscontinuousacrossthephaboundaries.Inturbu-

lenttransportproblems,theconvectivevelocityfieldfluc-

tuatesrandomlyandcontainsmanyscalesdependingon

theReynoldsnumberoftheflow.areadaptedtothelocalpropertiesofthedifferentialopera-

169

Adirectnumericalsolutionofthemultiplescaleprob-

lemsisdifficultevenwithmodernsupercomputers.The

majordifficultyofdirectsolutionsisthescaleofcomputa-

tion.Forgroundwatersimulations,itiscommontohave

millionsofgridblocksinvolved,witheachblockhavinga

dimensionoftensofmeters,whereasthepermeability

measuredfromcoresisatascaleofveralcentimeters

[23].Thisgivesmorethan10degreesoffreedomper

5

spatialdimensioninthecomputation.Therefore,atremen-

dousamountofcomputermemoryandCPUtimearere-

quired,andtheycaneasilyexceedthelimitoftoday’s

computingresources.Thesituationcanberelievedtosome

degreebyparallelcomputing;however,thesizeofdiscrete

problemisnotreduced.Theloadismerelysharedbymore

processorswithmorememory.Somerecentdirectsolu-

tionsofflowandtransportinporousmediaarereported

in[1,25,9,22].Wheneveronecanaffordtoresolveallthe

smallscalefeaturesofaphysicalproblem,directsolutions

providequantitativeinformationofthephysicalprocess

atallscales.Ontheotherhand,fromanengineeringper-

spective,itisoftensufficienttopredictthemacroscopic

propertiesofthemultiple-scalesystems,suchastheeffec-

tiveconductivity,elasticmoduli,permeability,andeddy

diffusivity.Therefore,itisdesirabletodevelopamethod

thatcapturesthesmallscaleeffectonthelargescales,but

whichdoesnotrequireresolvingallthesmallscalefea-

tures.

Here,westudyamultiscalefiniteelementmethod

(MFEM)forsolvingpartialdifferentialequationswith

multiscalesolutions.Thecentralgoalofthisapproachis

toobtainthelargescalesolutionsaccuratelyandefficiently

withoutresolvingthesmallscaledetails.Themainideais

toconstructfiniteelementbafunctionswhichcapture

thesmallscaleinformationwithineachelement.Thesmall

scaleinformationisthenbroughttothelargescales

throughthecouplingoftheglobalstiffnessmatrix.Thus,

theeffectofsmallscalesonthelargescalesiscorrectly

captured.Inourmethod,thebafunctionsarecon-

structedfromtheleadingorderhomogeneousellipticequa-

tionineachelement.Asaconquence,thebafunctions

0021-9991/97$25.00

Copyright©1997byAcademicPress

Allrightsofreproductioninanyformrerved.

170

HOUANDWU

tor.Inthecaoftwo-scaleperiodicstructures,Hou,Wu,althoughthehomogenizationtheoryhelpsrevealthecau

andCaihaveprovedthatthemultiscalemethodindeedoftheproblem.Thismakesitpossibletogeneralizeour

convergestothecorrectsolutionindependentofthesmallmethodtoproblemswithcontinuousscales.Wewilldem-

scaleinthehomogenizationlimit[21].onstratethroughextensivenumericalexperimentsthatthis

Inthispaper,wecontinuethestudyofthemultiscalesimpletechniqueisveryeffectiveforawiderangeofappli-

method,withemphasisonproblemswithcontinuousscalescations,includingproblemswithrandomcoefficientsand

fromcompositematerialsandflowsinporousmedia.Ex-problemswithcontinuousscales.

tensivenumericaltestsareperformedontheproblems.Inpracticalcomputations,alargeamountofoverhead

Theerroranalysisofthemethodisreviewedbrieflytimecomesfromconstructingthebafunctions.The

forproblemswithscaleparation.Theaccuracyofourmultiscalebafunctionsareconstructednumerically,

methodforproblemswithcontinuousscalesisthenstudiedexceptforcertainspecialcas.Sincethebafunctions

numerically.Moreover,wecompareourmethodwithtra-areindependentofeachother,theycanbeconstructed

ditionalfiniteelement(difference)methodsaswellasex-independentlyandthiscanbedoneperfectlyinparallel.

istingnumericalupscalingmethodsintermsofoperationThisgreatlyreducestheoverheadtimeinconstructing

countsandmemoryrequirement.Wegivetwosimplepar-thebas.Onaquentialmachine,theoperationcount

allelimplementationsofourmethodandstudytheirparal-ofourmethodisabouttwicethatofaconventionalfinite

lelefficiencycomputationally.elementmethod(FEM)fora2Dproblem.Thedifference

Acommondifficultyinnumericalupscalingmethodsisisreducedsignificantlyforamassivelyparallelcomputer.

thatlargeerrorsresultfromthe‘‘resonance’’betweentheForexample,runningon256processors,ourmethodonly

gridscaleandthescalesofthecontinuousproblem.Thisspends9%moreCPUtimethanaFEMusing1024ϫ1024

isrevealedbyourearlieranalysis[21].Forthetwo-scalelinearelements(eSection4.6).

problem,theerrorduetotheresonancemanifestsasaAnotheradvantageofourmethodisitsabilitytoreduce

ratiobetweenthewavelengthofthesmallscaleoscillationthesizeofalargescalecomputation.Thisoffersabig

andthegridsize;theerrorbecomeslargewhenthetwosavingincomputermemory.Forexample,letNbethe

scalesareclo.Adeeperanalysisshowsthattheboundarynumberofelementsineachspatialdirection,andletM

layerinthefirst-ordercorrectoremstobethemainbethenumberofsubcellelementsineachdirectionfor

sourceoftheresonanceeffect.Byajudiciouschoiceofsolvingthebafunctions.Thentherearetotal(MN)

boundaryconditionsforthebafunction,wecanelimi-(nisthedimension)elementsatthefinegridlevel.Fora

natetheboundarylayerinthefirst-ordercorrector.ThistraditionalFEM,thecomputermemoryneededforsolving

wouldgiveaniceconrvativedifferencestructureinthetheproblemonthefinegridisO(MN).Incontrast,

discretization,whichinturnleadstocancellationofreso-MFEMrequiresonlyO(M)amountofmemory.

nanceerrorsandgivesanimprovedrateofconvergenceIfMϭ32ina2Dproblem,thentraditionalFEMneeds

independentofthesmallscalesinthesolution.about1000timesmorememorythanMFEM.

Motivatedbyourearlieranalysis[21]mentionedabove,Sinceweneedtouanadditionalgridtocomputethe

herewepropoanover-samplingmethodtoovercomebafunctionnumerically,itmakesntocompareour

thedifficultyduetoscaleresonance.TheideaisquitemultiscaleFEMwithatraditionalFEMatthesubcellgrid,

simpleandeasytoimplement.Sincetheboundarylayerh

inthefirst-ordercorrectoristhin,O(␧),wecansampleinsolutionatthecoargridh,whileatraditionalFEMtries

adomainwithasizelargerthanhϩ␧anduonlythetoresolvethesolutionatthefinegridh

interiorsampledinformationtoconstructthebas(eextensivenumericalexperimentsdemonstratethattheac-

Section3.3).Here,histhemeshsizeand␧isthesmallcuracyofourmultiscaleFEMonthecoargridhiscom-

scaleinthesolution.Bydoingthis,theboundarylayerinparabletothatofFEMonthefinegrid.Insomecas,

thelargerdomainhasnoinfluenceonthebafunctions.MFEMisevenmoreaccuratethanFEM(eSections4.3

Nowthecorrespondingfirst-ordercorrectorsarefreeofand4.4).

boundarylayers.Asaresult,weobtainanimprovedrateAtthispoint,wewouldliketoemphasizethatthepur-

ofconvergencewhichisindependentofthesmallscale.poofourmethodistosolvepracticalproblemswhichare

Frompracticalconsiderations,thisimprovementiscru-toolargetohandlebydirectmethodsongivencomputing

cial.Forproblemswithmanyscalesorcontinuousscales,resources.Ourmethodgivesasystematicandlf-consis-

itisinevitabletohavethemeshsizehcoincidewithoneoftentapproachtocapturethelargescalesolutioncorrectly

thephysicalscales.Withoutthisimprovement,wecannotwithoutresolvingthesmallscaledetailsandwithout

guaranteethatourmethodconvergescompletelyindepen-resortingtoclosurearguments.Weshowthatatareason-

dentofthesmallscalefeaturesinthesolution.Itisalsoablecost,themultiscaleFEMhastheabilitytosolvevery

importantthatouroversamplingtechniquedoesnotrelylargescalepracticalproblemswithaccuracycomparable

onthehomogenizationtheory(likesolvingacellproblem),tothecorrespondingdirectsimulationsatthefinegrid.

n

nn

nn

ϩN

s

ϭh/M.NotethatthemultiscaleFEMonlycapturesthe

s

ϭh/M.Our

MULTISCALEFINITEELEMENTMETHOD

171

Thisgiveshopetosolvingsomelargescalecomputationalscaleandthephysicalscaleneveroccurinthecorrespond-

problemsthatareotherwiintractableusingdirect

methods.

Itshouldbementionedthatmanynumericalmethods

havebeendevelopedwithgoalssimilartoours.The

includemethodsbadonthehomogenizationtheory

(cf.[14,10]),andsomeupscalingmethodsbadonsimple

physicaland/ormathematicalmotivations(cf.[12,23]).

Themethodsbadonthehomogenizationtheoryhave

beensuccessfullyappliedtodeterminingtheeffectivecon-

ductivityandpermeabilityofcertaincompositematerials

andporousmedia[14,10].However,theirrangeofapplica-

tionsisusuallylimitedbyrestrictiveassumptionsonthe

media,suchasscaleparationandperiodicity[8].As

discusdinSection4.2,theyarealsoexpensivetoufor

solvingproblemswithmanyparatescalessincethecost

ofcomputationgrowsexponentiallywiththenumberof

scales.Butforthemultiscalemethod,thenumberofscales

isirrelevanttothecomputationalcost.Theupscalingmeth-

odsaremoregeneralandhavebeenappliedtoproblems

withrandomcoefficientswithpartialsuccess(cf.[12,23]).

Butthedesignprincipleisstronglymotivatedbythe

homogenizationtheoryforperiodicstructures.Theirappli-

cationstononperiodicstructuresarenotalwaysguaran-

teedtowork.

Therehasalsobeensuccessinachievingnumericalho-

mogenizationforsomemilinearhyperbolicsystems,the

incompressibleEulerequations,and1Dellipticproblems

usingthesamplingtechnique;e,e.g.,[17,15,2].This

techniquehasitsownlimitations.Itsapplicationtogeneral

2Dellipticproblemsisstillnotsatisfactory.Forfullyran-

dommedia,statisticaltheoryandrenormalizationgroup

theoryhavebeenudtoobtaintheeffectiveproperties.

However,themethodsusuallybecomedifficulttoapply

whentheintegralscaleofcorrelationislarge(Ref.[23]

andreferencestherein).Moreover,certainsimplifyingas-

sumptionsintheunderlyingphysicsareusuallymadein

ordertoobtainaclosureoftheeffectiveequations.In

comparison,suchaclosureproblemisnotprentinthe

multiscalemethod.

Weremarkthattheideaofusingbafunctionsgov-

ernedbythedifferentialequationshasbeenappliedto

convection–diffusionequationwithboundarylayers(e,

e.g.,[6]andreferencestherein).Withamotivationdiffer-

entfromours,Babuskaetal.appliedasimilarideato1D

problems[5]andtoaspecialclassof2Dproblemswith

thecoefficientvaryinglocallyinonedirection[4].How-

ever,mostofthemethodsarebadonthespecialprop-

ertyoftheharmonicaverageinone-dimensionalelliptic

problems.Asindicatedbyourconvergenceanalysis,there

isafundamentaldifferencebetweenone-dimensional

problemsandgenuinelymultidimensionalproblems.Spe-

cialcomplicationssuchastheresonancebetweenthemeshandlowerbounds.Inthecontextofporousflows,Eq.

ing1Dproblems.

Thispaperisorganizedasfollows.Theformulationof

the2Dmultiple-scaleellipticproblemandthemultiscale

finiteelementmethodaregiveninthenextction.In

Section3,weprenttherationalebehindthemethod,

includingabriefreviewofthehomogenizationtheoryand

convergenceanalysis.Theresonanceeffectisanalyzedand

theoversamplingtechniqueispropod.Moredetailed

numericalanalysisofthemethodisgiveninaparate

paper[21].Thenumericalimplementationofthemethod,

itsconvergence,andparallelperformancearestudiedin

Section4.Section5containstheapplicationofthe

multiscalemethodtomorepracticalproblemsincomposite

materialsandporousmediaflows,includingsteadyconduc-

tionthroughfibercompositesandflowsthroughrandom

porousmediawithnormalandfractalporositydistribu-

tions.Usingtheexamples,weshowtheadaptabilityof

themethod,itsabilitytosolvelargepracticalproblems,

anditsaccuracyforgeneralproblems.Section6isrerved

forsomeconcludingremarksanddiscussionoffuture

work.

2.FORMULATIONS

Inthisction,weintroducetheellipticproblemand

themultiscalemethod.First,westatesomenotationsand

conventionstobeudinthepaper.Inthefollowing,

theEinsteinsummationconventionisud;summationis

takenoverrepeatedindices.Somenotationsoffunctional

spaceswillbeudoccasionallyfortheconvenienceof

expressingtheformulationandsomerelevantanalytical

estimatesaboutthemultiscalemethod.L(⍀)denotesthe

2

spaceofsquareintegrablefunctionsdefinedindomain⍀.

WeuL(⍀)badSobolevspacesH(⍀)equippedwith

2k

normsandminormsgivenby

ʈuʈ

2222

k,k,

⍀⍀

ϭ͉Dϭ͉D

͵͵

⍀⍀

͉Ͱ͉Յ͉Ͱ͉ϭ

͸͸

ͰͰ

͉,͉u͉uu͉,

kk

whereD

Ͱ

udenotestheͰthordermixedderivativesofu.

H(⍀)consistsofthofunctionsinH(⍀)thatvanish

11

0

onѨ⍀.

2.1.GoverningEquationsandtheMultiscaleFinite

ElementMethod

Weconsidersolvingthecond-orderellipticequation

Ϫٌиa(x)ٌuϭfin⍀,(2.1)

wherea(x)ϭ(a

ij

(x))istheconductivitytensorandis

assumedtobesymmetricandpositivedefinitewithupper

172

HOUANDWU

(2.1)isthepressureequationforsinglephasteadyflowelementKʦK,wedefineatofnodalbasis͕,iϭ

throughaporousmedium.Correspondingly,aistheratio1,...,d͖withdbeingthenumberofnodesoftheelement.

ofthepermeabilitytensorandthefluidviscosityȐ,andThesubscriptKwillbeneglectedwhenbasinone

␬

ureprentsthepressure.Thesteadyvelocityfieldisre-elementareconsidered.Inourmultiscalemethod,

latedtothepressurethroughDarcy’slaw:satisfies

qϭϪ

1

Ȑ

␬

ٌuϭϪaٌu(2.2)

Inthispaper,weassumeȐϭ1forconvenience.Equation

(2.1)isalsotheequationofsteadystateheat(electrical)

conductionthroughacompositematerial,withaandu

interpretedasthethermal(electric)conductivityandtem-

perature(electricpotential).Inpractice,amayberandom

orhighlyoscillatory;thusthesolutionof(2.1)displaysa

multiplescalestructure.Sinceforthetransientproblem

themaindifficultyisthesameasthatforthesteadystate

problem,i.e.,themultiplescalesinthesolution,weonly

considersolvingthesteadyproblemhere.Themultiscale

method,however,canbeeasilyextendedtosolvethetran-

sientproblems.

Tosimplifytheprentationofthefiniteelementformu-

lation,weassumeuϭ0onѨ⍀andthatthesolutiondomain

isaunitsquare⍀ϭ(0,1)ϫ(0,1).Thevariationalproblem

of(2.1)istoekuʦH

1

0

(⍀)suchthat

a(u,v)ϭf(v)᭙vʦH(⍀),(2.3)

1

0

where

a(u,v)ϭ

͵͵

⍀⍀

adx,f(v)ϭfvdx.

ij

ѨvѨu

ѨxѨx

ij

Afiniteelementmethodisobtainedbyrestrictingthe

weakformulation(2.3)toafinite-dimensionalsubspaceof

H

1h

0

(⍀).For0ϽhՅ1,letKbeapartitionof⍀bya

collectionofrectanglesKwithdiameterՅh,whichisde-

finedbyanaxi-parallelrectangularmesh(Fig.2.1).Ineach

FIG.2.1.Rectangularmeshwithtriangulation.

hi

␾

K

␾

i

ٌиa(x)ٌϭ0inKʦK

␾

ih

.(2.4)

Letx

j

ʦK(jϭ1,...,d)bethenodalpointsofK.As

usual,werequire(x)ϭ.Oneneedstospecifythe

␾ͳ

i

jij

boundaryconditionoftomake(2.4)awell-podprob-

␾

i

lem(ebelow).Fornow,weassumethatthebafunc-

tionsarecontinuousacrosstheboundariesoftheelements,

sothat

V:iϭ1,...,d;KʦK(⍀).

hih1

ϭspan͕͖ʚH

␾

K0

Inthefollowing,westudytheapproximatesolutionof

(2.3)inV,i.e.,usuchthat

hhh

ʦV

a(u,v)ϭf(v)᭙vʦV.(2.5)

hh

Notethatthisformulationofthemultiscalemethodisnot

restrictedtorectangularelements.Itcanalsobeapplied

totriangularelements(eFig.2.1)whicharemoreflexible

inmodelingcomplicatedgeometries.

2.2.TheBoundaryConditionofBaFunctions

Theimportantroleoftheboundaryconditionofthe

bafunctionsisobvioussincethebafunctionssatisfy

thehomogeneousequation(2.4).Wewillelaterthata

goodchoiceoftheboundaryconditioncansignificantly

improvetheaccuracyofthemultiscalemethod.Infact,

theboundaryconditiondetermineshowwellthelocal

propertyoftheoperatorissampledintothebafunctions

(eSection3).Here,wedescribetwomethodsofimposing

theboundarycondition,whichareeasytoimplementand

toanalyze.

DenoteȐ

iii

ϭ͉

␾

Ѩ

K

.OnechoiceistoletȐvarylinearly

alongѨK,justasinthestandardbilinear(linear)ba

functions.Anothermoreappealingapproachistochoo

Ȑ

i

tobethesolutionofsomereducedellipticproblemson

eachsideofѨK.Thereducedproblemsareobtainedfrom

(2.4)bydeletingtermswithpartialderivativesinthedirec-

tionnormaltoѨKandhavingthecoordinatenormalto

ѨKasaparameter.Itisclearthatthereducedproblems

areofthesameformas(2.4).Whenaisparableinspace,

i.e.,a(x)ϭa(x)a(y),canbecomputedanalytically

12

␾

i

MULTISCALEFINITEELEMENTMETHOD

173

FIGURE2.2

fromthetensorproductofȐalong⌫and⌫(notethat

i

⌫⌫ϵ

i1i

Ϫ

04

;eFig.2.2).Furthermore,itcanbeshownthat

thisboundaryconditionisoptimumforthespace-para-

bleproblems.

Tobemorespecific,consideranelementKʦKwith

h

nodalpointsx,y)(iϭ1,...,d),whicharelabeled

iii

ϭ(x

counterclockwi,startingfromthelowerleftcorner(Fig.

2.2).On⌫and⌫,wehaveȐ(x)and

13

ii

ϭȐ

Ѩ

ѨxѨx

a

Ȑ

(x)

ѨȐ

i

(x)

ϭ0,(2.6)

wherea

Ȑ⌫⌫Ȑ

(x)ϭaanda,respectively.Notethata

1111

͉͉

13

isboundedfromaboveandbelowbypositiveconstants.

Similarly,on⌫

24

and⌫,wehaveȐ(y)and

ii

ϭȐ

Ѩ

ѨȐ

i

(y)

ѨyѨy

a

Ȑ

(y)

ϭ0

witha(y)ϭaanda,respectively.Thebound-

Ȑ⌫⌫

2222

͉͉

24

aryconditionofthe1Dellipticequationsisgivenby

Ȑ

i

(x)ϭ.Theequationscanbesolvedanalytically.For

jij

ͳ

example,on⌫wehave

1

Ȑ

1

(x)ϭ

͵

xx

22

dtdt

xx

a(t)(t)a

ȐȐ

΋

͵

.(2.7)

1

Ifaisaconstant,thenȐ(x)ϭ(x)islinear.

Ȑ

1

221

Ϫx)/(xϪx

Ingeneral,ȐsareoscillatoryduetotheoscillationsinͰ.

i

Ȑ

Onemayverifythatusingtheaboveboundaryconditions,

thebafunctionsarecontinuousacrossѨK.Also,with

bothtypesofboundarycondition,onehas

͸

d

␾

ih

K

ϭ1᭙KʦK

.(2.8)

i

ϭ

1

Thus,theconstantfunctionsbelongtoV.Later,wee

h

thatthispropertyisufulindiscreteerrorcancellations.

Thegeneralizationofthereducedproblems,e.g.,(2.6),to

moregeneralelements,suchasthetriangularelements,is

straightforward.

2.3.SomeGeneralRemarks

Themultiscalemethodformulatedaboveisdesignedto

capturethelargescalesolutions.Unlikeexistingnumerical

upscalingmethods,ourmethodisconsistentwiththetradi-

tionalfiniteelementmethodinawell-resolvedcomputa-

tion.Itisprovedin[21]thatthemultiscalemethodgives

thesamerateofconvergenceasthelinearfiniteelement

methodwhenthesmallscalesarewellresolved,hӶ␧.

Inparticular,whenthecoefficientisadiagonalconstant

matrix,thebafunctionsconstructedfrom(2.4)arenoth-

ingbuttheusualbilinear(linear)bafunctions.Whenh

doesnotresolvethesmallscales,themultiscalemethod

andthetraditionalfiniteelementmethodbehaveverydif-

ferently.Itiseasytoshowthatthetraditionalfiniteelement

methodsdonotconvergetothecorrectsolution.Bycon-

trast,themultiscalemethodcapturesthecorrectlarge

scalesolutions.

Asindicatedbyouranalysisandnumericalexperiments

in[21],theboundaryconditionofthebafunctionscan

haveabiginfluenceontheaccuracyofthemultiscale

method.Fromourcomputationalexperience,wefound

thattheoscillatoryboundaryconditionforthebafunc-

tionsingeneralleadstobetteraccuracythanthelinear

boundarycondition.However,themultiscalemethodin

generalmayfailtoconvergewhenthemeshscaleisclo

tothephysicalsmallscaleduetoaresonancebetween

thetwoscales.Forthetwo-scaleproblem,theerrordue

totheresonancemanifestsasaratiobetweenthewave-

lengthofthesmallscaleoscillationandthegridsize.Moti-

vatedbyourearlieranalysis[21],wepropoinSection

4.4anoversamplingmethodtoovercomethedifficultydue

toscaleresonance.

3.THEORETICALBACKGROUND

Weuamodelellipticproblemtoprovidesomeinsights

tothemultiscalemethodandtherationalebehindthe

oversamplingscheme.Here,weonlybrieflyoutlinethe

analysis.Themainconcernishowtoremovethe‘‘reso-

nance’’effect.

3.1.TheModelProblemandHomogenization

Inthemodelproblem,thecoefficientischonasaϭ

a(x/␧),where␧isasmallparameter,characterizingthe

smallscaleoftheproblem.Weassumea(y)tobeperiodic

inYandsmooth.WedenotethevolumeaverageoverY

as͗и͘ϭ(1/͉Y͉)͐

Y

иdy.AsinSection2,weassumeuϭ0

onѨ⍀.

174

HOUANDWU

Bythehomogenizationtheory[8],thesolutionof(2.1)T3.1.Letuandubethesolutionsof(2.1)

hasanasymptoticexpansion;i.e.,and(2.5),respectively.Thenthereexistpositiveconstants

uϭu(x)ϩ␧u(x,y)Ϫ␧),(3.1)

01

␪

␧

ϩO(␧

2

whereyϭx/␧isthefastvariable.Here,uisthesolution

0

ofthehomogenizedequation

ٌиa*ٌuϭfin⍀,uϭ0onѨ⍀,(3.2)

00

a*istheconstanteffectivecoefficient,givenby

a*

ijikkj

ϭ͗aϪ

(y)()͘,(3.3)

ͳ

Ѩ

Ѩy

␹

j

k

andistheperiodicsolutionof

␹

j

ٌиa(y)ٌϭ

yyij

␹

j

Ѩ

Ѩy

a(y)(3.4)

i

withzeromean,i.e.,͗

␹

j

͘ϭ0.Itisprovedin[8]thata*

issymmetricandpositivedefinite.Moreover,wehave

u

uѨ

0

1

(x,y)ϭϪ.(3.5)

␹

j

Ѩx

j

Sinceingeneralu

1

϶0onѨ⍀,theboundarycondition

u͉

␪

Ѩ⍀

ϭ0isenforcedthroughthefirst-ordercorrectionterm

␧

,whichisgivenby

ٌиa(x/␧)ٌ

␪␪

␧␧

ϭ0in⍀,ϭu

1

(x,x/␧)onѨ⍀.(3.6)

Theasymptoticexpansion(3.1)hasbeenrigorouslyjusti-

fiedin[8].Undercertainsmoothnessconditions,onecan

alsoobtainpoint-wiconvergenceofutouas␧Ǟ0.

0

Theconditionscanbeweakenediftheconvergenceis

consideredintheL(⍀)space.

2

AsmentionedinSection1,somenumericalupscaling

methodsaredirectlybadon(3.2),(3.3),and(3.4);e,

e.g.,[14,10].Weutheresultsonlyfortheconvenience

ofanalysis.Indeed,theasymptoticstructure(3.1)isud

torevealthesubtledetailsofthemultiscalemethodand

obtainsharperrorestimates[21].Withoutusingthisstruc-

ture,theconventionalfiniteelementanalysisdoesnotgive

correctanswers.Anextensionoftheconvergenceanalysis

tothemultiplescaleproblemsisgivenin[16].

3.2.ErrorEstimatesandtheResonanceEffect

In[21],weprovethatthemultiscalemethodconvergesshouldbepointedoutthattheestimateonlyprovidesthe

tothecorrecthomogenizedsolutioninthe␧Ǟ0limit.rateofconvergence;theactualnumericalerrorofthe

Thiscanbesummarizedfromthefollowingestimate:multiscalemethodintheresonantregimecanstillbesmall

HEOREM

h

CandC,independentof␧andh,suchthat

12

ʈuϪuʈՅCϩC

h1/2

1,10,2

⍀⍀

hʈfʈ(␧/h)(␧Ͻh).(3.7)

Thekeyto(3.7)isthatthebafunctionsdefinedby

(2.4)havethesameasymptoticstructureasthatofu;i.e.,

␾␾␾␪

iiii

ϭϩ␧Ϫ␧ϩиии(iϭ1,...,d),(3.8)

01

where

␾␾␪

iii

,,andaredefinedsimilarlyasu,u,and

10

␪

01

␧

,respectively.Wenotethatifa*isdiagonal(i.e.,iso-

tropic),thenbecomestheusualbilinearbafunction.

␾

i

0

Wewouldliketopointoutthatapplyingtheconventional

finiteelementanalysistoourmultiscalemethodgivesan

overlypessimisticestimateO(h/␧)intheHnorm,which

1

isonlyufulforhӶ␧.Itisimportantthatweobtainan

estimateintheformof␧/hforourmultiscalemethod.This

showsthatourmethodconvergestothecorrecthomoge-

nizedsolutioninthelimitas␧Ǟ0.Thispropertyisnot

sharedbytheconventionalfiniteelementmethodswith

polynomialbas,sincesmallscaleinformationisaveraged

outincorrectly.

TheL

2

-normerrorestimatecanbeobtainedfrom(3.7)

byusingthestandardfiniteelementanalysis.However,

again,theerrorisoverestimated.In[21],itisshownthat

ʈuϪuʈՅCʈfʈϩC␧ϩCʈuϪuʈ

h2hh

0,10,23l()

⍀⍀⍀

h,

0

2

whereu

hi

00

isthesolutionof(3.2),usingsastheba

␾

3)areconstantsϾ0(iϭ1,2,independent

functionsandC

i

of␧andh.Thediscretel

2

normʈиʈisgivenby

l()

2

⍀

ʈu

hh22

ʈϭ

l()i

2

⍀

ͩͪ

͸

u(x)h,

i

ʦN

1/2

whereNisthetofindicesofallnodalpointsonthemesh.

Wewillebelowthat,ingeneral,ʈu

hh

ϪuʈϭO(␧/h).

0

l()

2

⍀

Thus,wehave

ʈuϪuʈϭO(hϩ␧/h).

h2

0,

⍀

Itisnowclearthatwhenhȁ␧themultiscalemethod

attainslargeerrorinbothHandLnorms.Thisiswhat

12

wecalltheresonanceeffectbetweenthegridscale(h)and

thesmallscale(␧)oftheproblem.Thisestimatereflects

theintrinsicscaleinteractionbetweenthetwoscalesin

thediscreteproblem.Ourextensivenumericalexperiments

confirmthatthisestimateisindeedgenericandsharp.It

MULTISCALEFINITEELEMENTMETHOD

175

duetoasmallerrorconstantinO(␧/h).ThisisindeedtheLettingG),wehaveUfAU.

caasshownbyournumericaltestsin[21].However,byNotethatGconsistsofthenodalvaluesofthefinite

removingtheresonanceeffect,wecangreatlyimprovetheelementprojectionofG(x,),thecontinuousGreen’s

accuracyandtheconvergencerate.Suchanimprovementfunctionforthehomogenizedequation(3.2).Theproper-

isespeciallyimportantforproblemswithcontinuousscales,tiesofGhavebeenstudiedin[19,24].Itturnsoutthat

becauthereisalwaysascaleoftheproblemthatcoin-GissimilartoG,whichhasalog͉xϪ͉typeofsingularity.

cideswiththegridscaleandhencetheresonanceeffectLikethecontinuousGreen’sfunction,Gisabsolutely

cannotbeavoidedbyvaryingh.InSection3.3,anover-summableoverthewholedomain.Thus,bydirectsumma-

samplingmethodispropodtoovercomethisdifficulty.tiononehasGf

Themechanismoftheresonanceeffectcanbeunder-givesGAU),whichisanoverestimate.By

stoodfromadiscreteerroranalysis[21].Forconvenience,(2.8)andthesymmetryofA,onecanwriteAUina

weoutlinetheanalysisherewithoutgivingthedetailsofconrvativeform[21],

thederivation.WederivetheO(␧/h)estimateforthel-

2

normconvergenceandillustratethedifficultyinimproving

theconvergencerate.

LetUandUdenotethenodalpointvaluesofuand

hhh

0

u,respectively.ThelinearsystemofequationsforUis

hh

0

AU,(3.9)

hhh

ϭf

whereA

hhh

andfareobtainedfroma(u,v)andf(v)by

usingvϭforiʦN.Similarly,forUonehas

␾

ih

0

AU,(3.10)

hhh

000

ϭf

whereA

hhi

000

andfareobtainedbyapplyingvϭ(iʦN)

␾

toa*(u,v)ϭf(v)with

hN1

0

a*(u,v)ϭadx.

h

0

͵

⍀

*

ij

Ѩv

Ѩu

h

0

ѨxѨx

ij

Byusing(3.8),itcanbeshownthat

A,f,

hhhhhh

ϭAϩϩOϭfϩϩO

␧␧␧␧

22

0101

hhhh

Af

ͩͩ

22

ͪͪ

(3.11)

wheretheelementsofmatrixAandvectorfareO(1)

hh

11

andO(h),respectively.TheexpansionofAindicatesthat

2h

thehomogenizeddifferentialoperatoriscapturedatthe

discretelevelbythemultiscalebafunctions.Itfollows

immediatelythatUcanbeexpandedas

h

U

hhh

ϭUϩϩиии,

01

␧

h

U

thusUconvergingtoUasǞ0.Toobtaintheconver-

hh

0

gencerate,itremainstodeterminetheorderofU

h

1

.Substi-

tutingtheexpansionsofA,f,andUinto(3.9),weobtain

hhh

A

hhhhh

01110

UU.(3.12)

ϭfϪA

hhhhhhhh

ϭ(AϭGϪG

01110

Ϫ

1

h

␰

h

h

␰

h

hh

ϭO(1/h

1

ϭO(1).However,thedirectsummation

2hhh

10

hhh

110

(AU),(3.13)(DBD)U

hhsh

10ij0ij

ijss

ϭ

Ϫϩ

s

͸

4

ϭ

1

where(i,j)isthe2Dindexforgridpoints(Fig.2.1),and

BobtainedfromAaretheweightsforthestencil.Here,

sh

ij1

DandDaretheforwardandbackwarddifferenceopera-

ϩϪ

ss

torsinthehorizontal,thevertical,andthetwodiagonal

directionsforsϭ1to4,respectively.Forexample,we

haveD

ϩϪ

11j31j1

UandDU.For

hhhhhh

ijiijijiji

ϭUϪUϭUϪU