ENO 도식

1. 개요[편집]

ENO 도식 Essentially Non-Oscillatory Scheme
발표	Harten · Engquist · Osher · Chakravarthy (1987), J. Comput. Phys. 71
핵심	나눗차분으로 가장 매끄러운 스텐실 하나를 고른다
정확도	$r$ 점 스텐실 → $r$ 차
진동 조건	$\mathrm{TV}(u^{n+1}) \le \mathrm{TV}(u^{n}) + O(\Delta x^{r})$
고효율 구현	Shu · Osher (1988, 1989) — FD 플럭스 판본 + SSP-RK
후계	WENO 도식

스텐실이 불연속을 물면 진동한다. 그러면 물지 않는 스텐실을 찾으면 되잖아?

ENO 도식(Essentially Non-Oscillatory scheme)은 고정된 스텐실에 제한자를 걸어 진동을 누르는 대신, 후보 스텐실 여러 개 중 나눗차분이 가장 작은 것 — 즉 자료가 가장 매끄러운 것 — 을 골라 그 위에서만 고차 보간을 하는 재구성 기법이다. 1987년 하튼·엥크비스트·오셔·차크라바시가 발표했고, 고차 충격파 포착이라는 분야를 사실상 열어젖힌 논문으로 통한다.¹

전변분 감소(TVD) 계열이 “스텐실은 그대로 두고 기울기를 깎는다”였다면, ENO는 **“기울기는 그대로 두고 스텐실을 옮긴다”**다. 이 차이 하나가 TVD의 고질병인 극값 클리핑을 없앴다. 불연속 근처에서 3점이든 5점이든 그 안에 점프가 없는 쪽으로 스텐실이 도망가므로, 매끈한 마루와 진짜 위글을 구별하지 못해 둘 다 깎아 버리던 문제가 사라진다.

대신 새 문제가 생겼다. 스텐실 선택이 자료의 불연속 함수라는 것이다. 이 성질이 ENO의 정확도·수렴성·구현 난이도를 전부 갉아먹었고, 7년 뒤 WENO 도식이 “고르지 말고 섞자”로 갈아탄 이유가 된다. 그래서 오늘날 ENO를 그대로 쓰는 코드는 드물지만, WENO를 이해하려면 반드시 거쳐야 하는 관문이라 문헌에서 사라지지 않는다.

2. TVD가 남긴 숙제[편집]

먼저 왜 새 아이디어가 필요했는지부터. 고두노프 도식 장벽은 “선형이면서 단조인 도식은 1차를 넘을 수 없다”고 말한다. TVD는 이 장벽을 제한자라는 비선형 장치로 우회했지만, 그 대가로 $r \le 0$ 에서 제한자가 0이 되는 조건, 즉 국소 극값에서 무조건 1차로 내려앉는 성질을 떠안았다. 사인파를 이류시키면 마루가 매 스텝 깎여 나가고 $L^1$ 수렴 차수가 2차 아래로 주저앉는다.

원인은 TVD의 정의 자체에 있다. 전변분이라는 하나의 스칼라는 “새 극값이 생겼다”만 알려줄 뿐 그것이 물리인지 수치 잡음인지 구별하지 못한다. 3점만 보면 매끈한 마루와 위글은 똑같이 생겼다.

ENO의 답은 조건을 느슨하게 푸는 것이었다. 전변분이 절대 늘지 않을 것까지는 요구하지 않고,

$$\mathrm{TV}(u^{n+1}) \;\le\; \mathrm{TV}(u^{n}) + O(\Delta x^{r})$$

만 요구한다. 즉 진동이 없는 게 아니라 격자를 조이면 진동의 크기가 $r$ 차로 사라진다는 것. 이름의 “essentially”가 정확히 이 뜻이다.² 엄밀한 보증을 조금 내주고 매끄러운 극값에서의 차수를 되사 온 거래다.

3. 나눗차분 — 매끄러움의 자를 하나 고른다[편집]

ENO가 매끄러움을 재는 도구는 나눗차분(divided difference)이다. 보간과 근사에서 나오는 그 뉴턴 나눗차분이 맞다. 서로 다른 점 $x_{j},\dots,x_{j+k}$ 에 대한 $k$ 계 나눗차분 $V[x_j,\dots,x_{j+k}]$ 는 두 가지 얼굴을 가진다.

