POSTPROCESSING THE GALERKIN METHOD:
THE FINITE-ELEMENT CASE∗
BOSCO GARC´
IA-ARCHILLA†AND EDRISS S. TITI‡
SIAM J. NUMER. ANAL.c
°2000 Socie y o Indus ial and Applied Ma hema ics
Vol. 37, No. 2, pp. 470–499
Abs ac . A pos p ocessing echnique, de eloped ea lie o spec al me hods, is ex ended
he e o Gale kin ini e-elemen me hods o dissipa i e e olu ion pa ial di e en ial equa ions. The
pos p ocessing amoun s o sol ing a linea ellip ic p oblem on a ine g id (o highe -o de space)
once he ime in eg a ion on he coa se mesh is comple ed. This echnique inc eases he con e gence
a e o he ini e-elemen me hod o which i is applied, and his is done a almos no addi ional
compu a ional cos . The nume ical expe imen s p esen ed he e show ha he esul ing pos p ocessed
me hod is compu a ionally mo e e icien han he me hod o which i is applied (say, quad a ic ini e
elemen s) as well as s anda d me hods o simila o de o con e gence as he pos p ocessed one (say,
cubic ini e elemen s). The e o analysis o he new me hod is pe o med in L2and in L∞no ms.
Key wo ds. dissipa i e equa ions, pos p ocessing ini e-elemen me hods, mul ile el me hods,
nonlinea Gale kin me hods
AMS subjec classi ica ions. 65P25, 65M70, 65M15, 65M20
PII. S0036142998335893
1. In oduc ion. Fini e-elemen me hods do no seem o ha e bene i ed as
much as spec al me hods om some o he ecen ad ances in he dynamical sys-
ems app oach o pa ial di e en ial equa ions (PDEs) like hose in [15], [14], [13],
and [41]. Since hese ad ances a e mos ly based on spec al decomposi ions, hey a e
eadily adap ed o spec al me hods, bu do no seem o ha e a clea -cu ansla ion
o ini e elemen s. In [21] and based on he esul s o [15] and [13], an inexpensi e
no el echnique o inc ease he accu acy and compu a ional e iciency o Fou ie spec-
al me hods was de eloped. In his pape , we p esen a gene al echnique o imp o e
he con e gence a e o Gale kin me hods which applies o ini e-elemen me hods
(and in he pa icula case o Fou ie –Gale kin me hods i coincides wi h ha in [21];
see also [37]). We do his wi h no di ec add ess o [13].
Le Ω ⊂Rdbe a domain wi h a smoo h bounda y. We conside dissipa i e PDEs
(see, o ins ance, [8], [24], [25], [41]) which can be w i en as e olu ion sys ems o he
o m
du
d +νAu +F(u)=0,(1)
in he Hilbe space H(in his wo k H=L2(Ω)), wi h solu ions de e mined uniquely
by he ini ial condi ion
u(·,0) = u0.(2)
∗Recei ed by he edi o s Ma ch 19, 1998; accep ed o publica ion (in e ised o m) Ma ch 8,
1999; published elec onically Janua y 5, 2000. This wo k was pa ially inanced by DGICYT p ojec
PB95-216 and he Na ional Science Founda ion and was comple ed while he second au ho was he
O son Ande son Visi ing Schola a he Ins i u e o Geophysics and Plane a y Physics (IGPP) a
he Los Alamos Na ional Labo a o y.
h p://www.siam.o g/jou nals/sinum/37-2/33589.h ml
†Depa amen o de Ma em´a icas, Uni e sidad Au ´onoma de Mad id, 28049 Mad id, Spain
(b[email p o ec ed]). Cu en add ess: Dep o. Ma ema ica Aplicada II, Uni e sidad de Se illa,
Escuela Supe io de Ingenie o , Camino de lo Descub imien o S/N, 41092 Se illa (Spain)
‡Depa men o Ma hema ics and Depa men o Mechanical and Ae ospace Enginee ing, Uni-
e si y o Cali o nia, I ine, CA 92697-3875 ([email p o ec ed]).
470
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
POSTPROCESSING FINITE-ELEMENT METHODS 471
He e, ν>0 is a scala , A:D(A)⊂H→His a densely de ined, unbounded,
sel -adjoin , and posi i e ope a o wi h compac in e se. Fo simplici y, we ea
he e only he case A=−∆, whe e ∆ s ands o he Laplacian ope a o subjec
o homogeneous Di ichle bounda y condi ions, bu ou esul s also apply o o he
ellip ic ope a o s in di e gence o m wi h su icien ly smoo h coe icien s and (wi h
adequa e modi ica ions) o o he bounda y condi ions. The (nonlinea ) ope a o F
ha we conside is one o he ollowing wo ypes:
1. eac ion-di usion equa ions,
F(u)=g(u),(3)
o some smoo h unc ion g:R→R;
2. eac ion-di usion equa ions plus nonlinea con ec ion,
F(u)=g(u)+b(u)·∇u,(4)
o some smoo h mapping b:R→Rd, and gis as abo e.
Fo simplici y, we concen a e he e on he wo ypes o nonlinea i y abo e, bu
bo h gand bcan be made dependen on xand as well. Also, al hough we concen a e
on scala equa ions, he esul s he e can be ex ended o sys ems. We ea he e he
case whe e Ω ⊂Rdwi h d>1; he case d= 1 is pa icula and much simple o
analyze.
Le Th=(τ
h
i,φ
h
i)
i∈I
h,h>0, be a amily o pa i ions o sui able domains Ωh,
whe e he pa ame e his he maximum diame e o he elemen s τh
iin Th, and φh
i
a e he mappings o he e e ence simplex τ0on o τh
i.Fo ≥2 we conside he
ini e-elemen spaces
Sh, =nχh∈C(Ωh)|χh|τh
i◦φh
i∈P −1(τ0),χ
h
(x)=0 ∀x∈∂Ω
h
o,
whe e P −1(τ0) deno es he space o polynomials o deg ee a mos −1onτ
0
.
Le us deno e by a(·,·) he posi i e de ini e, bilinea o m induced by A, ha is,
a(u, )=(A
1/2
u, A1/2u)=(∇u, ∇ ) o u, ∈D(A1/2)=H
1
0(Ω), whe e (·,·) deno es
he s anda d inne p oduc in L2(Ω) (o in L2(Ω)d). In a simila manne le ah(·,·)
be he co esponding bilinea o m on Sh, (in ou case ah(χh,ψ
h)=(∇χ
h
,∇ψ
h
)
h
,
χ
h
,ψ
h∈S
h, , whe e (·,·)hs ands o he s anda d inne p oduc in L2(Ωh)); and le
us deno e by Ah he associa ed posi i e, sel -adjoin ope a o in Sh, , ha is,
ah(χh,ψ
h)=(A
h
χ
h
,ψ
h)
h=(χ
h
,A
hψ
h)
h∀χ
h,ψ
h∈S
h, .
Le us also deno e by Ph he s anda d L2o hogonal p ojec ion on o Sh, , and
by Rh he ellip ic p ojec ion on o Sh, (also known as he H1p ojec ion) which, o
u∈H1
0(Ω) is de ined by
ah(Rhu, χh)h=ah(u, χh)=(∇u, ∇χh)h∀χh∈Sh, .
The disc epancy be ween Ω and Ωhis usually sol ed by an adequa e selec ion o
quad a u e ules, al hough o he al e na i es a e also possible (see sec ion 2.1).
The Gale kin app oxima ion o he solu ion uo (1)–(2) is desc ibed as ollows:
Find uh:[0,T]→S
h, such ha
d
d uh+νAhuh+PhF(uh)=0,(5)
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
472 BOSCO GARC´
IA-ARCHILLA AND EDRISS S. TITI
uh(0) = Rhu0.(6)
We use (6) o simplici y in he analysis. Ou esul s may be easily ex ended o he
case whe e uh(0) = Phu0.
Nex , we mo i a e and in oduce he me hod s udied he e. Suppose ha we a e
in e es ed in he solu ion uo (1)–(2) a a gi en ime T. A ime T, ew i ing (1),
we ha e ha νAu(T)=−F(u(T)) −d
d u(T). Thus, u(T) can be seen as he solu ion
o an ellip ic p oblem whose igh -hand side is no known bu can be app oxima ed.
The me hod we p opose is as ollows.
(i) Fi s , in eg a e (5)–(6) up o T o ob ain he Gale kin app oxima ion uh(T).
(ii) Then sol e (o , in p ac ice, app oxima e) he ollowing linea ellip ic p oblem:
Find ˜u∈D(A) such ha
νA˜u=−F(uh(T)) −d
d uh(T).(7)
We call his app oxima ion p ocedu e he pos p ocessed Gale kin me hod. Unde
ce ain assump ions ( o be speci ied in sec ion 2.1) we can s a e Theo em 1 below,
whose p oo is de e ed un il sec ion 2.3 (a e sion o his esul in L∞is p esen ed
in sec ion 4.1). In Theo em 1 and in he es o he pape , he cons an s µand a e
µ=2i ≥4 and (3) holds,
1 o he wise, =0i = 3 and (3) holds,
1 o he wise.
Theo em 1. Le T>0and ≥3.The e exis s a cons an C>0which depends
on K(u),de ined in (22) below, such ha o hsu icien ly small he pos p ocessed
Gale kin app oxima ion ˜usolu ion o (7) sa is ies
ku(T)−˜ukL2(Ω) +hku(T)−˜ukH1(Ω) ≤Ch +µ|log(h)| .(8)
We no ice ha he bound (8) is an imp o emen o e he s anda d Gale kin e o
bound, ku−uhkL2(Ω) +hku−uhkH1(Ω) ≤Ch , which is op imal e en in he case o
linea p oblems.
We ema k ha in p ac ice, o cou se, ˜ucanno be compu ed exac ly since in
gene al i does no belong o a ini e-dimensional space, as opposed o uh. Howe e ,
one can app oxima e he solu ion ˜uo (7) by some ˜uhbelonging o a ini e-elemen
space o piecewise polynomials ei he o deg ee +µ−1 o e Th, o o deg ee −1
bu o e some ine pa i ion Th0wi h h +µ=h0 .
I mus be no iced ha , om he p ac ical poin o iew, he compu a ional cos
o he pos p ocessing s ep (7) is a e y small ac ion o he cos o compu ing uh(T)by
ime in eg a ion om =0 o =T. Thus, ˜uhis an app oxima ion o u(T) o highe
o de (i.e., asymp o ically mo e accu a e) han uh(T), bu i cos s (almos ) no hing
once uh(T) is a ailable. We will see he implica ions o his ac in he nume ical
expe imen s in sec ion 3.
Obse e ha he combina ion o he Gale kin me hod (5)–(6) and he pos p o-
cessing s ep (7) can be seen as a no el wo-le el o wo-g id me hod o e olu ion
equa ions. Two-le el me hods o nonlinea p oblems ha e mos ly been de eloped
and implemen ed o s eady equa ions (see, e.g., [5], [31], [47], [48], and he e e ences
he ein). The basic idea in he s eady-s a e case is o sol e he nonlinea p oblem on
a low-o de app oxima ion space (o coa se g id) and hen ob ain a be e app oxi-
ma ion wi h one o wo New on i e a ions on a highe -o de app oxima ion space (o
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
POSTPROCESSING FINITE-ELEMENT METHODS 473
on a ine g id). In his way, he nonlinea i ies a e ea ed in he (cheape ) low-o de
app oxima ion space o coa se g id, and only linea sys ems a e sol ed in he (mo e
cos ly) highe -o de app oxima ion space.
On e olu ion p oblems, wo-le el (o u he , mul ile el) me hods can ob iously
be used in he nonlinea sys ems ha a ise when using implici ime in eg a o s.
O he mo e e ined ideas ha e ecen ly been sugges ed [3], [9], [33], [34], bu , so a ,
he wo le els o disc e iza ion a e used a e e y ime s ep along he ime e olu ion.
On he con a y, Theo em 1 in his pape s a es ha i is sa e o pe o m he ime
e olu ion on he low-le el (o coa se g id) app oxima ion space and ob ain he highe -
o de co ec ion only once,a =T, ha is, when he ime-ma ching is inished. The
p ice o be paid is ha he low-le el (o coa se g id) app oxima ion space mus be
composed o piecewise polynomials wi h a deg ee o a leas 2 ( ≥3), since he
pos p ocessing s ep (7) does no inc ease he con e gence a e i uh(T) is compu ed
by in eg a ing on ime on a space o piecewise-linea polynomials.
The pos p ocessing s ep (7) is a gene aliza ion o ini e-elemen me hods o an
ea lie pos p ocessing p ocedu e de eloped o spec al me hods in [16], [21], and
[22]. To be mo e speci ic, suppose ha ins ead o Sh, , he app oxima ion space is
Hmspanned by he eigen unc ions o Aassocia ed wi h he lowes meigen alues o
equencies. Then, he Gale kin app oxima ion (5) would be um:[0,T]→H
msuch
ha
dum
d +νAum+PmF(um)=0,(9)
whe e Pmis he L2p ojec ion on o Hm. The pos p ocessing s ep (7) would be
νA˜u=−dum
d (T)−F(um(T)).(10)
P ojec ing (10) on o Hm, since Pmand Acommu e, we ge νAPm˜u=−PmF(um(T))−
dum( )
d  =T, and hence, Pm˜u=um(T), he Gale kin app oxima ion a ime T. Thus,
one has only o compu e he high- equency modes ˜q=(I−P
m
)˜u. Applying (I−Pm)
o (10) we ob ain
νA˜q=−(I−Pm)F(um),(11)
which is he pos p ocessing s ep p oposed in [21], [22]. Obse e also ha ˜q=Φ(u
m
)=
(νA)−1(I−Pm)F(um).
The o mula ion (11) o he pos p ocessing s ep is mo e na u al in he case o
spec al me hods. Howe e , when de eloping his pape , (7) (o (10)) was seen o be
mo e meaning ul and use ul. This poin o iew was also eached independen ly in
[17], [18].
In ac , in he case o spec al me hods, he pos p ocessed Gale kin me hod was
de eloped he opposi e way. In he con ex o ine ial mani olds [14] and app oxi-
ma e ine ial mani olds, i was shown in [13] (see also [15]) ha gi en he low modes
Pmuo he solu ion uo (1)–(2), Φ(Pmu)=(νA)−1(I−Pm)F(Pmu) is a high-o de
app oxima ion o he high- equency modes (I−Pm)uo u. Based on his ac , he
so-called nonlinea Gale kin me hods (NLG) [12], [28], [32] we e de eloped (see also
[10], [11], [15], [29], [42], [43], and he many e e ences he ein). In hese NLG me h-
ods, nonlinea e ms a e ypically e alua ed in he whole spec um (o some gene ous
unca ion o i ), o example, F(ym+Φ(ym)), whe e ym( )∈Hmis he low- equency
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
474 BOSCO GARC´
IA-ARCHILLA AND EDRISS S. TITI
componen o he NLG app oxima ion ym+Φ(y
m
). This is compu a ionally cos ly,
and ( o add o he cos ) i is done along he ime e olu ion in NLG me hods.
Cu en ly, he e is enough a ailable e idence [20], [21], [35], [46] ha NLG me h-
ods a e no compe i i e om he poin o iew o e iciency (o a leas , no necessa ily
compe i i e). Fo his eason, he pos p ocessed Gale kin (spec al) me hod (9)–(10)
was de eloped. The aim was o exploi he app oxima ion capabili ies o Φ bu
wi hou paying o he compu a ional cos o NLG me hods (no ice ha in (9)–(10)
nonlinea e ms a e applied only o elemen s o Hm, and Φ is compu ed only once).
The pos p ocessed Gale kin me hod was seen o be compu a ionally mo e e i-
cien han classical Gale kin spec al me hods in [16] and [21]. This is also he case
o Gale kin ini e-elemen me hods, as is shown in sec ion 3 and in [30]. The compu-
a ional gain is e en mo e signi ican in he maximum no m. The las sec ion o his
pape is de o ed o he e o analysis in L∞.
We end his sec ion by gi ing an idea o he p oo o Theo em 1. E alua e he
PDE (1) a ime =Tand sub ac i om (7). A e ea anging e ms and applying
A−1one sees ha
u(T)−˜u=1
νA−1d
d uh(T)−d
d u(T)+1
νA−1(F(uh(T)) −F(u(T))).
Thus, a i s sigh , u(T)−˜udepends on uh(T)−u(T) (and (duh/d )−(du/d )| =T)
which is only O(h ). Howe e , in due cou se we will show ha °
°A−1(F(uh(T)) −
F(u(T)))°
°L2(Ω) can be bounded in e ms o °
°A−1(u(T)−uh(T))°
°L2(Ω) (A−1/2ins ead
o A−1when Fis gi en by (4)). We w i e u−uh=(u−R
h
u)+(R
hu−u
h). Since i
is well known (see, e.g., [44]) ha °
°A−1(I−Rh)u(T)°
°L2(Ω) =O(hmin(2 −2, +2)) (and
he same bound o A−1(I−Rh)u (T)), we ha e ha
ku(T)−˜ukL2(Ω) ≤C
νð
°A−1(uh(T)−Rhu(T))°
°L2(Ω)
+°
°
°
°
A−1d
d uh(T)−Rh
d
d u(T)°
°
°
°L2(Ω)!+O(hmin(2 −2, +2)).(12)
The O(hmin(2 −2, +2)) e m abo e clea ly shows ha he pos p ocessed me hod will
ha e a s ic ly highe con e gence a e han he Gale kin me hod on which i is
based, only i ≥3, ha is, uh(T) is a piecewise polynomial wi h a deg ee o a leas
2. We will duly show ha he o he wo e ms on he igh -hand side o (12) a e
O(h +µ|log(h)| ).
The a gumen abo e shows ha he e is no hing especially nonlinea abou he
idea behind he pos p ocessed Gale kin me hod, and he esul s would be he same i
Fwe e linea . No ice ha e en in he linea case he me hod p esen ed he e allows
an O(h +2) (o O(h +1)) e o a he “same” p ice o a cheape O(h ) me hod. In
any case, since mos o he in e es ing phenomena a ise in nonlinea p oblems, o
comple eness we conside Fas in (3)–(4).
The es o his pape is o ganized as ollows. Sec ion 2 is de o ed o p o ing
Theo em 1. Nume ical expe imen s a e p esen ed in sec ion 3. Finally, we ca y he
L∞analysis in sec ion 4.
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php

