초록 ▼

조밀한 선형연립방정식을 푸는 데에는 LU 분해와 같은 아주 강력한 직접적 방법이 있다. 그러나 편미분방정식을 유한차분법이나 유한요소법으로 근사할때 생성되는 차수가 크고 드문성을 지닌 선형연립방정식에는 적은 기억용량과 연산량을 필요로 하는 반복적인 방법들이 많이 사용된다. 대칭이고 양정치인 행렬에 대하여는 강력하면서도 효율적인 CG 방법이 있다. 따라서 비대칭인 행렬을 갖는 선형연립방정식을 푸는많은 반복적인 방법이 알려져 왔다. 이 방법은 크게 최소 나머지(MR) 방법과 쌍직교(BO)방법으로 나누어 진다. 최근

조밀한 선형연립방정식을 푸는 데에는 LU 분해와 같은 아주 강력한 직접적 방법이 있다. 그러나 편미분방정식을 유한차분법이나 유한요소법으로 근사할때 생성되는 차수가 크고 드문성을 지닌 선형연립방정식에는 적은 기억용량과 연산량을 필요로 하는 반복적인 방법들이 많이 사용된다. 대칭이고 양정치인 행렬에 대하여는 강력하면서도 효율적인 CG 방법이 있다. 따라서 비대칭인 행렬을 갖는 선형연립방정식을 푸는많은 반복적인 방법이 알려져 왔다. 이 방법은 크게 최소 나머지(MR) 방법과 쌍직교(BO)방법으로 나누어 진다. 최근에는 쌍직교 방법의 불규칙적인 수렴성을 보완할 목적으로 쌍직교(BO) 방법과 최소 나머지 (MR) 방법을 융합하는 혼성 반복적인 방법이 제안되어졌다.본 연구의 목적은 혼성 반복적인 방법인 BiCGSTAB(ℓ)에 대응되는 효율적인 병렬방법을 개발하는 것이다. 혼성 반복적인 방법들은 lanczos 방법에 기초를 두기 때문에, 먼저 lanczos/orthodir를 변형시켜 병렬성이 더 많은 block-updated lanczos/orthodir를 개발하였다. 이 방법은 불규칙적인 수렴성을 가지므로 오차에 민감한다. 따라서 비교적 정확한근사값을 얻기 위하여는 preconditioning을 필요로 한다. 그리고 동시점을 줄임으로써 병렬성을 높이는 어떤 변형된 BiCGSTAB과 BiCGSTAB(ℓ)을 개발하였다. 더우기 재시작기법을 사용함으로써, 이들의 실행속도를 증가시킬 수 있었다. 위에서 언급한 변형된 혼성반복적인 방법에 대한 병렬화를 위하여, 이들 방법이 가지고 있는 중요한 연산인 행렬과 벡터의 곱 및 내적 연산에 대한 병렬 알고리즘을 소개하였다. 특히 Type A와 Type B로 불리워지는 2가지 종류의 병렬내적연산을 소개하고, 민감한 값으로 내적들을 가지는 반복적인방법들에는 type B가 type A보다 더 좋은 병렬 알고리즘임을 보였다. 또한 cray C90 컴퓨터에서의 수치적 실험을 통하여 병렬혼성방법의 효율성이 우수함을 보였다. 그리고 어떤 수렴조건을 만족하는 병렬혼성반복적인 방법들의 반복횟수가 사용되어질 CPU의 수에따라 변함을 알았다. 마지막으로 반복횟수가 CPU의 수에 무관한 병렬방법을 얻을 수가있으면 아주 바람직하다고 생각되고, 이에 대한 연구는 다음 연구에서 하겠다.

Abstract ▼

Direct methods such as Lu decomposition are very powerfulmethods solving dense linear systems. However, for large sparse linear systemsarising from FDM or FEM for the PDE(partial differential equation) problems, iterativemethods are commonly used rather than direct methods since iterati

Direct methods such as Lu decomposition are very powerfulmethods solving dense linear systems. However, for large sparse linear systemsarising from FDM or FEM for the PDE(partial differential equation) problems, iterativemethods are commonly used rather than direct methods since iterative methods requireless storages and arithmetic operations than direct methods. For linear systems withsymmetric positive definite matrices, there is a robust and efficient iterative methodcalled CG(conjugate gradient). So, many iterative methods for nonsymmetric linearsystems have been proposed by many scientists. There have been two types ofiterative methods for nonsymmetric problems called minimal residual(MR) methods(e.g.,GMRES) and biorthogonalization(BO) methods(e.g., lanczos methods) recently, hybriditerative methods which combine both minimal residual and biorthogonalization propertieshave been proposed for the purpose of remedying the irregular convergence behavior ofBO methods.The goal of this research is to develop efficient parallel algorithms correspondingto hybrid iterative methods BiCGSTAB and BiCGSTAB(ℓ). Since those hybridmethods are based on lanczos method, we first developed a block-updatedlanczos/orthodir method which has more parallelism than lanczos/orthodir. Because ofirregular convergence behavior, preconditioning needs to be done for this method to becompetitive with hybrid methods. We then have developed variants of BiCGSTAB andBiCGSTAB(ℓ) which increase parallelism by decreasing synchronization points.Furthermore, it was shown that their performance can be increased by using restartingtechnique. For the parallelization of these variants, we introduced how to parallelizematrix-vector products and inner products which are basic kernels of iterative methods.Two parallel inner products called type A and type B were presented in this paper.But it was seen that type B of parallel inner products is preferable to type A of thosefor iterative methods which contain sensitive values of inner products. Numericalexperiments showed that parallel hybrid methods preform efficiently on the CRAY C90and that the number of iterations for satisfying a convergence criterion depends on thenumber of processors to be used. Hence it would be so nice if we have parallelhybrid methods that have a constant iteration number onany number of processors.This research will be done in a furture work.

목차 Contents

• TABLE OF CONTENTS...7
• 1. Introduction...8
• 2. Block-updated variant of the Lanczos method...11
• 3. Parallel implementation of hybrid methods...14
• 4. Numerical results and Test conditions...23
• 5. Calculations...27
• References...29
• 자체평가서...32