• 자료가 매끄러우면 $V[x_j,\dots,x_{j+k}] = \dfrac{V^{(k)}(\xi)}{k!} = O(1)$ — 격자를 조여도 유계다.
• 구간 안에 크기 $[V]$ 의 점프가 있으면 $V[x_j,\dots,x_{j+k}] = O\!\left(\dfrac{[V]}{\Delta x^{k}}\right)$ — 격자를 조이면 발산한다.

즉 나눗차분의 절댓값이 크다는 것은 그 스텐실이 불연속을 물었다는 신호다. 이게 ENO의 전부이고, 나머지는 이 판정을 어떻게 반복해서 쓰느냐일 뿐이다.³

한 가지 기술적 우회가 필요하다. 유한체적법이 들고 있는 것은 점값이 아니라 셀 평균 $\bar u_i$ 라서 그대로 보간할 수 없다. 하튼 등은 원함수(primitive function)

$$V(x_{i+1/2}) \;=\; \int_{-\infty}^{x_{i+1/2}} u(\xi)\,d\xi \;=\; \sum_{k \le i} \bar u_{k}\,\Delta x_{k}$$

를 도입해 이 문제를 정면 돌파했다. 셀 평균의 누적합이 곧 원함수의 격자점 값이므로, $V$ 를 $r+1$ 차로 보간해 미분하면 $u$ 의 $r$ 차 재구성이 나온다. 누적합만 취하면 재구성이 보간 문제로 환원된다는 이 관찰이 논문의 기술적 심장이다.

4. 스텐실을 키워 가는 알고리즘[편집]

$r$ 차 재구성을 위한 스텐실 선택은 한 점씩 붙여 나가는 탐욕 절차다. 셀 $i$ 에서 시작하자.

1. 스텐실을 셀 하나 $\{i\}$ 로 시작한다. 원함수 기준으로는 두 점 $\{x_{i-1/2},\,x_{i+1/2}\}$ 이다.

2. 현재 스텐실이 $\{x_{l},\dots,x_{m}\}$ 일 때, 왼쪽으로 한 점 늘린 나눗차분과 오른쪽으로 한 점 늘린 나눗차분을 비교한다.

   $$\bigl\lvert V[x_{l-1},\dots,x_{m}] \bigr\rvert \quad \text{vs} \quad \bigl\lvert V[x_{l},\dots,x_{m+1}] \bigr\rvert$$

3. 작은 쪽으로 스텐실을 늘린다. 즉 덜 매끄러운 방향으로는 가지 않는다.

4. 셀 $r$ 개를 모을 때까지 2~3을 반복한다.

결과적으로 얻는 스텐실은 $\{i-l,\dots,i-l+r-1\}$ 형태이고, 편향 $l$ 이 자료에 따라 $0$ 부터 $r-1$ 까지 자유롭게 움직인다. 충격파 왼쪽에 있는 셀은 왼쪽으로만 뻗고, 오른쪽에 있는 셀은 오른쪽으로만 뻗는다. 아무도 불연속을 넘어가지 않는다 — 그래서 재구성 다항식이 점프를 흉내 내려다 진동하는 일이 원천적으로 줄어든다.

$r=3$ 이면 후보 스텐실이 $\{i-2,i-1,i\}$, $\{i-1,i,i+1\}$, $\{i,i+1,i+2\}$ 셋이다. WENO 도식이 가중 평균하는 바로 그 셋이며, 두 도식의 관계가 여기서 한눈에 보인다.

5. ENO의 세 가지 약점[편집]

발표 직후부터 잘 알려진 문제가 셋이다. 세 가지 모두 “고른다”는 행위 자체에서 나온다.

첫째, 스텐실 선택이 자료의 불연속 함수다. 수치 플럭스가 격자값에 대해 미분가능하지 않다는 뜻이고, 청구서가 두 군데로 온다. 정상상태 계산에서 반복마다 스텐실이 딸깍거리면 잔차가 어느 수준 아래로 안 내려가고 그대로 정체한다 — TVD 제한자의 채터링과 같은 병이다. 그리고 자동 미분이나 수반법으로 도식을 미분해야 하는 형상 최적화·자료 동화에서는 아예 미분 대상이 성립하지 않는다.