POSTPROCESSING FINITE-ELEMENT METHODS 475
2. The pos p ocessed Gale kin me hod.
2.1. P elimina ies. We now p esen he assump ions unde which Theo em 1
holds. We es ic ou sel es o quasi-uni o m meshes Th, so ha he ollowing in e se
es ima e holds o any elemen τ∈T
hand h∈Sh, (see, e.g., [39]):
k hkWm,p(τ)≤Chl−m−d(1
q−1
p)k hkWl,q (τ),0≤l≤m≤2,1≤q≤p≤∞.(13)
Also, we assume he ollowing es ic ion be ween he o de o app oxima ion
and he dimension d:
d≤2 −1.(14)
This is equi ed by he p esence o he nonlinea e m F, bu i can be loosened i
Fis linea . Since ini e elemen s a e mos ad an ageous when dealing wi h complex
geome ies, we conside only d≥2. Following he ideas p esen ed he e, he one-
dimensional case admi s a much simple ea men .
In his si ua ion, o 1 ≤p≤∞, and o any ∈D(A)∩W ,p(Ω), an in e polan
Ih( )∈Sh, exis s such ha
k −Ih( )kLp(Ω) +hk −Ih( )kW1,p(Ω∩Ωh)≤C¡h +δ(h)k kW ,p (Ω) ,(15)
(we ex end by ze o Ih( )inΩ Ω
h
), whe e δ(h) = maxx∈Ωhdis (x, ∂Ω). Fo x∈Ω∩Ωh,
his bound ollows om he s anda d heo y o in e pola ion and he B amble–Hilbe
lemma. Fo x∈Ω Ωh, (x) can be bounded using o he mean- alue heo em (see,
e.g., (19) below).
Howe e , o he pu pose o analysis, we may assume (see, e.g., [39]) ha Ωh⊆Ω,
since one may conside a domain Ωδwi h a smoo h bounda y such ha Ω ∪Ωh⊂Ωδ,
and max {dis (x, ∂(Ω ∪Ωh)) |x∈∂Ωδ}≤c
0
δ(h) o some c0>0. Then, o each
, eplace u( ) by he solu ion uδ( )o −∆u
δ
( )=
u
( ), whe e u( ) is a sui able
ex ension o −∆u( ) oΩ
δ(see [39] o de ails). The se s Ωδmus be buil so ha o
δsu icien ly small we ha e ha
k δkWl+2,p(Ωδ)≤Cpk kWl,p(Ωδ)=Cpk∆ kWl,p(Ω) ,0≤l≤ ,
o e e y p∈[2,∞) and e e y ∈W +2(Ω). He e Cp>0 cons an ha depends
on pbu no on δ. This can be eadily done i Ω is bounded and + 2 smoo h, o
uni o mly + 2 smoo h [1, p. 67].
We will also assume ha he solu ion o (1) sa is ies
M3= max
0≤ ≤T°
°A3/2u(·, )
°
°L
2(Ω) <+∞.(16)
To ensu e he es ima e (16) o e e y solu ion o (3), (4), wi h ini ial da a in D(A3/2),
i is su icien o equi e, o example, ha bo h gand bsa is y g(0) = 0 and b(0)=0.
I , in addi ion, he igh -hand side o (1) has a smoo h o cing e m = (x, ) ins ead
o ze o, hen i is su icien ha (x, ) has a ze o ace a he bounda y o Ω.
In he unde s anding o he pos p ocessed Gale kin me hod, he ellip ic p ojec ion
Rhuo uwill play a p ominen ole. To simpli y no a ion we w i e
h=Rhu.
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
476 BOSCO GARC´
IA-ARCHILLA AND EDRISS S. TITI
Unde hese condi ions he ollowing bounds hold o 1 ≤l≤ :
ku−PhukL2(Ω)
ku− hkL2(Ω) +hku− hkH1(Ω) ≤ChlkukHl(Ω) ,(17)
and, o 0 ≤s≤2,
°
°A−s/2(u−Phu)°
°L2(Ω)
°
°A−s/2(u− h)°
°L2(Ω) )≤Chl+skukHl(Ω) , s = min(s, −2).(18)
Fo hese bounds o hold, ca e mus be aken o app oxima e he bounda y wi h he
necessa y accu acy (see, e.g., [44, sec ion 5.1]). Hence o h, we will assume ha o
some cons an cδ>0,
δ(h) = max
x∈Ωh
dis (x, ∂Ω) ≤cδh +2.
We also ema k ha (16) plays a ole in o de o bound k∇(u− h)kL2(Ω) in e ms
o hl−1kukHl(Ω) in (17), due o he skin-laye Ω Ωh. To be mo e p ecise, le D⊂Ω
be such ha max{dis (x, ∂Ω) |x∈D}≤cδ(h). Fo any ∈D(A), since =0on
∂Ω, one can check ha
k kL2(Ω D)≤Cδ(h)k∇ kL2(Ω) .(19)
Hence, aking D=Ω
h
, we ha e ha
k∇ kL2(Ω Ωh)≤Ck k1/2
L2(Ω Ωh)k k1/2
H2(Ω Ωh)≤Cδ(h)1/2k kH2(Ω) .
Fo ∈D(A3/2) be e es ima ions can be ob ained as ollows. Conside Ω1⊂⊂
Ωhwi h a su icien ly smoo h bounda y such ha max{dis (x, ∂Ωh)|x∈Ω1}≤
c
0
δ(h) o some c0>0. Then k∇ kL2(Ω Ωh)≤k∇ k
L
2
(Ω Ω1). Using he di e gence
heo em, ace heo ems, and he smoo hness o Ω, one can show ha k∇ k2
L2(Ω Ω1)≤
k∆ kL2(Ω Ω1)(k kL2(Ω Ω1)+k∇ kL2(Ω Ω1)). Now, ecalling (19), we ha e ha
°
°∇ °
°L2(Ω Ωh)≤Cδ(h)k kH3(Ω) .
Fo he L2p ojec ion Phwe will use s onge es ima es han hose in (17). Mo e
p ecisely, he e exis s a cons an C>0 such ha
k −Ph kLq(Ω) ≤Ck kLq(Ω) ,1≤q≤∞,(20)
∀ ∈Lq(Ω) (see, e.g., [44, p. 39]). Simila ly, o he ellip ic p ojec ion
kRhk∞≤C(21)
(see [39]), whe e, he e and in he es o he pape , k·kpdeno es he ope a o no m
in L(Lp(Ω)) o 1 ≤p≤∞. We ema k ha o piecewise-linea ini e elemen s (i.e.,
= 2) he bound (21) does no hold (Cshould be eplaced by C(1+|log(h)|)). In
his pape , howe e , we es ic ou sel es o ≥3.
The e o es ima es in sec ions 2.2 and 2.3, as well as he cons an Cin Theo em
1 depend on
K(u, )=ku(·, )kH (Ω) +ku (·, )kH (Ω) ,K(u) = max
0≤ ≤TK(u, ).(22)
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
POSTPROCESSING FINITE-ELEMENT METHODS 477
No ice hen, ha we a e assuming su icien smoo hness o he solu ion as well as o
he ini ial condi ion. I mus be s a ed ha i (1) is au onomous and gand bin he
nonlinea e ms Fin (3)–(4) a e analy ic, due o he analy ici y in ime o he solu ions
o (1)–(2), o mos ini ial condi ions u0, i is possible o bound ku (·, )kH (Ω) in e ms
o maxz∈Sku(·,z)kH (Ω) o zin an adequa e neighbo hood So [0,T] in he complex
plane (see, e.g., [7, pp. 104–109]).
We will equen ly use he ollowing e sion o Sobole ’s lemma: o p∈[1,∞),
he e exis s a cons an C=C(Ω,p) such ha
k kLp0(Ω) ≤Ck kWs,p(Ω) o 1
p≥1
p0≥1
p−s
dand ∈Ws,p(Ω)
whene e p0<∞.Fo p
0=∞ he abo e inequali y holds o 1
p≥1
p0>1
p−s
d, and,
u he mo e, in his case is also a con inuous unc ion.
Also he ollowing inequali y, which is easily ob ained om H¨olde ’s inequali y,
will be equen ly used:
|( , w))|≤k k
L
2
(Ω) k kLp(Ω) kwkLq(Ω) ,1
p+1
q=1
2.(23)
2.2. Analysis o he Gale kin me hod. In his sec ion we ob ain bounds o
uh− h. The main esul is Theo em 2 a he end o he sec ion. I s p oo will be
ob ained as a consequence o se e al p e ious lemmas.
In he ollowing, we need he esidual o unca ion e o Tho he ellip ic p o-
jec ion h= h( )=R
h
u( ). No ice ha hsa is ies
d
d h+νAh h+PhF( h)=T
h
,(24)
whe e he unca ion e o This
Th=Ph(F( h)−F(u)) + d
d h−Phu .(25)
In gene al, kThkL2(Ω) is no smalle han ku −d h/d kL2(Ω) =O(h ). In ac ,
he abo e is de ini ely ue in he linea case when F= 0. On he o he hand,
no ice ha in Lemma 4 below, we bound no only kThkL2(Ω) bu also an in eg al o
e−ν( −s)AhTh(s) wi h espec o s. I is he smoo hing e ec o he semig oup e−ν Ah
ha gi es he ex a powe hµ|log(h)| in Theo em 2 wi h espec o he O(h ) decay
o kThkL2(Ω).
Lemma 1. Le h:[0,T]→S
h, sa is y he h eshold condi ion,
k h( )− h( )kL2(Ω) ≤c hh ,(26)
o ∈[0,T]. Se µ=0i he nonlinea i y Fis gi en by (3); o he wise se µ=1
when Fis gi en by (4). Then he e exis s a cons an C, which depends on c h and
max0≤ ≤Tku( )kH (Ω), such ha o ∈[0,T]
°
°A
−µ/2
hPh(F( h( )) −F( h( )))°
°L2(Ω) ≤Ck h( )− h( )kL2(Ω) .(27)
Fu he mo e, o Fgi en by (4) we ha e ha
kPh(F( h( )) −F( h( )))kL2(Ω) ≤C¡k∇( h( )− h( ))kL2(Ω)
+h−1k h( )− h( )kL2(Ω).(28)
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
478 BOSCO GARC´
IA-ARCHILLA AND EDRISS S. TITI
P oo . Le us ake ∈[0,T], and o simplici y, le us d op he explici dependence
on . We i s no ice ha bo h hand ha e bounded in L∞in e ms o u, since
k hkL∞(Ω) ≤k
h−
h
k
L
∞
(Ω) +k hkL∞(Ω), which, hanks o he in e se es ima e (13)
and he h eshold condi ion (26), is bounded by c hh −d/2+k hkL∞(Ω). Then in iew
o he ac ha Rhis bounded in L∞( ecall (21)), Sobole ’s lemma, and he es ic ion
(14) be ween he dimension dand we ha e ha k hkL∞(Ω),k hkL∞(Ω) ≤CkukH (Ω).
As a consequence, o any smoo h unc ion ,
( h), (
h)∈L
p(Ω) o 1 ≤p≤∞.(29)
Thus, o Fas in (3), he s a emen (27) is a di ec consequence o he mean- alue
heo em.
Fo Fas in (4) we i s p o e (27). No ice ha A−µ/2
hPh=A1−µ/2
hA−1
hPh=
A1−µ/2
hRhA−1. In addi ion, o χh∈Sh, , we ha e ha kA1/2
hχhkL2(Ω) =k∇χhkL2(Ω),
and kA−1·kH1(Ω) ≤CkA−1/2·kL
2(Ω). Then, using (17) we ha e ha
°
°A−1/2
hPh(F( h)−F( h))°
°L2(Ω)≤C°
°A−1/2(F( h)−F( h))°
°L2(Ω).
Le us es ima e he igh -hand side abo e by duali y. Since A−1/2is bounded, we
need only o s udy he con ec ion e m. Le us deno e eh= h− h. We ha e ha
b( h)·∇
h−b(
h
)·∇
h=b(
h
)·∇e
h+(b(
h
)−b(
h
)) ·∇
h
.(30)
Le φ∈C∞
0(Ω) be a es unc ion. Taking he inne p oduc in (30) wi h φand
in eg a ing by pa s he i s e m on he igh -hand side abo e becomes
¡b( h)·∇e
h
,A
−1/2φ
=¡e
h,di ¡b( h)A−1/2φ
=¡eh,b
0(
h)·∇
h
A
−1/2φ
+¡e
h
,b(
h)·∇A
−1/2φ
.(31)
We now ake psuch ha
1
p=1/4i d=2
1/2−1/d i d>2.
Then, by Sobole ’s lemma, we ha e ha k·kL
p(Ω) ≤Ck·kH
1(Ω), and, in pa icula ,
kA−1/2φkLp(Ω) ≤CkφkL2(Ω). We also ake qsuch ha 1/q +1/p =1/2. Fo his
alue o q, hanks o (14), i is immedia e o check ha
kukW1,q(Ω) ≤CkukH (Ω) .(32)
Applying (23) o he igh -hand side o (31), we ha e ha
¡eh,b
0(
h)·∇
h
A
−1/2φ

