臺灣博碩士論文加值系統

本文討論解 Poisson's equation 的數值解在有界的定義域上，透過隨機漫步的方法，造出一種新的預處理 (precondition) 並且使用圖形處理器來加速此方程的數值解，而疊代法使用 Conjugate Gradient 方法並與現有的預處理方法做比較的有 ILU0，multigrid 在 CPU 上，其它還有對此新的預理討論收斂速度，以及給出一些改良策略。

This paper discuss to solve numerical solution of Poisson's equation on finite domain and create a new precondition with random walk method and use graphic process unit to accelerate numerical solution of this equation. At iteration method is used by Conjugate Gradient method and compare with ILU0 and Multigrid method on CPU, other discuss this new precondition has convergence rate and give some improvement strategy.

Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 簡介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 隨機漫步方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 gambler’s ruin problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Laplace’s equation in 1-D . . . . . . . . . . . . . . . . . . . . . 5
2.2 Central difference to random walks in 2-D . . . . . . . . . . . . . . . . . 6
3 一些改良的策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 更進一步的改良策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5 數值結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.1 實驗環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 product and summation . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.3 special Block LDU decompotion(SBLDU) and ilu0 . . . . . . . . . . . . 30
5.3.1 Breakdown analysis. . . . . . . . . . . . . . . . . . . . . . . . . 30
5.4 Di^(-1) partial calculate and multigrid . . . . . . . . . . . . . . . . . . . . . 32
5.4.1 Breakdown analysis . . . . . . . . . . . . . . . . . . . . . . . . 32
5.5 Modify transition matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.6 Eliminate low expect . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.7 期望值分佈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6 結論與未來展望 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7 附錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
參考文獻. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

[1] Yousef Saad. Iterative Methods for Sparse Linear Systems. SIAM, 2003.
[2] Rudi Helfenstein and Jonas Koko. Parallel preconditioned conjugate gradient algo-
rithm on GPU. Journal of Computational and Applied Mathematics, 236:3584–3590,
2012.
[3] Gundolf Haase, Manfred Liebmann, Craig C. Douglas, and Gernot Plank. A Parallel
Algebraic Multigrid Solver on Graphics Processing Units. Volume 5938 of Lecture
Notes in Computer Science:38V47, 2010.
[4] Craig C. Douglas, Hyoseop Lee, Gundolf Haase, Manfred Liebmann, Victor M. Calo,
and Nathan Collier. Parallel Algebraic Multigrid Method with GP-GPU Hardware
Acceleration. Journal of Computational and Applied Mathematics.
[5] Charles M. Grinstead and J. Laurie Snell. Introduction to Probability. American
Mathematical Society, 1997.