Ⅰ. 서 론
전자파 산란해석 수치해석방법 중 MoM(Method of Moments)은 full-wave simulation의 대표적인 방법이다. MoM 방법은 적분방정식을 차분화하여 최종 행렬 방정식을 얻은 후, 이를 풀어 표면전류를 구한다[1]. 그러므로 MoM 방법의 수치복잡도는 일반적으로 행렬 방정식의 해를 구하는 알고리듬에 의해 결정된다. 행렬크기가 N이고 반복법(iterative method)을 사용하는 경우, MoM 방법의 수치복잡도는 O(N2)로 알려져 있다.
전자파해석에 일반적으로 사용되는 반복법으로 CGS (Conjugate Gradient Squared), BiCGstab(BiCG stabilized) 등이 있다[2]. BiCGstab 반복법은 CGS 반복법의 불규칙한 수렴성을 개선하기 위하여 BiCG 과정 후 GMRES(General-ized Minimal Residual) 과정을 수행한다. 그러나 대규모 산란문제에는 BiCGstab 반복법의 수렴성 및 속도가 크게 개선되지 못하는 한계가 있다. 그러므로 BiCGstab(l) 반복법이 제안되었고, 이는 GMRES(l) 과정을 사용하여 수렴성 및 속도를 개선하였으며[3], 여러 전자파 수치해석 방법에 적용되었다[4]. 일반적으로 l값이 증가할수록 반복 횟수는 줄어들지만, 반복당 수행되는 연산량이 증가한다.
BiCGstab(l) 반복법의 알고리듬에는 스칼라-벡터 곱(AXPY), 내적(DOT), 행렬-벡터 곱(MV) 등의 연산들이 수행된다. 이 가운데 행렬-벡터 곱의 연산량 O(N2)은 MLFMM (Multi-Level Fast Multipole Method)을 통하여 O(NlogN)까지 낮출 수 있다. 여기서 MLFMM 방법은 MoM 방법의 기저함수들과 테스트함수들의 상호작용을 계층적으로(hierarchically) 그룹화함으로써 수행된다[5]~[7].
본 논문에서는 MLFMM 방법에 대한 BiCGstab(l) 반복법의 l값에 따른 수렴속도와 연산량을 몇 가지 산란문제들에 관하여 살펴본 후, 효율적인 l값을 제안한다.
Ⅱ. BiCGstab(l)의 총 연산량 분석
BiCGstab(l) 반복법의 수치복잡도(numerical complexity)는 스칼라-벡터 곱셈(AXPY), 내적(DOT), 행렬-벡터 곱셈(MV) 연산들의 연산랑에 의해 결정된다. 이런 연산들은 반복법이 수렴할 때까지 매 반복과정마다 필요하다. 표 1 은 각 반복과정에서 필요한 연산들의 횟수를 보여준다. 여기서 KAXPY, KDOT, KMV는 각각 반복과정 당 AXPY, DOT, MV의 연산들의 사용횟수를 나타낸다. 각 연산들의 정확한 연산량은 행렬크기 N에 비례하나 정확하게 예측하기 어렵다. 예를 들어, MLFMM의 MV 연산인 경우 점근적(asymptotic) 연산량은 O(NlogN)로 알려져 있다[5]~[7]. 그러므로 AXPY 및 DOT 연산에도 점근적 연산량을 사용하고, 두 연산 모두 O(N)로 알려져 있다. 특정한 산란 문제의 반복횟수(NI)를 알 수 있으면 총 점근적 연산량(NT)를 다음과 같이 구할 수 있다.
Method | K AXPY | K DOT | K MV | Memory usage |
---|---|---|---|---|
BiCGstab | 6 | 4 | 2 | 10N |
BiCGstab(2) | 15 | 9 | 4 | 12N |
BiCGstab(3) | 27 | 15 | 6 | 14N |
⋯ | ⋯ | ⋯ | ⋯ | ⋯ |
BiCGstab(l) | 3l(l + 3)/2 | l(l + 7)/2 | 2l | (8 + 2l)N |
식 (1)에서 NI는 산란문제에 따라 달라진다. 본 논문에서는 3가지 예제에 대해 NI를 구한다. 그림 1(a)~(c)는 고려하는 산란문제들을 보여준다. 그림 1(a)는 작은 두 산란체(박스와 구)의 상호작용인 경우이다. 그림 1(b)는 하나의 산란체이나 입사파가 산란체의 뽀족한 부분으로 입사하여 상호작용이 상대적으로 많은 경우이다. 그림 1(c)는 보다 크고 일반적인 형상을 지닌 산란체 경우이다. 주파수는 모두 2 GHz로 가정하고, 메시 개수와 입사각, 편파 등은 표 2에 나타내었다. 그림 1은 산란체의 형상 및 반복법으로 계산된 표면전류도 함께 보여준다.
Scatterer | N | Incident angle / Polarization |
---|---|---|
Fig. 1(a) | 5,451 | θ = 60°,ϕ = 0° / h-pol. |
Fig. 1(b) | 7,410 | θ = 0°,ϕ = 90° / v-pol. |
Fig. 1(c) | 35,043 | θ = 60°,ϕ = 0° / h-pol. |
Ⅲ. 결과분석
그림 2는 그림 1(a) 산란문제에 적용된 다양한 l값에 따른 BiCGstab(l) 반복법 수렴곡선을 보여준다. l=1은 전통적인 BiCGstab 방법이다. 앞서 언급한 바와 같이, l이 클수록 수렴성이 좋아진다. 그림 3은 그림 1(a)~그림 1(c) 산란문제들의 총 반복횟수(NI)를 l값에 관한 그래프를 보여준다. 그림 3에서 보듯이, BiCGstab(l) 반복법은 l값이 증가할수록 NI가 감소한다. 그러나 표 1에서 보듯이 l값이 증가할수록 KAXPY, KDOM, KMV도 함께 증가하기 때문에, 식 (1)에서 NI가 감소하더라도 NT는 NI만큼 효과적으로 감소하지 않는다. 뿐만 아니라, 표 1에서 보듯이, l값이 증가할수록 메모리 사용량도 증가하기 때문에 효율적인 l값의 선택이 중요하다. 그림 4는 그림 1(a)~그림 1(c)의 산란문제들에 관하여 식 (1)에 의해 계산된 총 점근적 연산량(NT)을 보여준다. 비교를 위해 결과들은 l=1일 때의 연산량으로 정규화 하였다. 그림 4에서 보듯이 l=2~3의 근방에서 모든 결과들의 NT가 국소값(local minimum)을 가짐을 알 수 있다. NT가 다시 증가하는 이유는 KAXPY와 KDOT가 l2에 비례하기 때문이다.
![jkiees-29-3-167-g2](/journal/jkiees/jkiees-29-3/gif/jkiees-29-3-167-g2.gif)
![jkiees-29-3-167-g3](/journal/jkiees/jkiees-29-3/gif/jkiees-29-3-167-g3.gif)
![jkiees-29-3-167-g4](/journal/jkiees/jkiees-29-3/gif/jkiees-29-3-167-g4.gif)
산란체의 전기적 크기가 매우 클 경우에는 AXPY와 DOT의 연산에 비하여 MV의 연산이 총 연산량(NT)에 주된 영향을 준다. 그러므로 MV만을 고려하여 총 연산량(NT)을 예측할 수 있으며, 이 경우에 근사화된 총 연산량은 그림 5에 보여진다. 마찬가지로 결과들은 l=1일 때의 연산량으로 정규화되었다. 그림 5에서 보듯이, l=2~3일 경우 총 연산량은 l=1을 사용한 경우에 비하여 55~70 % 정도 줄어든다. 그러나 l값을 계속 증가시켜도 총 연산량은 현저히 개선되지는 않는 것을 알 수 있다. 그러므로 l= 2~3을 선택하면 BiCGstab(l) 반복법의 연산량과 메모리 사용량을 최적으로 사용할 수 있다.
![jkiees-29-3-167-g5](/journal/jkiees/jkiees-29-3/gif/jkiees-29-3-167-g5.gif)
Ⅳ. 결 론
대규모 산란체의 산란해석 문제에는 반복법 기반의 MLFMM 방법이 주로 사용된다. BiCGstab(l) 반복법은 Bi-CG 과정 후 GMRES(l) 과정을 수행하는 반복법으로, l값이 증가할수록 수렴하기까지 필요한 총 반복횟수가 줄어든다. 그러나 반복 당 MV 등의 연산들의 횟수와 필요 메모리가 증가한다. 3가지 산란문제 해석결과에 기반하여, BiCGstab(l) 반복법의 l값에 따른 수렴곡선과 연산량을 분석하였다. l=2~3을 선택 시 l=1일 경우에 비하여 총 연산량을 55~70 %까지 감소시킬 수 있다. 그러나 보다 큰 l값에 관해서는 연산량의 감소가 미미하므로, l=2~3이 BiCGstab(l) 반복법의 최적이 선택이 된다.