≤Cke
h
kL
2(Ω) kb0( h)kL∞(Ω) k∇ hkLq(Ω) kφkL2(Ω) ,
¡eh,b(
h)·∇A
−1/2φ

≤Cke
h
kL
2(Ω) kb( h)kL∞(Ω) kφkL2(Ω) .
Also, o he second e m on he igh -hand side o (30), hanks o he mean- alue
heo em and (29), a guing as abo e we ha e ha
¡(b( h)−b( h))∇ h,A
−1/2φ

≤Cke
hkL
2(Ω) k∇ hkLq(Ω) kφkL2(Ω) .
Thus, (27) is p o ed, p o ided we show ha
k∇ hkLq(Ω) ,k∇ hkLq(Ω) ≤CkukH (Ω)
(33)
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
POSTPROCESSING FINITE-ELEMENT METHODS 485
P oo o Theo em 1. Sub ac ing (7) om (1) and applying νA−1we ha e ha
u(T)−˜u=ν−1A−1(F(uh(T)) −F(u(T))) + A−1duh
d (T)−du
d (T).(59)
Since k∇·kL2(Ω) =°
°A1/2·°
°L2(Ω), hen by Lemma 3 and an a gumen simila o ha
leading om (50) o (47), we ob ain he ollowing bounds:
ku−˜ukL2(Ω) ≤C°
°A−1(uh−u)°
°L2(Ω) +°
°A−1(uh−u) °
°L2(Ω) +2,(60)
ku−˜ukH1(Ω) ≤C°
°A−1/2(uh−u)°
°L2(Ω) +°
°A−1/2(uh−u) °
°L2(Ω) +1,(61)
whe e o µ=1,2, µ=ku−uhkLq(Ω)ku−uhkHi(Ω), wi h qas indica ed in Lemma
3 and i= 1 when Fis gi en by (4); o he wise i=0.
Le us i s ind an uppe bound o µ. We w i e
u− h=(u−
h
)+(
h−u
h
).(62)
Fo h−uh, using he in e se es ima e (13) and Theo em 2, we ha e ha
k h−uhkLq(Ω) ≤Chd
q−d
2k h−uhkL2(Ω) ≤CK(u)h +µ+d
q−d
2|log(h)| .
Bu d/q−d/2=−d/p, which, in iew o (38), allows us o w i e +µ−d/p ≥µ+µ−1,
whe e we ha e used ha ≥3 in he case d/2<µ. This and (52) lead o
ku−uhkLq(Ω) ≤CK(u)hmin(µ+µ−1,µ)|log(h)| .
Using again (62), applying (17), (13), and Theo em 2, one can show ha
ku−uhkHi(Ω) ≤CK(u)h −i,
whe e i= 1 when Fis gi en by (4); o he wise i= 0. Hence, i ollows ha
2≤CK(u)h +µ|log(h)| ,
1
≤CK(u)h +1−i|log(h)| .
Le us now u n o he o he e ms in (60)–(61). Using (62) and aking in o
accoun ha A−µ/2is bounded, we ha e ha
°
°A−µ/2(u−uh)°
°L2(Ω) ≤°
°A−µ/2(u− h)°
°L2(Ω) +Ck h−uhkL2(Ω) ,
°
°A−µ/2(u−uh) °
°L2(Ω) ≤°
°A−µ/2(u− h) °
°L2(Ω) +°
°A−µ/2( h−uh) °
°L2(Ω).
Then, (17)–(18) and Lemma 6, oge he wi h (54), yield he bound (8).
3. Nume ical expe imen s. We conside he eac ion-di usion sys em
∂u1
∂ =1−4u
1+u
2
1
u
2+ν∆u
1
∂u2
∂ =3u
1
−u
2
1
u
2
+ν∆u
2