둘째, 매끄러운 영역에서 기계 반올림에 스텐실이 흔들린다. 자료가 거의 균일하면 좌우 나눗차분의 크기가 거의 같아지고, 최종 판정을 배정도 마지막 자리가 내린다. 문제는 스텐실이 한 칸 바뀌면 재구성 계수가 통째로 바뀐다는 것 — 이웃한 두 셀이 서로 $2r-2$ 점 떨어진 스텐실을 고를 수도 있다. 이렇게 되면 매끄러운 해에 격자 규모의 잡음이 실리고, 설계 차수가 실측에서 안 나온다. 로저슨과 마이버그(1990)가 선형 이류 문제에서 ENO가 설계 차수에 도달하지 못하는 사례를 보고했고, 슈(1990)가 중앙 스텐실 쪽으로 편향을 주는(biasing) 처방을 제안해 완화했다. 근본 치료가 아니라 진통제라는 점이 중요하다.

셋째, 차수가 최적이 아니다. $r$ 차를 얻으려고 실제로 훑는 점은 후보 전체를 합쳐 $2r-1$ 개인데, 정작 쓰는 것은 그중 $r$ 개다. 나머지 $r-1$ 개의 정보는 “어느 쪽으로 갈지” 판정에만 쓰이고 버려진다. 매끄러운 영역에서는 $2r-1$ 차를 공짜로 가질 수 있었는데 $r$ 차만 챙긴 셈이다. WENO의 출발점이 정확히 이 낭비다.

부수적인 문제도 있다. 스텐실이 완전히 하류 쪽으로 치우칠 수 있어 특정 조합에서 선형 불안정이 나타날 수 있고, 나눗차분 비교와 분기(branch)가 셀마다 들어가서 벡터화·GPU 이식이 최악이다. 조건 분기가 SIMD 레인을 갈라놓는 구조라 요즘 하드웨어와 궁합이 나쁘다.⁴

6. Shu–Osher 판본 — ENO를 실제로 쓸 만하게 만든 논문[편집]

원 논문의 ENO는 셀 평균·원함수·리만 솔버 조합이라 다차원에서 비쌌다. 슈와 오셔가 1988·1989년 두 편에 걸쳐 유한차분 플럭스 판본으로 갈아엎으면서 실용화됐고, 오늘날 “ENO/WENO 구현”이라 하면 대개 이 골격을 뜻한다. 세 가지 부품이 여기서 나왔다.

• 점값 기반 플럭스 재구성. 셀 평균 대신 점값을 들고, 플럭스 함수의 점값을 보조함수의 셀 평균으로 간주해 같은 재구성 연산자를 먹인다. 균등 격자에서만 성립하는 대신 방향별로 1차원 커널을 돌리면 끝이라 다차원 비용이 선형으로 떨어진다.
• 플럭스 분해. 상류 편향을 주기 위해 $f = f^{+} + f^{-}$ 로 나눈다. 락스-프리드리히스 분해 $f^{\pm} = \tfrac{1}{2}(f \pm \alpha u)$ 가 표준이고, 리만 솔버를 안 부르고도 상류성을 확보한다.
• SSP 룽게-쿠타. 공간을 아무리 잘 짜 놔도 시간 적분이 진동을 만들면 헛일이다. 후진 오일러의 볼록결합으로만 구성돼 공간 도식의 비진동성을 보존하는 시간 적분자를 같이 제시했다. 발표 당시엔 “TVD 룽게-쿠타”라 불렀고 지금은 SSP(strong stability preserving)로 이름이 바뀌었다. 3단 3차 판본이 CFL 계수 1로 나와 사실상 공짜라 룽게-쿠타법 문헌에서도 유명하다.

이 세 부품은 그대로 WENO에 상속됐다. WENO가 바꾼 것은 재구성 한 군데뿐이고 나머지 골격은 전부 1989년에 완성돼 있었다는 점을 알아 두면 코드를 읽을 때 편하다.

7. TVD 제한자와 무엇이 다른가[편집]

	TVD 제한자 (MUSCL 등)	ENO
비선형성이 들어가는 곳	기울기(제한자 함수)	스텐실 선택
스텐실	고정	자료 적응
진동 보증	$\mathrm{TV}$ 비증가 (엄밀)	$\mathrm{TV}$ 증가가 $O(\Delta x^{r})$
매끈한 극값	1차로 강등 (클리핑)	차수 유지
최대 차수	실용상 2~3차	원리상 임의 $r$
미분가능성	대부분 미분가능	불가능
구현 난도	낮음	높음 (분기·나눗차분)

