Computational Complexity of BiCGstab(l) in Multi-Level Fast Multipole Method(MLFMM) and Efficient Choice of l

Lee, Hyunsoo; Rim, Jae-Won; Koh, Il-Suek; Seo, Seung-Mo

doi:10.5515/KJKIEES.2018.29.3.167

J. Korean Inst. Electromagn. Eng. Sci. 2018; 29(3):167-170

pISSN: 1226-3133, eISSN: 2288-226X

DOI: https://doi.org/10.5515/KJKIEES.2018.29.3.167

논문/REGULAR PAPERS

MLFMM(Multi-Level Fast Multipole Method) 방법에 적용된 BiCGstab(l)반복법의 l값에 따른 연산량 분석 및 효율적인 l값

이현수¹, 임재원¹, 고일석¹^,^†, 서승모^*

Computational Complexity of BiCGstab(l) in Multi-Level Fast Multipole Method(MLFMM) and Efficient Choice of l

Hyunsoo Lee¹, Jae-Won Rim¹, Il-Suek Koh¹^,^†, Seung-Mo Seo^*

Author Information & Copyright ▼

¹인하대학교 전자공학과

^*국방과학연구소

¹Department of Electronic Engineering, Inha University

^*Agency for Defense Development

^†Corresponding Author: Il-Suek Koh (e-mail: ikoh@inha.ac.kr)

© Copyright 2019 The Korean Institute of Electromagnetic Engineering and Science. This is an Open-Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/4.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Received: Dec 06, 2017; Revised: Feb 08, 2018; Accepted: Feb 12, 2018

Published Online: Mar 31, 2018

요약

MoM은 대표적인 적분방정식기반 full-wave simulation 방법이며, 이는 MLFMM 방법을 적용하여 효율적으로 계산될 수 있다. MoM 또는 MLFMM 방법에서 대규모 산란체 표면전류를 계산하는 과정에는 주로 반복법들이 사용된다. 이 가운데 BiCGstab(l)은 l값이 증가할수록 반복횟수는 줄어들지만, 반복당 수행되는 연산횟수가 증가하는 특징이 있다. 본 논문에서는 MLFMM 방법에 적용된 BiCGstab(l) 반복법의 l값에 따른 수렴속도와 연산량을 분석한 후, 효율적인 l값을 제안한다.

Abstract

The method of moments(MoM) is one of the most popular integral-equation-based full-wave simulation methods, and the multi-level fast multipole method(MLFMM) algorithm can be used for its efficient calculation. When calculating the surface current on the large scatterer in the MoM or MLFMM, iterative methods for the final matrix inversion are used. Among them, BiCGstab(l) has been widely adopted due to its good convergence rate. The number of iterations can be reduced when l becomes larger, but the number of operations per iteration is increased. Herein, we analyze the computational complexity of BiCGstab(l) in the MLFMM method and propose an optimum choice of l.

Keywords: BiCGstab(l); MLFMM; Iterative Method; Scattering

Ⅰ. 서 론

전자파 산란해석 수치해석방법 중 MoM(Method of Moments)은 full-wave simulation의 대표적인 방법이다. MoM 방법은 적분방정식을 차분화하여 최종 행렬 방정식을 얻은 후, 이를 풀어 표면전류를 구한다^[1]. 그러므로 MoM 방법의 수치복잡도는 일반적으로 행렬 방정식의 해를 구하는 알고리듬에 의해 결정된다. 행렬크기가 N이고 반복법(iterative method)을 사용하는 경우, MoM 방법의 수치복잡도는 O(N²)로 알려져 있다.

전자파해석에 일반적으로 사용되는 반복법으로 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(N²)은 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 은 각 반복과정에서 필요한 연산들의 횟수를 보여준다. 여기서 K_AXPY, K_DOT, K_MV는 각각 반복과정 당 AXPY, DOT, MV의 연산들의 사용횟수를 나타낸다. 각 연산들의 정확한 연산량은 행렬크기 N에 비례하나 정확하게 예측하기 어렵다. 예를 들어, MLFMM의 MV 연산인 경우 점근적(asymptotic) 연산량은 O(NlogN)로 알려져 있다^[5]～^[7]. 그러므로 AXPY 및 DOT 연산에도 점근적 연산량을 사용하고, 두 연산 모두 O(N)로 알려져 있다. 특정한 산란 문제의 반복횟수(N_I)를 알 수 있으면 총 점근적 연산량(N_T)를 다음과 같이 구할 수 있다.

N T = N I × K A X P Y + K D O T × N + K M V × N log N

(1)

표 1. | Table 1. BiCGstab(l) 반복법에서 반복당 AXPY, DOT, MV 연산들의 사용 횟수와 메모리 사용량^[3] | Required numbers per each iteration for AXPY, DOT, MV, and storage requirement in BiCGstab (l).

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

Download Excel Table

식 (1)에서 N_I는 산란문제에 따라 달라진다. 본 논문에서는 3가지 예제에 대해 N_I를 구한다. 그림 1(a)～(c)는 고려하는 산란문제들을 보여준다. 그림 1(a)는 작은 두 산란체(박스와 구)의 상호작용인 경우이다. 그림 1(b)는 하나의 산란체이나 입사파가 산란체의 뽀족한 부분으로 입사하여 상호작용이 상대적으로 많은 경우이다. 그림 1(c)는 보다 크고 일반적인 형상을 지닌 산란체 경우이다. 주파수는 모두 2 GHz로 가정하고, 메시 개수와 입사각, 편파 등은 표 2에 나타내었다. 그림 1은 산란체의 형상 및 반복법으로 계산된 표면전류도 함께 보여준다.

