An efficient two-dimensional Vortex method with long time accuracy

SIAM J. NUMER. ANAL. Vol. 33, No. 4, pp. 1425-1450, Augus 1996 () 1996 Socie y o Indus ial and Applied Ma hema ics 008 AN EFFICIENT TWO-DIMENSIONAL VORTEX METHOD WITH LONG TIME ACCURACY* IBRAHIM BLESS RANERO AND TOM/S CHAC(3N REBOLLO Abs ac . This pape deals wi h e icien echniques o he nume ical solu ion o wo-dimensional ee-space incomp essible Eule equa ions. We de elop an algo i hm o as compu a ion o eloci y in a o ex me hod based upon disc e iza ion o o ici y by ini e elemen s. We p o e ha he me hod wi h as compu a ion o eloci y is nume ically s able and con e gen wi h second-o de accu acy. Some s anda d nume ical es s show ha he algo i hm wi h Delaunay eg idding bea s good s abili y and accu acy p ope ies o long in eg a ion imes, wi h a ela i ely low compu a ional cos . Mo eo e , he algo i hm is ound o be mo e accu a e han high-o de o ex-blob me hods wi h eg idding o long enough in eg a ion imes. Key wo ds, o ex me hods, ini e elemen s, Delaunay eg idding, long ime accu acy AMS subjec classi ica ion. 65N30 1. In oduc ion. This pape deals wi h he nume ical solu ion o wo-dimensional ee- space incomp essible Eule equa ions by means o o ex me hods wi h ini e elemen s. Lag angian me hods, and in pa icula o ex me hods, ha e many a o able p ac ical p ope ies o he nume ical simula ion o incomp essible lows a a high Reynolds numbe (c . Leona d 18], Majda 19] o a de ailed bibliog aphy and Ande son 1 o lows in bounded domains). Vo ex me hods essen ially in oduce no nume ical iscosi y and a e qui e accu a e and s able, a leas o sho imes (c . Beale and Majda [5], Pe lman [20]). A comple e heo y o s abili y and con e gence o o ex me hods o ee-space wo- and h ee-dimensional Eule equa ions has been de eloped since he la e se en ies. In Ande son and G eenga d [2] and Beale and Majda [3], [4] an analysis o con e gence in/P-no ms, wi h ini e p, may be ound. La ely, a heo y o con e gence in/-no ms was de eloped, mos ly by Hou and his collabo a o s (c . Hou and Loweng ub [16], Hou [14], Hou [15]). Those wo ks p o e ha o ex me hods a e essen ially s able in p- and/-no ms, bu s abili y is condi ioned o a ela i ely high o de o consis ence. Such "condi ioned s abili y" appea s in all con e gence p oo s o o ex me hods, as essen ially ela ed o he singula i y o he B io -Sa a ke nel. In p ac ice, o ex me hods compu e qui e accu a e solu ions o Eule equa ions o ela- i ely sho in eg a ion imes. Beale and Majda [5] and Pe lman [20] ha e es ed o ex-blob algo i hms wi h high-o de ke nels. Those expe imen s con i m he heo e ical p edic ions o o de o con e gence o mode a e imes; howe e , a la e imes he high-o de accu acy p og essi ely de e io a es. This seems o be due o he p og essi e inc ease o local g id size ha , in gene al, akes place as he ini ial g id is de o med by he low. This leads o an inc eas- ing loss o accu acy in he compu a ion o eloci ies. As s abili y is condi ioned o enough accu acy, a p og essi e loss o s abili y also occu s. Beale and Majda conclude ha o ob ain accu a e solu ions o long in eg a ion imes, eg idding echniques a e usually needed. In oducing eg idding echniques dec eases he local g id size and allows s abili y and accu acy o longe imes. Un o una ely, his in oduces inc easing le els o nume ical di usion, coun e balancing he main ea u e o o ex me hods. Ou pu pose he e is essen ially o de elop a o ex me hod in which i is possible o educe he local g id size wi hou in oducing nume ical di usion a he g id nodes. Ou *Recei ed by he edi o s May 19, 1993; accep ed o publica ion (in e ised o m) Sep embe 28, 1994. This esea ch was pa ially suppo ed by Spanish M. E. C. P ojec DGICYT PB91-0619. Depa amen o de Ma emi ica Aplicada, Uni e sidad Complu ense de Mad id, A da. de la Complu ense, s/n. 20840 Mad id, Spain ([email p o ec ed]). Depa amen o de Ecuaciones Di e enciales y Amilisis Num6 ico, Uni e sidad de Se illa, C/Ta ia, s/n. 41080 Se illa, Spain ([email p o ec ed]). 1425 1426 IBRAHIM BLESS RANERO AND TOM/S CHACON REBOLLO wo k is based upon a o ex me hod in oduced in Chacon and Hou 10]. In his me hod he o ici y is disc e ized by means o piecewise linea ini e elemen s. Also, he mesh poin s o he ini ial iangula ion a e anspo ed along he s eamlines o he disc e e low. Thus, he o ici y is accu a ely compu ed a he mesh poin s, since he o ici y is conse ed along s eamlines. This me hod sha es many nice p ope ies o o ex me hods, being in pa icula nondissipa i e. The me hod is p o ed o be s able and con e gen wi h second-o de accu acy in he uni o m no m. Howe e , he s abili y is condi ioned o an o de o accu acy bigge han one, much as in classical o ex me hods. Nume ical expe imen s show ha o sho in eg a ion imes his me hod is qui e accu a e, bu ha as ime inc eases, he iangula ions gene ally become degene a ed. This p oduces a as loss o accu acy in a sho ime a e degene a ion. On he o he hand, he me hod uses a echnique o compu a ion o disc e e eloci ies ha equi es an amoun o ope a ions o o de O (N2), N being he numbe o g id nodes in he suppo o he o ici y. These wo d awbacks make he me hod un easible in p ac ical cases. This pape epo s some modi ica ions o his me hod ha ende i accu a e o e y long imes, wi h a ela i ely low compu a ional cos . A i s , we de elop a as echnique o compu e he disc e e eloci y in he Chacon-Hou algo i hm. This is an adap a ion o he echnique in oduced in G eenga d and Rokhlin 12] o ou con ex o disc e iza ion o o ici y by ini e elemen s. This educes he amoun o compu a ional wo k equi ed by he me hod o O(N log 2 N). We p o e an es ima e o e o , in e ms o he uni o m no m o he o ici y, o he compu a ion o disc e e eloci ies by his echnique. Fu he mo e, we p o e ha i in he Chacon-Hou algo i hm he eloci y is compu ed by his echnique wi h enough accu acy, he nume ical solu ion is s ill con e gen in he uni o m no m wi h second-o de accu acy. The p oo deals essen ially wi h he ac ha ou algo i hm keeps cons an he uni o m no m o he disc e e o ici y. This allows us o ob ain uni o m- in- ime es ima es o he e o in he compu a ion o he eloci ies wi h he as algo i hm and ensu e he s abili y o he algo i hm. We also p o e ha i Delaunay eg idding is in oduced, he algo i hm wi h as compu a- ion o eloci y is s ill con e gen wi h second-o de accu acy. Delaunay eg idding cons uc s he iangula ion ha maximizes he smalles angle o all possible iangula ions suppo ed by a gi en cloud o poin s. In oducing his eg idding echnique in ou me hod p oduces he only e ec o ede ining he connec ions be ween g id poin s. The alues o he disc e e o ici y a he g id poin s emain unchanged. Thus, he local g id size is educed, wi hou in oducing nume ical di usion. The algo i hm is con e gen independen o he ac ual ime-s epping s a egy used o apply Delaunay eg idding. We inally epo some nume ical expe imen s dealing wi h es cases conside ed by Beale and Majda. We con i m ou heo e ical expec a ions on he numbe o ope a ions in he compu a ion o disc e e eloci ies. We also pe o m some es s o he modi ied Chacon- Hou algo i hm, in oducing Delaunay eg idding. These es s show excellen p ope ies o s abili y and accu acy, o e y long ime in e als, in he es cases conside ed. The e o s a e conse ed close o he ini ial alues, and he heo e ical con e gence o de s a e con i med nume ically, e en o long in eg a ion imes. We also obse e ha his algo i hm compa es ad an ageously o a desingula ized o ex me hod o he same o de , and also o high-o de o ex-blob me hods wi h eg idding o long enough imes o in eg a ion. Ou pape is o ganized as ollows. In 2, we desc ibe he algo i hm epo ed in Chacon and Hou 10]. In 3 we de elop he echnique o as compu a ion o eloci ies. Sec ion 4 is de o ed o he analysis o he con e gence o he modi ied Chacon-Hou algo i hm. Finally, in 5 we epo ou nume ical es s. LONG TIME ACCURATE VORTEX METHOD 1427 2. Desc ip ion o he base algo i hm. In his sec ion we shall desc ibe he o ex me hod wi h ini e elemen s in oduced in Chacon and Hou 10], as some ele an p ope ies o his me hod mo i a e ou wo k. We a e in e es ed in he nume ical solu ion o ee-space Eule equa ions in wo space dimensions, wi h a homogeneous condi ion a in ini y. In o ici y (co)-s eam unc ion (q) o mula ion, hese equa ions a e CO -[- (U V)co 0 in Rex]0, T[, co(x, 0) co0(x) in R e, (1) -Aq co inR 2, lim q(x) 0. He e, u (u l, u2) is he eloci y ield, de ined by he wo-dimensional Bio -Sa a law, (2) u(x, ) (K co)(x) [ K(x y) co(y, ) dy, whe e K is he B io -Sa a ke nel, (3) g(x) 2z lxl 2 (-x2, Xl). Equa ions (1) a e equi alen o he usual o mula ion o Eule equa ions (c . Ande son and G eenga d [2], Ka o [1 ]). The equa ion o he o ici y in (1) may be in eg a ed exac ly on he s eamlines X ( ; s, associa ed o he eloci y ield u. The cu e 6 [0, T] --+ X ( ; s, o ) 6 R 2 desc ibes he ajec o y o a luid pa icle whose posi ion a ime s is he poin o 6 R 2. I sa is ies he ollowing o dina y di e en ial equa ion: -d--( ; s, o ) u(X( ; s, ), ) in [0, T], (4) X(s; ,) =. Then, (5) co(X ( ; s, o ), ) co(o , s) ’ o R 2 and V s, in [0, T]. Chacon and Hou show ha i co is app oxima ed by a piecewise polynomial unc ion on polygons, hen he co esponding eloci y gi en by (2) may be compu ed analy ically. This, oge he wi h (5), sugges s ha we app oxima e he o ici y by ini e elemen s on a mo ing g id whose nodes desc ibe s eamlines o he low. The algo i hm o Chacon and Hou is based upon his idea. Al hough i s desc ip ion needs a he complex no a ion, we shall p o ide i as needed h oughou his pape . Conside a iangula ion Th o R 2 wi h iangles {727}i u and nodes {Olj}j6 u. We shall assume ha h deno es he leng h o he longes side o all iangles o Th. Deno e by Vh he space o con inuous piecewise a ine ini e elemen s on iangula ion Th, de ined by (6) Vh Vh C 0 (RZ) hl is a ine o all iangles 6 Th }. A unc ion Vh Vh is uniquely de e mined by he alues Vh (o j) ’i iV. 1428 IBRAHIM BLESS RANERO AND TOM/S CHACON REBOLLO Assume ha we know an app oxima ion Xj o he poin X ( n; 0, o j) o each j 6 N. De ine he app oxima e unc ion X 6 Vh o he low map X ( ; 0, .), espec i ely, in such a way ha i e i ies ^n ’j 6N. (c s) x ^n Then, 7 { i ( /) ’4 / Th} de ines a iangula ion o R e, p o ided he iangles do no o e lap. I his is he case, we also de ine he piecewise a ine ini e elemen space Q on iangula ion 7 in he same way ha Vh is de ined on Th in (6). We shall deno e by/3 (x; {coj }) he canonical in e pola ion ope a o on P, de ined by We shall also deno e by di)j }jEN he canonical base o V h Each (Ioj is uniquely de ined by i j k, j(O k)-- 0 i jCk. We a e now eady o s a e he Chacon-Hou algo i hm. ALGORITHM A. Suppose ha coo is o compac suppo . Deno e wj co0(o j). 1. Ini ializa ion (i) T iangula ion; (ii) Vo ici y; (iii) Veloci y; ^0 X =o j and T=Th. 2. Time i e a ion (i) Upda e Lag angian mesh poin s by he second-o de Adams-Bash o h me hod, ^n+l "n A [ ^n(]) ^n-l( y-1 ] Xj Xj -- - 3 l, h --l, h (ii) Cons uc a piecewise linea app oxima ion o X ( ; 0, .), ^n+l j n+l Z Xj jEN (iii) Upda e o ici y; ()+1 (X) /3+1 (X, {O)j }). (i ) Upda e eloci y; ^n+l +1 u h =K*d Algo i hm A may be iewed as a o ex-blob me hod wi h a cu o unc ion a ying in space and ime and nono e lapping smoo hing pa ame e 3 h. Thus, Algo i hm A sha es wi h LONG TIME ACCURATE VORTEX METHOD 1429 o ex me hods he p ope y o being nondissipa i e. Fu he mo e, i is con e gen wi hou o e lapping he smoo hing "blobs." Chacon and Hou p o e ha Algo i hm A is con e gen in he uni o m no m wi h second- o de accu acy unde some egula i y p ope ies o he amily o ini ial iangula ions. Accu- acy o o de highe han one appea s o be c ucial o ensu e he s abili y o he me hod. Some nume ical es s show ha his me hod is accu a e only o ela i ely sho ime in e als, much as a e o ex-blob me hods (see Pe lman [20]). Howe e , a la e imes he iangula ions become degene a ed and accu acy is p og essi ely los in a sho ime. Thus, eg idding echniques a e needed o inc ease he in e al o accu acy o he me hod. Chacon and Hou p o e ha he me hod is con e gen o longe ime in e als i some speci ic eg idding echniques a e in oduced. This occu s in pa icula i he g id nodes a e eg ouped o o m new iangula ions, so ha hei egula i y is conse ed. 3. Fas compu a ion o disc e e eloci ies. The me hod o compu a ion o disc e e e- loci ies in oduced by Chacon and Hou equi es compu a ions o o de O(Ne), whe e N is he numbe o g id poin s in he suppo o w h." o This makes he algo i hm slow e en o mode - a ely la ge g id sizes. In his sec ion we de elop an adap a ion o he algo i hm in oduced in G eenga d and Rokhlin [12] (c . also G eenga d [13]) ha compu es an app oxima ion o he disc e e eloci ies by means o Taylo expansions. This educes he compu a ional complexi y o O (N log e N). We omi mos o he p oo s o he esul s p esen ed in his sec ion, as hey a e adap a ions o he co esponding ones gi en by G eenga d and Rokhlin. Le Th be a ian- gula ion o R e wi h nodes {o j }jsN. We assume a ce ain uni o mi y in he spa ial dis ibu ion o he g id nodes o Th. This is needed o ensu e he con e gence o he in e pola ion by ini e elemen s (c . Cia le 11 ]). We a e gi en a o ici y oh Vh, whe e Vh deno es he space o piecewise a ine elemen s on Th de ined in (6). Mo eo e , we assume ha h has compac suppo . 3.1. T unca ed expansions. Ou i s goal is o ob ain a unca ed Lau en expansion ha app oxima es he a - ield eloci y induced by he o ici y suppo ed by a gi en subse Q o R 2. This o ici y is gi en by (7) &Q (i (I)i. o i a De ine he se Qh-- {x R2 / d(x’ Q)-- in lx- yl <-h } Then, supp ()Q may include Q, bu in any case supp OQ C Qh. Deno e by/Q (b/l, b/2) he eloci y induced by &O" K(x x’) OQ(X’) IQ(X) Jsu PP Q Then, H ul iu2 is a unc ion o complex a iables, analy ic in C supp &a, as he eal and imagina y pa s o H sa is y he Cauchy-Riemann condi ions in C supp &a. Mo eo e , (8) /(Z) pp Q Z- Z Q(x )dx ’ whe e Z Xl "3 " ix2, Z X X -q- lX2, (X l X2). 1430 IBRAHIM BLESS RANERO AND TOMAS CHACON REBOLLO This allows us o expand//in a Lau en se ies as ollows. THEOREM 3.1. Assume supp _Oa ( D(zo, ), whe e D(zo, ) deno es he complex disc o cen e zo and adius > O. Then, (9) 5/(z) (Z Z0) k+l V z C D(Zo, ), k=0 whe e (10) 1 su (z’ zo)koQ(X ’) dx’. ak / PP Q Mo eo e , gi en p > 1, le us deno e by L p (z) he p- e m unca ed expansion (9). Then, he ollowing e o es ima e holds: (11) I(z) -p(z)l _< Iz zol- Iz z01 i Iz z0l > , whe e 1 Ial. (12) A --- PP a The coe icien s a gi en by (11) may be compu ed analy ically by means o a complex e sion o G een’s heo em. Indeed, as supp (Q is a eunion o iangles o Th, o each such iangle he e exis b , c , and d such ha 1_ 1 ()QI (371’ 372) b xl -b c x2 q- d P Z + P q- d , whe e p = b + c . Thus, 1 C supp 5 Q z (z zo) g z dz + - p (z zo) dz + d (z zo) k dz The men ioned complex e sion o G een’s o mula is used o compu e he in eg als in (3.1). I is s a ed as ollows. LEMMA 3.2. Le B be a bounded measu able subse o R 2 wi h Lipschi z bounda y 0 B. Le and g be wo unc ions o complex alues de ined and analy ic in some open se con aining B U 0 B. Then, 1 (z) g(z) dz. ’z gz dz Le us now conside a iangle Th included in supp ()Q. By aking (z) z, e,(z) (z zo) z, we ob ain 1 ) (z zo) z dz z (z zo dz. LONG TIME ACCURATE VORTEX METHOD 1431 Also, by aking Z 2 (z) g(z) (z Zo) 2’ o2 (z zo) z z (z zo) clz. A simila choice allows us o ind he las e m in (3.1). Finally, he compu a ion o he coe icien s a educes o ha o polynomials on segmen s o s aigh lines, which is ob ained analy ically. Ou pu pose now is o shi he cen e s o he unca ed Lau en expansion ob ained abo e and o con e hese expansions in o Taylo expansions. We do his in he nex h ee lemmas. LEMMA 3.3. Assume supp Oa Q D(zo, ). Le zl C be such ha Iz0 zi[ > . Then, bk (13) (z) = (Z- Zl) k+l k=0 whe e Y z C D(zl, Izl z0l + ), (14) b Z a (z ZO) k-l. /=0 Mo eo e , i we deno e by ld he p- e m unca ed expansion (13), he ollowing e o es ima e holds: A [,Zl-ZOl+ ] p+I (15) I/d(z) -/d(z)l _< Iz zl- (]Zl zol + ) Iz Zol whe e The ans o ma ion o Lau en expansions in o Taylo expansions is made as ollows. LEMMA 3.4. Assume supp &a C D(zo, ). Le z C be such ha IZl z0[ > (c + 1) (16) (z) = /k(Z- Zl) k /Z D(Zl, ), k=0 whe e (k+l) a (17) (-1) (z zo) + o= (zl zo) l" Mo eo e , gi en an in ege numbe q > 1, de ine he unca ed expansion p (18) Upq(Z) /k (Z Zl) k, k=O whe e he coe icien s , a e de ined by k al (19) = (-1) (z- z0) k+l (Zl -zo) l" A 2 ppQ o some c > 1. Then, 1432 IBRAHIM BLESS RANERO AND TOMAS CHAC 3N REBOLLO Then, he ollowing e o es ima e holds: (20) [(z) LCpq(Z)] c-1 c-1 +1 whe e 1 u IQI, A PPQ Z G D(Zl, ), Lemma 3.4 p o ides an e o es ima e o a unca ed expansion l/[pq ha is de ined only wi h a ini e numbe o da a: he p + q coe icien s a l, a2 ap+q u nished by ei he Theo em 3.1 o Lemma 3.3. The ansla ion o he cen e s o he unca ed Taylo expansions is gi en as ollows. LEMMA 3.5. Gi en he complex numbe s Zl, Z2; /91,/91 pp, he ollowing holds: p p (21) & (z z) /Sk (Z Z2) , k=0 l=0 whe e (22) p /k /gk (Z2 Zl) k-l. k=l Obse e ha as o mula (21) is exac , he e o bound (20) is s ill ue o he unca ed Taylo expansion wi h shi ed cen e i z2 6 D(Zl, ) and z D(z2, ]Zl z21). Also, assume ha he p a e he coe icien s o he Taylo expansion o /g a ound z. Then, in gene al, he/5l a e no he coe icien s o b/a ound z2. This would happen only i he sum in (22) we e in ini e. 3.2. Desc ip ion o he algo i hm. To desc ibe o some ex en he algo i hm o as compu a ion o he disc e e eloci y, we shall need some speci ic de ini ions. We assume ha he suppo o he o ici y h is included in a squa e o sides o leng h H, = 2’2 x 2’2 We e e o his squa e as he compu a ional domain. We subdi ide he compu a ional domain in o a amily o boxes o dec easing size which will be linked by a hie a chy ela ion. Le N be he numbe o nodes Oem in supp (Sh, and de ine he highes le el o e inemen : J log 4 N. Gi en a le el o e inemen j 0, 1 J, we deno e by Q, k 1, 2 4J he squa es /-/ We deno e by ob ained by spli ing each side o in o 2 j subin e als o leng h hj 2-7. /Jk he cen e o box Q. We assume ha each box Q a le el j is a Ca esian p oduc o in e als o he o m Q [a, b[ x [c, d[ H o some a < b and c < d in [-7, [" Then, he boxes a le el j do no o e lap, bu hei eunion is he whole compu a ional box LONG TIME ACCURATE VORTEX METHOD 1433 DEFINITION 3.6. Gi en d > O, we shall say ha wo boxes Q and Q J o he same le el j a e d-sepa a ed i k --i11 " d hj. The ac ha wo boxes a e well sepa a ed allows us o app oxima e uni o mly on each one o hem he eloci y ield induced by he o ici y suppo ed by he o he one by means o he unca ed Taylo de elopmen u nished by Lemmas 3.4 and 3.5. To s a e his esul we need o gi e a o mal de ini ion o he aspec a io o a iangula ion, as a measu e o i s egula i y. The aspec a io o a gi en iangle is he a io be ween he diame e o he smalles ci cle ha can ci cumsc ibe he iangle and ha o he la ge ci cle ha can be insc ibed in he iangle. The aspec a io o a iangula ion Th is he la ges o all aspec a ios o all iangles o Th. LEMMA 3.7. Gi en a box Q o le el j, deno e by co Vh he o ici y suppo ed by QJ (23) O m E Q Call l he (p, q)- e m Taylo expansion associa ed o o9 de ined by (18). De ine Le c > 1 be gi en. Then, he e exis s a cons an ) > O.depending only on he a.spec a io o iangula ion Th such ha i d (c + 1) and box QJ is d-sepa a ed om QJ, hen C-+-1 (24) xEQ{max lu uJl _< B hj (c 1)2 + c +1 Il h whe e B is a cons an depending only on he aspec a io o iangula ion Th. P oo . As h is he longes leng h o all iangles o Th, hen (25) supp coJ C B( lJ, j) wi h j -- hj + h. Also, as h j , he e exis wo posi i e cons an s and/z depending only on he aspec a io o T, such ha h<hj< zh. Thus, 1 1 j < ----_ hj +-hs <_. )hj, / 2 As he boxes a e d-sepa a ed, 1 1 whe e ) + -’ d l ill> d h j > . I we ake d ) (c + 1), we ha e he hypo heses o Lemma 3.4 wi h zo l J k’ Zl [l j. Es ima e (24) ollows immedia ely. 1440 IBRAHIM BLESS RANERO AND TOM,S CHAC 3N REBOLLO FIG. 5. Nume ical con e gence o de in eloci y o Algo i hm A’, applied o TC 1, o a sho ime in e al. The lines ma ked by and + symbols co espond, espec i ely, o hi 1/12, h: 1/16 and o hi 1/16, h2 1/20 o compu e he nume ical con e gence o de . The co esponding heo e ical con e gence o de is p 2 (line ma ked by 0 symbols). FIG. 6. Nume ical con e gence o de in eloci y o Algo i hm A’, applied o TC 1, o a sho ime in e al. The lines ma ked by and + symbols co espond, espec i ely, o h / 12, h2 / 16 and o h / 16, h2 1/20 o compu e he nume ical con e gence o de . The co esponding heo e ical con e gence o de is p 1.5 (line ma ked by 0 symbols). In Figs. 5 and 6 we ep esen he beha iou o he nume ical con e gence o de in eloci y o TC 1 o sho imes. Figu e 5 co esponds o a heo e ical con e gence o de p 2, ob ained by choosing a 2 in Algo i hm A’. Figu e 6 co esponds o p 1.5, ob ained by choosing c 1.5. The sha p oscilla ions obse ed in hese cu es occu when Deiaunay eg idding is pe o med. In bo h cases he e is a good ag eemen be ween he compu ed con e gence o de and he heo e ical one. Fu he mo e, he cu es co esponding o smalle alues o h a e globally close o he heo e ical con e gence o de s. No e ha in all cases he compu ed o de s oscilla e a ound he heo e ical alue. I is in e es ing o obse e ha he con e gence o de o Algo i hm A’ may be p ese o any alue p 6] 1, 2] by simply choosing he pa ame e c p a he beginning o he un. Howe e , aking smalle han 2 would p oduce a was e o compu a ional wo k, as he compu a ional complexi y o Algo i hm A’ is o o de N log 2 N o any alue o a. In wha ollows we shall always ake 2. LONG TIME ACCURATE VORTEX METHOD 1441 o s FIG. 7. Time e olu ion o nume ical con e gence o de in o ici y o Algo i hm A , applied o TC2, o he ime in e al [0, 15]. The lines ma ked by +, *, and 0 symbols co espond, espec i ely, o hi 1/12, h2 1/16; hi 1/16, h. 1/20; and o hi 1/16, h2 1/20 o compu e he con e gence o de . A good ag eemen wi h he heo e ical p edic ion p 2, which imp o es o smalle alues o h, is obse ed o he whole ime in e al. 3"0 1 2.5 E o s FIG. 8. Time e olu ion o nume ical con e gence o de in eloci y o Algo i hm A , applied o TC2, o he ime in e al [0, 15]. The lines ma ked by +, *, and 0 symbols co espond, espec i ely, o hi 1/12, h2 1/16; hi 1/16, h2 1/20; and o hi 1/16, h2 1/20 o compu e he con e gence o de . A goodag eemen wi h he heo e ical p edic ion p 2, which imp o es o smalle alues o h, is obse ed o he whole ime in e al. Figu es 7 and 8 show he nume ical con e gence o de in o ici y and eloci y o TC2 du ing a ela i ely long in eg a ion ime. The sha p oscilla ions o he o me es a e s ill obse ed. Howe e , again he cu es co esponding o smalle alues o h a e close o he heo e ical o de p 2. No e ha he nume ical o de s in eloci y a e close o p 2 han hose in o ici y. This is p obably due o he highe egula i y o he eloci y ield. No e also ha he ag eemen holds e en o long imes. 5.3. Beha iou o long in eg a ion imes. Ou hi d se o nume ical expe imen s deals wi h he analysis o he long ime beha iou o e o s due o Algo i hm A’. A i s , we es ed he e ec o in oducing Delaunay eg idding in Algo i hm A’. In Fig. 9 we ep esen he ime e olu ion o he pe cen ela i e e o s in eloci y co esponding 1442 IBRAHIM BLESS RANERO AND TOM/S CHACON REBOLLO o E o s FIG. 9. Time e olu ion o ela i e e o s in o ici y o Algo i hm A wi h and wi hou using Delaunay eg idding (ma ked by and + symbols, espec i ely). The second one g ows exponen ially while he i s one keeps close o he ini ial e o . o Algo i hm A wi hou eg idding and o Algo i hm A’ using Delaunay eg idding, applied o TC wi h h / 12. We made a un in he ime in e al [0, 50], which appea s as qui e a long ime o he es case conside ed. Indeed, in ha in e al he as es poin s in supp 09 comple ed mo e han h ee o a ions, while he slowes ones did no comple e hal a o a ion. No e ha Algo i hm A is s ill de ined when he iangula ion TT, becomes degene a ed. Indeed, in his case i is s ill possible o compu e di ec ly he exac eloci y T. We may obse e ha in his case he e o g ows exponen ially un il a emp ing ela i e alues o mo e han 50% a _ 50. When Delaunay eg idding is used, he e is a all o e o each ime i is e ec i ely pe o med. This is due o he diminishing o he local g id size ha ende s he linea in e pola ions on each iangle mo e accu a e. A e his, he e is a slow exponen ial inc ease o e o s, which alls again he nex ime Delaunay eg idding is used. No e ha eg idding is no needed e y o en. The e o a 50 is app oxima ely only wo imes he ini ial one. Figu es 10 and 11 also show he beha iou o e o s in eloci y and o ici y co esponding o TC1 and TC2, espec i ely, wi h h 1!12, du ing he ime in e al [0, 100]. This is a e y long ime in e al o bo h cases, as a ime 100 he uni ci cle has been d ama ically de o med by bo h lows. The cu es p esen sha p oscilla ions due no only o he use o Delaunay eg idding, bu also o he low smoo hness o he disc e e/-no m used. Howe e , we ema k a i s ha in bo h cases he e o s in eloci y and o ici y emain almos cons an . Also, in bo h cases he e o s in eloci y a e subs an ially smalle han hose in o ici y. Again, his is e y p obably due o he highe smoo hness o he eloci y ields. No e also ha al hough in TC2 he o ici y is no smoo h enough o ensu e he con e gence o Algo i hm A’, in p ac ice second-o de con e gence is a emp ed. A possible eason o his ac is ha he singula i ies o he o ici y lie on he cu e 1, while we sol e Eule equa ions only inside he uni ci cle. Also, he ac ha he e o s co esponding o TC2 a e close o hose co esponding o TC 1 is p obably due o he adial dis ibu ion o he nodes in he iangula ion used. Figu e 12 ep esen s he iangula ion o TC1 a ime 99, he las ime Delaunay eg idding is used. Obse e he good quali y o he g id, which sugges s ha ou un could con inue o longe imes wi h simila e o le els. Globally, hese es s show ha Algo i hm A’ wi h he use o Delaunay eg idding is s able and accu a e, wi h second-o de accu acy, e en o e y long in eg a ion imes. LONG TIME ACCURATE VORTEX METHOD 1443 E o s 2.5 2.0 Z. 5 FIG. 10. Time e olu ion o e o s in eloci y (line ma ked by + symbols) and o ici y (line ma ked by symbols) o Algo i hm A’, applied o TC1 wi h h 1/12, in he ime in e al [0, 100]. Bo h e o s emain close o he ini ial alues o he whole ime in e al. E o s 2.5 2.0 0 9 18 27 36 45 54 63 72 81 90 99 FIG. 11. Time e olu ion o e o s in eloci y (line ma ked by + symbols) and o ici y (line ma ked by symbols) o Algo i hm A , applied o TC2 wi h h 1/12, in he ime in e al [0, 100]. Bo h e o s emain close o he ini ial alues o he whole ime in e al. 5.4. Compa ison o a desingula ized o ex me hod. Ou nex expe imen is o com- pa e he pe o mances o a o ex me hod on a ixed uni o m g id wi h hose o Algo i hm A’ using Delaunay eg idding. As he o ex me hod we ha e used he desingula ized poin o ex me hod (DPVM) in oduced in Hou [15]. To desc ibe i , le us conside a uni o m g id o size h o R 2 wi h nodes { lj }j EN. Deno e coj COO (/j). Then, DPVM compu es he disc e e eloci y a poin /3 and ime by (43) h( lk, ) g(k l) (COl (-Ok) COk I g( k y) dy, /l Esupp wo J 2h ( ) whe e ]h ( ) is a polygonal app oxima ion o supp co(., ). 1444 IBRAHIM BLESS RANERO AND TOM,/ S CHACON REBOLLO FIG. 12. T iangula ion a ime 99 co esponding o Algo i hm A , applied o TC2 wi h h 1/12, in he ime in e al [0, 100]. This is a s able modi ica ion o he poin o ex me hod, uni o mly con e gen wi h second-o de accu acy. Because o ha , i seems o be a good me hod o compa e wi h ou s. In ou expe imen s we ha e un bo h algo i hms o g ids o size h 1/12 and h 1/16. We always ake he uni ci cle o be he se 2h( ). This allows us o compu e exac ly he in eg al exp ession in (43). Also, we sol ed he equa ion o cha ac e is ics o he DPVM wi h he Adams-Bash o h second-o de scheme, jus as in Algo i hm A’. In ou es s, i no eg idding echniques a e in oduced, he DPVM p oduces a la ge inc ease o e o s in a ela i e ime in e al. Fo ins ance, o TC he ela i e e o s in eloci y ake alues o app oxima ely 80% by ime 40. As we poin ed ou in he In oduc ion, some con enien eg idding echnique is needed o ob ain accu a e solu ions o long in eg a ion imes. Beale and Majda in oduced in 1985 a simple, bu e icien , eg idding echnique in he con ex o a o ex-blob me hod (VBM). VBMs a e based upon he disc e iza ion o o ici y as a sum o smoo h unc ions wi h small suppo s, called blobs. Gi en a smoo h cu o unc ion q (i.e., an app oxima ion o he Di ac del a a he o igin), he o ici y a a ixed ime is app oxima ed by (44) co(x, ) coh(X, ) qa(x Xj( )) COj h 2, J whe e 1 %(x) Wi h a disc e iza ion o he kind o (44), i is possible o compu e he o ici y a any p esc ibed poin . The eg idding echnique o Beale and Majda consis s o ein e pola ing he o ici y a he nodes o a uni o m g id, whene e he cu en local g id size is la ge enough. Howe e , as epo ed by Beale and Majda, he g id size o he ein e pola ing g id should dec ease p og essi ely o main ain easonable e o le els. In DPVM he o ici y is disc e ized as a sum o Di ac masses: (45) co(x, ) -- cob(X, ) Z 6(X Xj( )) coj h 2. J LONG TIME ACCURATE VORTEX METHOD 1445 4 0 9 18 27 36 45 54 69 72 81 90 99 FIG. 13. Compa ison o e o s in eloci y be ween he DPVM (line ma ked by + symbols) and Algo i hm A (line ma ked by symbols), applied o TC1, in he ime in e al [0, 100]. A p og essi e inc ease is obse ed in he i s one, while he second emains almos cons an . Consequen ly, he eg idding echnique o Beale and Majda canno be di ec ly applied he e. Howe e , i is possible o use his echnique a e app oxima ing d by a sum o blobs as in (44). In p ac ice, we ha e used a ou h-o de cu o unc ion : *8(x)=- 2exp -- - This cu o unc ion was also in oduced by Beale and Majda in 1985. Fo smoo h unc ions , he e o a, is o o de 64. We ha e aken 6 o o de h, so his accu acy seems o be enough, as he DPVM is o o de h 2. The eg idding s a egy ha we ha e used consis s o ein e pola ing he o ici y when he smalles angle o he de o med g id is smalle han a p ese limi alue. Each eg idding has been se o p oduce an inc ease in he amoun o he g id poin s o app oxima ely 15%. Figu es 13 and 14 compa e he beha iou o e o s due o he DPVM and o he ini e elemen o ex me hod (FEVM) o Algo i hm A’. We ep esen he e o s in eloci y and ajec o ies co esponding o TC1 du ing he ime in e al [0, 100] wi h ini ial g id size h 1/16. Sha p a ia ions o e o s co esponding o he DPVM a e obse ed, p obably due o he addi ional e o in oduced in he ein e pola ion associa ed o he eg idding s eps. The e o s co esponding o he DPVM inc ease as e han hose co esponding o he FEVM. By ime 0, he e o s co esponding o bo h me hods ake e y simila alues. By ime 100, he la e e o s a e nea ly 200 imes smalle han he o me ones in eloci y and nea ly 20 imes smalle in ajec o ies. This di e en g ow h a e is p obably a consequence o he in oduc ion o nume ical di usion in he eg idding s eps. We may conclude ha he FEVM sol es mo e accu a ely ou TC 1 o long imes, wi hou in oducing nume ical di usion. We should poin ou ha he compu a ional wo k needed by one ime-s ep wi h he FEVM is nea ly 100 imes bigge han he one needed by one ime- s ep wi h he DPVM. Howe e , his wo k emains cons an in ime o he FEVM, while ha 1446 IBRAHIM BLESS RANERO AND TOM/S CHAC(3N REBOLLO 2.5 -0. E o s 1(3 27 3(3 45 54 63 72 131 90 99 FIG. 14. Compa ison o e o s in ajec o ies o g id poin s be ween he DPVM (line ma ked by + symbols) and Algo i hm A (line ma ked by symbols), applied o TC1, in he ime in e al [0, 100]. needed by he DPVM inc eases each ime eg idding is pe o med. Thus, o long enough ime in e als, bo h compu a ional e o s will be o he same o de . 5.5. Compa ison o high-o de VBMs. We inally compa ed he FEVM wi h he VBM wi h cu o unc ions o o de s m 4 and m 6. Speci ically, we used hose in oduced by Beale and Majda, co esponding o p:4, (x)=- 2exp - - exp (- 2@2)] p--6, 1 2 1 2 J6)(x) - I exp (----)- exp (--2@2)+ - exp (---)]. To ensu e he con e gence o he me hod, we ook he blob size o be 6 h q, wi h 0 < q < 1. Thus, o smoo h enough ini ial o ici y, he con e gence o de o he me hod is p=mq. In p ac ice, we ook q 0.95 in all ou expe imen s, as his alue seems o be quasiop- imal, as epo ed by Pe lman. The s eamline equa ion has been sol ed wi h a ou h-o de Runge-Ku a me hod wi h e y small ime-s ep. We ha e es ed ou code o TC1 a 1. Ou es ima ions o compu ed con e gence o de s a e gi en in Table 1. They a e in e y good ag eemen wi h hose epo ed by Pe lman. We ha e used he eg idding echnique desc ibed in he p eceding subsec ion, wi h some mino modi ica ions. Indeed, many possible c i e ia which can be used o apply eg idding a e equi alen in p ac ice o he o a ing s eady solu ions we a e conside ing. Ei he eg idding when he smalles angle o he mesh is smalle han a gi en ole ance, o when he cu en g id size is long enough, is equi alen o eg idding a ce ain ixed numbe o ime-s eps. In any LONG TIME ACCURATE VORTEX METHOD 1447 TABLE Con e gence o de o he VBM o TC1, es ima ed a ime 1, used o compa e o he FEVM. Values o m and h h 0.2 h 0.1 h 0.05 Theo e ical o de s m 4 2.53 3.32 3.60 3.80 m 6 2.78 4.44 5.16 5.70 O,B 0.7 IME I FIG. 15. Compa ison o e o s in eloci y be ween Algo i hm A’ (line ma ked by 0 symbols) and he VBM wi h m 4 (line ma ked by + symbols) and m 6 (line ma ked by symbols) o TC1 and h 1/16 in he ime in e al [0, 100]. case, he ac ual ole ance alue mus be uned wi h ca e o a oid an excessi e inc ease in e o s. I eg idding is applied oo o en, we shall p og essi ely in oduce high le els o nume ical di usion, bu i he g id is excessi ely dis o ed when eg idding, hen he accumula ed e o s will p oduce an un eco e able loss o accu acy. In Figs. 15 and 16 we ep esen he ela i e e o s in eloci y o he FEVM and o he VBM wi hm 4 andm 6, co esponding o TC1 wi h h 1/16 and TC2 wi h h 1/12. We may obse e ha eg idding is applied in all cases an almos cons an numbe o ime-s eps. In all cases e o s a e kep almos cons an o a sho ime in e al whene e eg idding is applied and expe ience a as inc ease when he g id becomes p og essi ely dis o ed. Fo m 6, his inc ease is e y as , and his is p obably he eason why eg idding p oduces a dec ease in e o s. Fo m 4, he e o s do no g ow as as , and eg idding p oduces an inc ease in hem. Also, almos linea g ow h a es o e o s a e obse ed in all cases. These a es a e smalle o m 6 han o m 4. Fo he FEVM, he g ow h o e o s as he g id is dis o ed is he as es o all cases conside ed. Thus, he loss o quali y o he g id mo e d ama ically a ec s he accu acy o he FEVM han ha o he VBM. Howe e , applying Delaunay eg idding in he FEVM diminishes he e o s o alues close o he ini ial ones, coun e balancing almos comple ely he o me inc ease. In TC 1, which co esponds o a smoo h solu ion, he FEVM p esen s a be e pe o mance a ime 100 han he VBM wi h m 4, while he VBM wi h m 6 yields a highe accu acy han he FEVM. Howe e , in TC2, which co esponds o a less smoo h o ici y, he pe o mance o he FEVM a 100 imp o es ha o he VBM wi h m 4 and also ha o he VBM wi h m 6. We should also ema k ha he g ow h a es o e o s o he BVM a e 1448 IBRAHIM BLESS RANERO AND TOM/S CHACON REBOLLO (VEL.),_ H=/! 4050. 70, 100. FIG. 16. "Compa ison o e o s in eloci y be ween Algo i hm A’ (line ma ked by 0 symbols) and he VBM (line ma ked by + symbols) wi h m 4 and m 6 (line ma ked by symbols) o TC2 and h 1/12 in he ime in e al [0, 100]. in all cases la ge han hose co esponding o he FEVM. Thus, he compa ison is e y likely o be e en mo e a ou able o he FEVM o la e in eg a ion imes. Finally, we mus say ha we may no expec o sol e wo-dimensional Eule equa ions wi h any ini ial condi ion, simply by using Algo i hm A’ combined wi h Delaunay eg idding. I seems clea ha , in gene al, he o he eg idding ules ha we men ioned in 2 a e needed o ob ain accu a e esul s. The esul s p esen ed in his pape mus be unde s ood in he sense ha ou FEVM, due o i s geome ical adap abili y, imp o es he accu acy o classical o ex me hods, wi hou in oducing nume ical di usion. Appendix: P oo o Theo em 4.1. P oo . Ou p oo is an adap a ion o he con e gence p oo o Algo i hm A gi en by Chacon and Hou. The essen ials o he p oo a e as ollows. Le us de ine T* max . "0 < n < T, max IlX 311,h < h I+p whe ep [min(2 c )-l] 0<k<n We p o e ha he e exis s a sepa a ion pa ame e d, depending only on Coo, T, c, and , such ha es ima es (33) hold in he ime in e al [0, T*]. Then, we conclude ha he e exis wo posi i e numbe s h T- and AT- such ha i 0 < h < h T- and 0 < A < AT-, hen he e mus be T*>T. The main inno a ion in ou analysis is ha we ob ain uni o m-in- ime es ima es o he e o in he compu a ion o disc e e eloci ies by Algo i hm B. As we shall see, his essen ially happens because ou algo i hm p ese es he uni o m no m o he disc e e solu ion. Indeed, i 0 _< , _< T*, ollowing Chacon and Hou we s a e ha i h is small enough, hen all iangula ions {7}0<_ ,<_, a e nondegene a ed. Mo eo e , all aspec a ios o hese iangula ions a e uni o mly bounded om abo e by a cons an }/ independen o h. Le us de ine he sepa a ion pa ame e d )L (1 + c), whe e i z is he pa ame e associa ed o ?’ gi en by Theo em 3.11. No e ha d7 depends only on coo, T, c, and he aspec a io o he ini ial iangula ions. LONG TIME ACCURATE VORTEX METHOD 1449 (46) and We p o e now ha he e exis wo posi i e cons an s and C such ha supp ^n o) h C B(0, ), 0 < n < T*, (47) Indeed, assume ^n .n. h T*. max I[ i--(K.(Oh)]( j)l <C 0< n < O<j<M supp b-I C B(0, n-1), supp ^n (-o h C B(O, n) o some posi i e numbe s n-1 < n. Le us deno e by he Euclidean no m on R 2 and by II he uni o m no m on R 2. Theo em 3.11 yields (48) < C1 n ^n h ^n %11 - - Ig(] Y)I Coh(Y)dY _< C2 n Ilco011 JB (O, .) No e ha he las inequali y he e ollows because Algo i hm A conse es in ime he uni o m no m o he disc e e o ici y. Consequen ly, IXj^n+l IXjl -A 3 [u h^n(Jy)[ _+_ [ n-l(j]-l)[ _< IXjl + C3 A , j--1 M. Thus, n < o exp(C3 T), 0 <_ n < T*. The emainde o he p oo is a echnical e inemen o ha o Chacon and Hou. We shall omi i he e, as i does no in oduce any essen ial inno a ion. V] Acknowledgmen s. The au ho s wish o hank Maca ena G6mez Ma mol o he aluable help in ob aining he g aphic ou pu . REFERENCES [1] C. ANDERSON, Obse a ions on o ici y c ea ion bounda y condi ions, in Ma hema ical Aspec s o Vo ex Dynamics, R. Ca lisch ed., Socie y o Indus ial and Applied Ma hema ics, Philadelphia, PA, 1988, pp. 144-159. [2] C. ANDERSON AND C. GREENGARD, On o ex me hods, SIAM J. Nume . Anal., 22 (1985), pp. 413-439. [3] J. T. BEALE AND A. MAJDA, Vo ex me hods I: Con e gence in h ee dimensions, Ma h. Comp., 32 (1982), pp. 1-27. [4] Vo ex me hods II: High o de accu acy in wo and h ee dimensions, Ma h. Comp., 32 (1982), pp. 29-52. [5] High o de accu a e o ex me hods wi h explici o ici y ke nels, J. Comp. Phys., 58 (1985), pp. 188-208. [6] M. BERNADOU e al., MODULEF A Modula Lib a y o Fini e Elemen s. INRIA, Rocquencou , F ance, 1986. [7] R. BOWYER, Compu ing Di ichle essella ions, Compu . J., 24 (1981) pp. 162-166. [8] T. E BUTTI(E, Fas o ex me hods in h ee dimensions, in Vo ex Dynamics and Vo ex Me hods, Lec u es in Appl. Ma h., Vol. 28, K. E. Gus a sson and J. A. Se hian, eds., Ame ican Ma hema ical Socie y, P o idence, RI, 1991, pp. 51-66. [9] A as adap i e me hod o pa ches o cons an o ici y in wo dimensions, J. Compu . Phys., 89 (1990) p. 161.