This thesis discusses parallel implementation of dual iterative substructuring methods, particularly FETI-DP method and enhanced penalty method. We optimize the algorithm for the enhanced penalty method and compare its performance with the FETI-DP method, which is the most renowned substructuring method. The substructuring method divides the domain into local subdomains and allocates each of them into parallel processors to solve the local problems. Enhanced penalty method adds a strong continuity constraint to the FETI-DP method by measuring the difference on the edge, which we call the penalty term. This additional term accelerates the convergence, but produces more data communication between processors. It is not easy to compare the performance between the two methods. However, it is obvious that optimizing the communication routine will be crucial in the performance of the enhanced penalty method.
Here, we present the process of optimizing communication routines in the enhanced penalty method. Our analysis shows that calculating the global inner product is the most expensive communication step in this algorithm and a parallel computer with effective network and memory system that can gather the values from all processor simultaneously is needed for efficient implementation. Overall, we conclude that FETI-DP method is recommended when the subdomain problem size is small and enhanced penalty method becomes more effective when the subdomain problem size is above certain level. Both method turn out to be efficient solvers for the elliptic partial differential equation when parallel computer is available. But the choice among FETI-DP and enhanced penalty method must be made carefully considering the number of processors, computing power, and network performance of the parallel computer. Particularly, for our test problem in two dimensional domain, enhanced penalty method becomes more efficient when the local problem size becomes larger than 128 $\times$ 128 in 2 dimensional problem in the Gaia system.
쌍대 영역분할 반복해법은 편미분방정식을 푸는 병렬 알고리즘으로서 문제의 정의역을 분할한 다음 각 부분 영역에서의 국소문제를 병렬컴퓨터에 할당하여 풀 수 있는 해법이다. 이를 병렬컴퓨터에서 구현할 경우 포아송문제를 비롯한 편미분방정식의 해를 빠르게 구해낼 수 있다. 영역분할법은 나누어진 영역 사이의 경계부분에서 국소문제들 간의 관계를 주는 방법에 따라 나눠진다. 가장 널리 알려진 FETI-DP 방법은 Lagrange 승수를 이용하여 경계에서 연속한 조건을 주는 방법으로서, 그 효율성과 안정성이 검증되어 있다. 본 연구에서는 더 강한 연속 조건을 줌으로써 FETI-DP 방법을 개선한 penalty 방법을 병렬컴퓨터에서 구현하여 그 효율성을 비교해보고자 한다.
병렬 알고리즘의 총 구현시간은 계산시간과 병렬컴퓨터간의 통신시간으로 나누어질 수 있다. 강화된 penalty 방법은 더해진 penalty 함수 부분이 연속 조건을 강하게 줌으로써 FETI-DP 방법에 비해 더 빠르게 수렴한다. 하지만 빠른 수렴성으로 인해 계산량이 줄어드는 반면, 그로인한 통신량이 증가하게 된다. 따라서 통신부분의 알고리즘을 구현하는 병렬컴퓨터의 네트워크에 맞게 최적화시키는 것이 강화된 penalty 방법의 효율성을 좌우하게 된다.
이 논문은 강화된 penalty 방법의 안정성을 검증하고, 통신부분을 최적화시키는 과정을 분석해보았으며, 그 결과를 FETI-DP 방법과 비교해 보았다. 강화된 penalty 방법의 빠른 수렴성을 나타내는 strongly scalable한 특징과 함께 $O(h^2)$ 의 안정적인 수렴형태를 확인할 수 있었다. 효율성에 있어서는, 병렬영역에서 문제크기와 관련된 $H/h$ 가 작을 경우에는 FETI-DP 방법이 더 효율적이었지만, 문제 크기가 일정 크기 이상이 되면 강화된 penalty 방법이 더 효과적이게 된다. 특히 KISTI의 Gaia 컴퓨터에서 포아송 방정식을 풀 경우, $H/h$ 가 128 이상이 될 때부터 강화된 penalty 방법이 FETI-DP 방법보다 더 빠르게 해를 구할 수 있다.