known as he B ussela o (see, e.g., [27]), in Ω ×[0,T], whe e Ω = [0,1]2and T= 10,
subjec o he Neumann bounda y condi ion
∂u1
∂n =∂u2
∂n =0 on ∂Ω.
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php

486 BOSCO GARC´
IA-ARCHILLA AND EDRISS S. TITI
0 5 10 15 20
2.5
3
3.5
4
4.5
||
u
||
L
2
Fig. 1.E olu ion o kukL2(Ω)2.
00.5 1
0
0.5
1
1
2
3
4
x
y
u
2
Fig. 2.Componen u2o he solu ion a T=10.
Al hough o simplici y we ha e de eloped he analysis o Di ichele bounda y con-
di ions, ou analysis can be modi ied o co e he Neumann bounda y condi ions case
as well.
We se ν=0.002. We complemen his sys em wi h he ini ial condi ion
u1(x, y, 0)=1−1
4(2y−1)((2y−1)2−3),
u2(x, y, 0)=3−(2x−1)((2x−1)2−3).
The co esponding solu ion becomes nea ly pe iodic in ime, and de elops mode a ely
la ge g adien s. Figu e 1 shows he e olu ion o kukL2(Ω)2up o ime T= 20, and a
pe iodic beha io can be obse ed. In Figu e 2, he componen u2o he solu ion, a
ime T= 10, is po ayed; he g adien akes alues abo e 50 in some poin s o he
domain.
In ou calcula ions we ake he so-called egula pa e n iangula ions o Ω, which
a e induced by he se o nodes (j/N,k/N), 0 ≤j, k ≤N, whe e N=|Ω|/h is an
in ege . Fo he Gale kin me hod (5) we used Lag ange quad a ic elemen s on hese
iangula ions (i.e., = 3) and o he pos p ocessing s ep, since he solu ion u=
(u1,u
2)
Tis smoo h, we choose Lag ange cubic elemen s on he same iangula ions.
Since he Laplacian is nonin e ible when subjec o Neumann bounda y condi-
ions, o he pos p ocessing s ep we sol e
ν˜
Ah˜u1,h +4˜u
1,h =1+ ˜
P
h
(u
2
1,hu2,h)−d
d u1,h,(63)
ν˜
Ah˜u2,h +˜
Ph¡˜u2
1,h ˜u2,h)=3˜u
1,h −d
d u2,h,(64)
sol ing i s (63) (no ice ha ν˜
Ah˜
+4Idis in e ible) and hen (64).
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
POSTPROCESSING FINITE-ELEMENT METHODS 487
Fo he ime in eg a ion, a a iable- o mula, a iable-coe icien implemen a ion
o he backwa d di e en ia ion o mulae (BDF) was used wi h o de s up o six (see,
e.g., [26]). This me hod is widely used in he nume ical in eg a ion o s i o dina y
di e en ial equa ions (ODEs), like hose a ising om he spa ial disc e iza ions o
dissipa i e PDEs. This BDF code was p e iously used in [16],[19], [20]. In [19], his
code is shown o be mo e e icien han o he widely used in eg a o s in dissipa i e
PDEs (including semi-implici me hods). Wi hou an e icien ime in eg a o , as
shown in [19], [20], i may ake an una o dable amoun o compu ing ime o each
he le els o accu acy desc ibed below.
Fo each hused in he iangula ions o Ω, e e y expe imen was ca ied ou wi h
di e en alues o he ole ance TOL (an inpu alue o he ime in eg a o ) below
which local ime disc e iza ion e o s a e desi ed. The smalles e o ob ained was
selec ed o he plo s. The e was always a poin , depending on h, a which u he
educing he ole ance did no educe he e o s any mo e. This means ha he
e o a ising om ime disc e iza ion is much smalle han he e o a ising om he
ini e-elemen spa ial disc e iza ion. When his happens, one can be su e ha he
e o s obse ed a e due only o he spa ial disc e iza ion and do no depend on he
ime in eg a o used. In iew o [19] we we e pa icula ly ca e ul o ensu e ha he
dominan e o in all he compu a ions p esen ed he e was he spa ial disc e iza ion
e o in o de o a oid w ong conclusions om ou nume ical expe imen s. Also, o
he compu a ional cos in Figu es 4–6 below, he la ges ole ance among hose wi h
which he spa ial disc e iza ion e o was dominan was used. We e e o his alue
o he ole ance as he op imal ole ance. A smalle ole ance would esul in a la ge
cos bu no smalle e o . A la ge one, on he o he hand, would imply a la ge e o ,
bu hen he same e o could be ob ained a less cos wi h he same ole ance and
la ge h.
In Figu e 3 we p esen a con e gence diag am showing he e o s commi ed by he
me hods when used wi h h=|Ω|/N ,N=12,24,48. By e o s we mean he di e ence
be ween he app oxima ions (u1,h,u
2,h)o (˜u
1,h,˜u2,h) and he exac solu ion (a he
end o he sec ion we explain how i was ob ained). In his and in he es o he plo s,
he compu a ional esul s o he classical quad a ic elemen s a e joined by con inuous
lines, and hose o he pos p ocessed me hod by discon inuous (dashed) lines. Wi h
his, we ge an idea o wha he esul would ha e been o in e media e alues o h.
I can be seen ha as his dec eased om le o igh , he e o s in bo h me hods
dec ease om op o bo om, bu hey dec ease as e in he pos p ocessed me hod.
Measu es o he slopes o he plo s con i m he a es p edic ed by he heo y (i.e., he
e o s in he plo dec ease like Nslope = cons .h−slope).
The imp o ed con e gence a e o he pos p ocessed me hod obse ed in Figu e
3 also implies imp o ed e iciency. This can be checked in Figu e 4, whe e he same
e o s as in Figu e 3 a e plo ed agains he smalles amoun o CPU ime ha
he me hods needed o achie e hem, ha is, he cos o in eg a ing he me hod
wi h he op imal ole ance (no ice ha , o a gi en h, he op imal ole ance o he
pos p ocessed quad a ics is, in gene al, smalle han ha o he quad a ics). The
eason o his imp o emen is ha he e o o he Gale kin me hod is educed when
he pos p ocessing is done, bu his is done a e y li le cos (less han 10% o
he whole compu a ion, including he ex a cos o in eg a ing in ime wi h smalle
ole ances). In ac , he cos o he pos p ocessing s ep is equi alen o he cos o
oughly 10 ime s eps, and he numbe o ime s eps in he esul s shown in Figu e 4
a ies be ween 109 and 344.
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
488 BOSCO GARC´
IA-ARCHILLA AND EDRISS S. TITI
101102
105
104
103
102
N=|Ω|/h
L2 ela i e e o s
B ussela o wi h nu=0.002: T=10
slope=3.0563
slope=3.8084
Quad a ics
Pos p ocessed
Quad a ics
N=48
N=12
Fig. 3.Con e gence diag am.
101102103
105
104
103
102
CPU ime
L2 ela i e e o s
B ussela o wi h nu=0.002: T=10
Quad a ics
Pos p ocessed Quad a ics
N=48
N=24
N=12
Fig. 4.E iciency diag am.
The pos p ocessed quad a ic elemen s a e no only mo e e icien han he classical
quad a ics bu also mo e e icien han he classical cubic elemen s, which ha e he
same con e gence a e as he pos p ocessed quad a ics. In Figu e 5 we ha e plo ed,
besides he esul s o Figu e 4, hose o he classical cubic elemen s, ha is, he
s anda d Gale kin me hod (5)–(6) bu wi h = 4. These a e ep esen ed by as e isks
joined by do ed lines. No ice how he discon inuous line (pos p ocessed me hod) is
always on he le (less CPU ime) o he do ed line o he cubics. In his example,
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
POSTPROCESSING FINITE-ELEMENT METHODS 489
101102103
105
104
103
102
CPU ime
L2 ela i e e o s
B ussela o wi h nu=0.002: T=10
Quad a ics
Pos p ocessed
Quad a ics
Cubics
N=6
N=12
N=12
N=24
N=48
N=48
N=48
Fig. 5.E iciency diag am.
101102103
104
103
102
101B ussela o wi h nu=0.002: T=10
L∞ ela i e e o s
CPU ime
Cubics
Pos p ocessed
Quad a ics
N=6
N=12
N=12
N=24
N=24
N=48
N=48
Fig. 6.E iciency diag am in L∞.
he pos p ocessed quad a ics sa e be ween 15% and 17% o he cos o he cubics.
Mo e signi ican is he gain in he maximum no m in Figu e 6, whe e he pos p ocessed
quad a ics equi e be ween 21% and 25% less compu ing ime han he classical cubics.
A signi ican de ail can be obse ed in Figu es 5 and 6: The pos p ocessed me hod
is mo e e icien han classical me hods o qui e la ge e o s (al eady abo e 10−3).
This is in con as o ou p e ious expe ience wi h spec al me hods, whe e, ypically,
pos p ocessing b ings a subs an ial imp o emen only o qui e small e o s (below
10−5) [16], [21].
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
490 BOSCO GARC´
IA-ARCHILLA AND EDRISS S. TITI
0 2 4 6 8 10
0
5
10
15
i e a ions
CPU ime = 1082 s
CPU ime = 739 s
CPU ime = 780 s
Fig. 7.E olu ion o PCG i e a ions o h=√2/48 and TOL =0.001: −·−MAXIPCG =8,−−
MAXIPCG =11,−− MAXIPCG = 18818.
We end his sec ion by commen ing on he mo e ele an de ails o he me hods
used. Recall ha he ime in eg a ion is done wi h he BDF. Since hese a e ully
implici me hods, hen, a e e y ime s ep, a sys em o nonlinea equa ions o he
o m
α h+(δ )(νAh h+PhF( h))=0,(65)
has o be sol ed, whe e δ is he ime s epleng h. This was done by New on i e a ion.
The exac Jacobian ma ices we e eplaced by he Jacobian ma ix o he linea e ms,
ha is,
αMh+(δ )νSh,(66)
whe e Mhand Sha e he mass and s i ness ma ices (see, e.g., [45]).
The co esponding linea sys ems we e sol ed by he p econdi ioned conjuga e
g adien me hod (PCG) wi h incomple e Cholesky (ICH) ac o iza ion o (66) as
p econdi ione (see, e.g., [23]). Bo h PCG and ICH algo i hms we e aken om
he SLAP lib a y. A single ICH ac o iza ion o (66) p o ed o be ex emely cos ly
(be ween 5% o 10% o he whole compu a ion om =0 oT= 10). Thus,
i was compu ed a he i s s ep and eused in la e s eps un il he PCG did no
con e ge, when i was ecalcula ed again. By con e gence in he PCG me hod we
mean achie ing a ela i e e o below a p esc ibed alue TOLPCG in less han a ixed
numbe o i e a ions MAXIPCG.
In ou p esen case, we chose TOLPCG =10
−3 o he linea sys ems in he New on
i e a ion o (65), and 10−9 o hose in he pos p ocessing (63)–(64). To se he alue
o MAXIPCG, we pe o med a p ac ical s udy o a ious alues o hand se le i o
MAXIPCG = 11, which usually o ced he compu a ion o wo ICH decomposi ions. In
Figu e 7, he numbe o PCG i e a ions ( he maximum o he wo o h ee linea
sys ems sol ed pe s ep) o di e en alues o MAXIPCG a e shown, oge he wi h he
CPU imes o he co esponding uns. I can be seen how i MAXIPCG is gene ous
(dashed line) he code compu es only one ICH ac o iza ion a = 0 bu in he end
pe o ms a c ippling numbe o i e a ions. I MAXIPCG is oo igh (dash-do ed line)
he second ICH decomposi ion is compu ed oo soon, a =1.6662; he numbe o
PCG i e a ions is d as ically educed om hen onwa d, bu he o e all numbe o
i e a ions (and hence he cos ) is la ge han o MAXIPCG = 11 (con inuous line).
No ice how in his las case, he numbe o i e a ions is d as ically educed a =
2.5005 when he second ICH ac o iza ion is compu ed, and emains he lowes om
hen onwa d.
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php