그림 1. | Fig. 1. 고려하는 산란문제들 | Considered scattering geometries.

Download Original Figure

표 2. | Table 2. 산란해석 파라미터 | Parameters for considered scattering problems.

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.

Download Excel Table

Ⅲ. 결과분석

그림 2는 그림 1(a) 산란문제에 적용된 다양한 l값에 따른 BiCGstab(l) 반복법 수렴곡선을 보여준다. l=1은 전통적인 BiCGstab 방법이다. 앞서 언급한 바와 같이, l이 클수록 수렴성이 좋아진다. 그림 3은 그림 1(a)～그림 1(c) 산란문제들의 총 반복횟수(N_I)를 l값에 관한 그래프를 보여준다. 그림 3에서 보듯이, BiCGstab(l) 반복법은 l값이 증가할수록 N_I가 감소한다. 그러나 표 1에서 보듯이 l값이 증가할수록 K_AXPY, K_DOM, K_MV도 함께 증가하기 때문에, 식 (1)에서 N_I가 감소하더라도 N_T는 N_I만큼 효과적으로 감소하지 않는다. 뿐만 아니라, 표 1에서 보듯이, l값이 증가할수록 메모리 사용량도 증가하기 때문에 효율적인 l값의 선택이 중요하다. 그림 4는 그림 1(a)～그림 1(c)의 산란문제들에 관하여 식 (1)에 의해 계산된 총 점근적 연산량(N_T)을 보여준다. 비교를 위해 결과들은 l=1일 때의 연산량으로 정규화 하였다. 그림 4에서 보듯이 l=2～3의 근방에서 모든 결과들의 N_T가 국소값(local minimum)을 가짐을 알 수 있다. N_T가 다시 증가하는 이유는 K_AXPY와 K_DOT가 l²에 비례하기 때문이다.

그림 2. | Fig. 2. 의 산란문제에 관한 BiCGstab(l) 반복법의 l값에 따른 수렴곡선 | Convergence rates of BiCGstab(l) for scattering problem in .

Download Original Figure

그림 3. | Fig. 3. ～의 산란문제들에 관한 BiCGstab(l) 반복법의 l값에 따른 반복 횟수 | Iteration numbers of BiCGstab(l) for scattering problems in ～.

Download Original Figure

그림 4. | Fig. 4. ～의 산란문제들에 관한 l=1일 때의 연산량으로 정규화된 총 점근적 연산량 | Asymptotic computational complexity for scattering problems in ～. The results are normalized by the complexity for l=1.

Download Original Figure

산란체의 전기적 크기가 매우 클 경우에는 AXPY와 DOT의 연산에 비하여 MV의 연산이 총 연산량(N_T)에 주된 영향을 준다. 그러므로 MV만을 고려하여 총 연산량(N_T)을 예측할 수 있으며, 이 경우에 근사화된 총 연산량은 그림 5에 보여진다. 마찬가지로 결과들은 l=1일 때의 연산량으로 정규화되었다. 그림 5에서 보듯이, l=2～3일 경우 총 연산량은 l=1을 사용한 경우에 비하여 55～70 % 정도 줄어든다. 그러나 l값을 계속 증가시켜도 총 연산량은 현저히 개선되지는 않는 것을 알 수 있다. 그러므로 l= 2～3을 선택하면 BiCGstab(l) 반복법의 연산량과 메모리 사용량을 최적으로 사용할 수 있다.

그림 5. | Fig. 5. 행렬-벡터 곱(MV)만을 고려한 경우, ～의 산란문제들에 관한 l=1일 때의 연산량으로 정규화된 총 점근적 연산량 | Asymptotic computational complexity for scattering problems in ～, considering MV operation only. The results are normalized by the complexity for l=1.

Download Original Figure

Ⅳ. 결 론

대규모 산란체의 산란해석 문제에는 반복법 기반의 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) 반복법의 최적이 선택이 된다.

Acknowledgements

이 연구는 국방과학연구소의 연구비 지원으로 수행되었음. (계약번호: UD170004FD)

References

[1].

R. F. Harrington, Field Computation by Moment Methods, Wiley-IEEE Press, 1993.

[2].

Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed. SIAM, 2003.

[3].

G. L. Sleijpen, D. R. Fokkema, “BiCGstab(l) for linear equations involving unsymmetric matrices with complex spectrum,” Electronic Transactions on Numerical Analysis, vol. 1, no. 11, pp. 11-32, 2000.

[4].

E. Topsakal, R. Kindt, K. Sertel, and J. Volakis, “Evaluation of the BICGSTAB(l) algorithm for the finite-element/boundary-integral method,” IEEE Antennas and Propagation Magazine, vol. 43, no. 6, pp. 124-131, Dec. 2001.

[5].

W. C. Chew, E. Michielssen, J. M. Song, and J. M. Jin, Fast and Efficient Algorithm in Computational Electromagnetics, Artech House, 2001.

[6].

O. Ergul, L. Gurel, The Multilevel Fast Multipole Algorithm(MLFMA) for Solving Large-scale Computational Electromagnetics Problems, John Wiley & Sons, 2014.

[7].

W. C. Gibson, The Method of Moments in Electromagnetics, 2nd ed. CRC Press, 2014.