요약하면 TVD는 안전을 사고 정확도를 팔았고, ENO는 정확도를 사고 안전과 매끄러움을 팔았다. 어느 쪽도 공짜가 아니었다는 것이 고두노프 도식 장벽의 실제 의미다.

8. 남은 자리, 그리고 WENO로[편집]

ENO를 그대로 쓰는 생산 코드는 이제 거의 없다. 매끄러운 영역의 차수, 정상상태 수렴, 벡터화 세 항목 모두 WENO 도식이 우세하고, 바꾸는 데 드는 비용도 크지 않기 때문이다. 그럼에도 ENO의 이름이 계속 등장하는 자리가 셋 있다.

• 해밀턴-야코비 방정식. 오셔와 세시안의 레벨셋 방법 원 논문이 ENO 이산화를 쓴다. 보존형이 아니라 재구성 대신 ENO 보간이 들어가는 형태이고, 요즘은 여기서도 WENO 판본이 표준이다.
• 적응 스텐실 보간 그 자체. 격자 간 자료 전달, 적응 격자 세분화의 프롤롱게이션처럼 “불연속을 넘지 않는 보간”이 필요한 곳에서 ENO 보간이 그대로 쓰인다.
• TENO 계열. 최근의 targeted ENO는 매끄러움 지표에 문턱을 걸어 후보를 완전히 켜고 끄는 방식인데, 이는 WENO의 매끄러운 가중이 매끄러운 영역에서 필요 이상으로 소산적이라는 반성에서 나온 것이다. 즉 ENO의 “고른다”가 30년 만에 문턱이라는 형태로 돌아왔다.

역사적 평가는 명확하다. ENO는 최종 도착지가 아니라 방향 전환점이었다. 진동 억제를 “값을 깎는 문제”에서 “정보를 어디서 가져올까 하는 문제”로 재정의했고, 그 재정의가 유효했기 때문에 후속 30년의 연구가 전부 그 위에 쌓였다.

9. 관련 문서[편집]

• WENO 도식 · 전변분 감소 · MUSCL · 고두노프 도식
• 유한체적법 · 유한차분법 · 리만 솔버 · 불연속 갤러킨법
• 보간과 근사 · 뉴턴 보간 · 차분 도식
• 충격파 · 압축성 유동 · 깁스 현상 · 유계 변동 함수
• 룽게-쿠타법 · CFL 조건 · 수치 소산과 분산
• 레벨셋 방법 · 적응 격자 세분화 · 자동 미분

10. Footnotes[편집]

1. 논문 제목이 ”…Essentially Non-oscillatory Schemes, III”이라 1편과 2편을 찾다가 헤매는 사람이 매년 나온다. 시리즈 앞 편들은 저널 논문 형태로 널리 유통되지 않았고, 정작 인용되는 것은 거의 언제나 이 세 번째 편이다. 참고로 이 논문은 10년 뒤 저널의 기념호에 통째로 재수록되는 대접까지 받았다. ↩

2. “essentially”를 “본질적으로”라고 옮기면 뜻이 반대로 읽힌다. 여기서는 “사실상, 실용적으로는”에 가깝다. 진동이 본질적으로 없다는 게 아니라 $O(\Delta x^{r})$ 만큼은 있는데 실용상 문제 없다는 겸손한 주장이다. 논문 제목의 단어 하나가 이 정도로 정확한 경우도 드물다. ↩

3. “가장 매끄러운 스텐실”이라는 말이 직관적이라 다들 그러려니 넘어가는데, 매끄러움을 나눗차분으로 재는 것은 선택이지 필연이 아니다. WENO가 나눗차분 대신 도함수 제곱 적분(매끄러움 지표)으로 갈아탄 것도 같은 자를 다르게 만든 것뿐이다. 자를 무엇으로 잡느냐가 그 도식의 성격을 거의 다 결정한다. ↩

4. 분기가 많아 GPU에 안 맞는다는 지적은 ENO만의 팔자가 아니다. 제한자든 스텐실 선택이든 “자료를 보고 갈림길에서 결정하는” 모든 도식이 같은 벌을 받는다. 그래서 WENO의 나눗셈 범벅이 오히려 분기 없는 산술이라 GPU에서 더 잘 도는 역설이 생긴다. ↩