POSTPROCESSING FINITE-ELEMENT METHODS 491
Fo he linea sys ems in he pos p ocessing s ep (63)–(64), i p o ed a mo e
e ec i e o use he diagonal o he co esponding ma ices as a p econdi ione . A a
g ea e numbe o PCG i e a ions we e aken (in he example o Figu e 7, 70 o ˜u1,h
and 308 o ˜u2,h o sys ems o 21025 unknowns), bu i compensa ed o he cos o
a new ICH ac o iza ion (no ice ha he ma ices in he pos p ocessing s ep a e o
la ge dimension han hose in (66)).
The ini ial guess o New on’s me hod in (65) was compu ed by s anda d ech-
niques o ex apola ion in he BDF code (see, e.g., [26]), and o he PCG me hod
in he co esponding linea sys ems he ini ial i e a es we e se o 0 (no ice ha he
solu ions o his sys ems a e he inc emen s o New on i e a ions ha a e supposed
o be small). Fo he linea sys em in he pos p ocessing s ep (63)–(64), he ini ial
guess was he Gale kin app oxima ion uhexp essed in he nodal basis o he cubic
elemen s.
I may be asked i o he linea algeb a echniques would ha e changed he esul s
shown he e. This would be especially he case i a as e (i exis ing) linea algeb a
would ha e a o ed he cubic elemen s bu no he quad a ics (and hence, nei he
he pos p ocessed me hod), al hough i is di icul o de ise why i should be so.
Ob iously, i is ou o he scope o his pape o es all possible linea sys em sol e s,
especially when he e does no seem o be a clea -cu c i e ion o when o apply
he many exis ing echniques compe ing o a en ion. The PCG used he e seems o
us a e y easonable choice, especially i we ake in o accoun he e y low numbe
o i e a ions ha i ook o sol e he sys ems in ou examples ( ecall Figu e 7).
Fu he mo e, a signi ican imp o emen could ha e been made o he pos p ocessing
s ep wi h mul ile el echniques (see, e.g., [4]), which would ha e a o ed ye u he
he pos p ocessed Gale kin me hod. We es ed di ec (spa se) sol e s, bu hey we e
ema kably mo e cos ly han he PCG. We also checked ha explici ime in eg a o s
we e much less e icien han he BDF (i.e., he sys em o ODEs (5) is genuinely s i ).
In all he esul s shown he e, he ini ial condi ion (6) was eplaced by he in e -
polan Ih(u0), which is much cheape o compu e han he ellip ic p ojec ion in (6).
We also pe o med he expe imen s wi h (6), and obse ed ha he di e ences wi h
hose shown he e we e insigni ican .
The heo e ical (“exac ”) solu ion uwas compu ed wi h cubic elemen s and
h=√2/96, using alues o he ole ance anging om 10−9 o 10−12, so ha he
compu ed solu ion aken as exac is easonably mo e accu a e han hose shown in
he expe imen s.
All expe imen s we e ca ied ou on a SUN Ul a-1, Mod. 140 wo ks a ion wi h
64 MB RAM, unde Sola is 2.5.1. All p og ams we e w i en in FORTRAN, used
double p ecision a i hme ic, and we e compiled wi h he Spa cWo ks 4.0 compile
wi h he - as op ion.
4. L∞analysis.
4.1. P elimina ies and main esul . In compa ison o sec ion 2, we u he
es ic ou sel es he e in he ollowing sense.
1. The esul s he e apply only o eac ion-di usion equa ions wi h nonlinea
e ms as in (3).
2. We conside only p oblems in Rd, wi h d=2,3.
(As wi h he L2analysis, he case d= 1 is pa icula and easie o s udy).
The e o es ima es in his sec ion depend on
K∞(u, )=ku(·, )kW ,∞(Ω) +ku (·, )kW ,∞(Ω) ,K
∞
(u) = max
0≤ ≤TK∞(u, ).(67)
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
492 BOSCO GARC´
IA-ARCHILLA AND EDRISS S. TITI
Unde hese condi ions, he e o bounds o he pos p ocessed Gale kin me hod
a e s a ed in he ollowing heo em whose p oo is gi en in sec ion 4.3.
Theo em 3. The e exis cons an s C=C(K∞(u)) >0and h0>0such ha o
e e y h∈(0,h
0] he solu ion ˜uo (7) sa is ies he ollowing bound:
ku−˜ukL∞(Ω) ≤Ch +2−d/2|log(h)|4−d/2i =3.(68)
ku−˜ukL∞(Ω) ≤Ch +2 |log(h)|3i ≥4.(69)
We now s a e he equi alen o (17)–(18) in he L∞no m. Ins ead o (17) we
ha e
ku− hkL∞(Ω) +hku− hkW1,∞(Ω∩Ωh)≤ChlkukWl,∞(Ω) ,1≤l≤ .(70)
This es ima e ollows om Theo em 5.1 in [39], (15), and (13). We a e unawa e o an
es ima e like (18) in L∞, al hough simila esul s in Lpcan be ound in he li e a u e.
Thus, we p o e he ollowing esul .
Lemma 7. Assume ha d≥2, ≥3,and δ(h)=O(h
min( +2,2( −1))). Then he e
exis s a cons an C>0such ha o ∈W ,∞(Ω) he ollowing bound holds:
°
°A−1( −Rh )°
°L∞(Ω) ≤Ck kW ,∞(Ω) hmin( +2,2( −1)) |log(h)|.(71)
P oo . Following [39], we ake χh=Ih¡A−1(I−Rh) ) he in e polan o A−1(I−
Rh) . Then
°
°A−1(I−Rh) °
°L∞(Ω) ≤°
°A−1(I−Rh) −χh°
°L∞(Ω) +kχhkL∞(Ω) .
Le us ake pwi h 2 ≤p≤∞. Fo he i s e m on he igh -hand side abo e we
ha e ha (c . [6, Thm. 3.1.6])
°
°A−1(I−Rh) −χh°
°L∞(Ω) ≤Ch2−d/p°
°A−1(I−Rh) °
°W2,p(Ω).
Le us ecall he ollowing inequali y (see, e.g., [39] and [49]) which, o linea ellip ic
equa ions, illus a es he a e a which he Agmon–Douglis–Ni enbe g egula i y and
well-posedness es ima e [2] de e io a es as p→∞. Namely, he e exis s a cons an
C>0, which is independen o p, such ha
°
°A−1w°
°W2,p(Ω) ≤CpkwkLp(Ω) ,2≤p<∞.(72)
Thus, i ollows ha
°
°A−1(I−Rh) −χh°
°L∞(Ω) ≤Cph2−d/p k(I−Rh) kLp(Ω)
≤Cph +2−d/p k kW ,p (Ω) .
Using (13) we ha e ha kχhkL∞(Ω) ≤Ch−d/pkχhkLp(Ω), and hus
kχhkL∞(Ω) ≤Ch−d/p°
°χh−A−1(I−Rh) °
°Lp(Ω) +°
°A−1(I−Rh) °
°Lp(Ω).(73)
In iew o he in e pola ion e o bound (15), (70) and (72) we ob ain he ollowing
es ima e o he i s e m on he igh -hand side o (73):
Ch−d/p°
°χh−A−1(I−Rh) °
°Lp(Ω) ≤Cph +2−d/p k kW ,p (Ω) .
Also, i is well known (see, e.g., [40, Example 3.2]) ha
Ch−d/p°
°A−1(I−Rh) °
°Lp(Ω) ≤Cphmin( +2,2( −1))−d/p k kW ,p (Ω) ,(74)
wi h Cindependen o pand h. Taking p=|log(h)|, (71) ollows easily.
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
POSTPROCESSING FINITE-ELEMENT METHODS 493
4.2. L∞analysis o he Gale kin me hod. The ollowing esol en es ima e,
which is due o Palencia [38], will be needed la e o ou L∞e o es ima es.
Lemma 8. Fix α∈(0,π/2) and h0∈(0,e
−1].Le β(h)deno e β(h)=k(P
h−
R
h
)A
−1
k
∞(= O(h2|log(h)|)).Then he e exis posi i e cons an s C∞and σ<1)
such ha he bounds
°
°(zI −Ah)−1°
°∞≤C∞|z|−1i |z|≤σβ(h)−1,
C∞h−d/2|z|−1i |z|≥0
hold o z∈Cwi h π≥|a g(z)|≥αand o 0<h≤h
0
.
Taking o example a=(d+3)/(2σcos(α)), i easily ollows ha he e exis s a
cons an C0>0 such ha o hsu icien ly small
°
°e− Ahχh°
°L∞(Ωh)≤C0kχhkL∞(Ωh),χ
h
∈S
h
, ≥
0
=aβ(h)|log(h)|.(75)
We will also use he ollowing bound om Ni sche and Wheele [36],
°
°e− Ahχh°
°L∞(Ωh)≤C1kχhkL∞(Ωh),χ
h
∈S
h
, ≥0, ≥4.(76)
The lack o a bound like (76) ∀ ≥0, i = 3, is he eason ha he con e gence a e
depends also on he dimension d. This will be seen in Lemma 11 below.
Lemma 9. Fix c h >0and T>0. Then he e exis s a cons an S>0such ha
o h:[0,T]→S
h, sa is ying h(0) = h(0) and he h eshold condi ion
k h( )− h( )kL∞(Ωh)≤c h,(77)
o ∈[0,
1]whe e 1≤T, he ollowing bound holds o hsu icien ly small:
max
0≤ ≤ 1k h( )− h( )kL∞(Ωh)≤Smax
0≤ ≤ 1°
°
°
°Z
0
e−ν( −s)Ah(ˆ
Th(s)−Th(s)) ds.°
°
°
°L∞(Ωh)
,
(78)
whe e ˆ
Tis as in (35).
P oo . We no ice ha he h eshold condi ion (77) and he ac ha Rhis bounded
ensu es ha bo h k hkL∞(Ω) and k hkL∞(Ω) a e bounded by some cons an C=
C(c h,max0≤ ≤Tku( )kL∞(Ω)). Since Fis smoo h, i ollows ha
kF( h)−F( h)kL∞(Ωh)≤Ck h− hkL∞(Ωh).(79)
Now ake no ms in (36). Fo ≥4, hanks o (76), he ac ha Phis bounded in
L∞( ecall (20)) and (79) abo e, s anda d a gumen s wi h he G onwall lemma lead
o (78).
Fo = 3, simila a gumen s (wi h a gene alized G onwall lemma as in Lemma
2) will also lead o (78) as long as we p o e
°
°
°
°Z
0
e−ν( −s)AhPh(F( h)−F( h)) ds°
°
°
°L∞(Ωh)≤CZ
0
k h(s)− h(s)kL∞(Ωh)
( −s)γds,
(80)
o some C>0 and γ<1. To do his, we conside he alue 0in (75) and le us call
= max(0, −
0/ν), so ha o s∈[0, ], ν( −s)≥ 0. Then, hanks o (75), (79),
and he ac ha Phis bounded, we ha e ha
°
°
°
°Z
e−ν( −s)AhPh(F( h)−F( h)) ds°
°
°
°L∞(Ωh)≤CZ
k h(s)− h(s)kL∞(Ωh)ds.
(81)
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
494 BOSCO GARC´
IA-ARCHILLA AND EDRISS S. TITI
On he o he hand, ake p=dand κ=d/2−1 so ha 1/p =1/2−κ/d. Then, o
s∈[ , ] and wh∈Sh, , hanks o he in e se es ima e (13) and Sobole ’s lemma, we
ha e ha
°
°
°e−ν( −s)Ahwh°
°
°L∞(Ωh)≤C
h°
°
°e−ν( −s)Ahwh°
°
°Lp(Ωh)≤C
h°
°
°e−ν( −s)Ahwh°
°
°Hκ(Ωh)
≤C
h°
°
°e−ν( −s)Ahwh°
°
°
1−κ
L2(Ωh)°
°
°A1/2
he−ν( −s)Ahwh°
°
°
κ
L2(Ωh)
≤C
h¡ν( −s)κ/2kwhkL2(Ωh).(82)
Now obse e ha o s∈[ , ], since ν( −s)≤ 0≤Ch3/2, i ollows ha h−1≤
C(ν( −s)−2/3). Thus, aking in o accoun ha
κ
2+2
3=d
4−1
2+2
3=d
4+1
6≤3
4+1
6=11
12 =γ<1,
we ha e ha
°
°
°e−ν( −s)Ahwh°
°
°L∞(Ωh)≤C
¡ν( −s)11
12 kwhkL2(Ωh)≤C|Ωh|1/2
¡ν( −s)11
12 kwhkL∞(Ωh).
This ( eplacing whby Ph(F( h)−F( h))) oge he wi h (79) and (81) leads o (80)wi h
γ=11/12.
Ha ing es ablished s abili y in he p e ious lemma, we now ace he ask o es i-
ma ing he igh -hand side o (78) when h=uh. Recall ha in he L2case, his was
s aigh o wa d hanks o he e y a o able L2-bounds o Ahe−µ( −s)Ah, which can
be ob ained by means o he spec um o Ah. In he p esen case, i.e., he L∞case,
he lack o such bounds o e−µ( −s)Ah(le alone Ahe−µ( −s)Ah) makes he ask much
ha de . Since he di icul y lies when −sis small ( ecall o example he es ic ion
in (75)), we will decompose he in eg als in (78) in o wo pa s co esponding o −s
la ge (Lemma 10 below) and small (Lemma 11 below).
Lemma 10. Fix α∈(0,π/2),le σand β(h)be as in Lemma 8, and se τ1=
dβ(h)|log(h)|/(2νσcos(α)).Then he e exis s a cons an C>0such ha o ≥τ1
he ollowing bound holds o hsu icien ly small:
°
°
°
°Z −τ1
0
eν( −s)AhTh(s)ds°
°
°
°L∞(Ωh)≤C
ν
log 
h
max
0≤s≤ −τ1°
°A−1
hTh(s)°
°L∞(Ωh).(83)
P oo . By w i ing eν( −s)AhTh(s)=A
h
e
ν( −s)A
hA
−1
hT
h
(s), we only need o bound
Aheν( −s)Ah. Le Γ be he bounda y o he sec o {z||a g(z)|≤α}, endowed wi h
he posi i e o ien a ion. Then
Ahe−ν( −s)Ah=1
2πi ZΓ
ze−ν( −s)z(zI −Ah)−1dz.
We ake ρ1=σβ(h)−1, and di ide Γ in he wo pa s Γ ∩{|z|≤ρ
1
}and he wo
hal -lines Γ ∩{|z|≥ρ
1
}. Taking in o accoun he esol en es ima e in Lemma 8, we
can w i e
°
°Ahe−ν( −s)Ah°
°∞≤2C∞Zρ1
0
e−ν( −s) cos(α)ρdρ +2C
∞
h
d/2Z∞
ρ1
e−ν( −s) cos(α)ρdρ,
Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php