簡易檢索 / 詳目顯示

研究生: 張耀文
Chang, Yao-Wen
論文名稱: An Experimental Performance Study of Polynomial Preconditioner in PCG
An Experimental Performance Study of Polynomial Preconditioner in PCG
指導教授: 黃聰明
Huang, Tsung-Ming
口試委員: 陳建隆
Chern, Jann-Long
林敏雄
Lin, Matthew M.
黃聰明
Huang, Tsung-Ming
口試日期: 2022/01/25
學位類別: 碩士
Master
系所名稱: 數學系
Department of Mathematics
論文出版年: 2022
畢業學年度: 110
語文別: 英文
論文頁數: 43
英文關鍵詞: Graph Laplacian, PCG, Polynomial Preconditioner
研究方法: 實驗設計法
DOI URL: http://doi.org/10.6345/NTNU202200194
論文種類: 學術論文
相關次數: 點閱:117下載:7
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • Solving laplacian system is common in the field of computer science nowadays. Preconditioner is an essential tool while solving linear system with indirect method. It may bring significant improvements to number of iterations, CPU time, and the errors. In this work we will start with graph laplacian, matrix splitting and approximation theories to get some polynomial preconditioners, and investigate the performance in the changes of different parameters in PCG(Preconditioned Conjugate Gradient) method mainly by experiments. We will show the experimental result as conclusion for the purpose of accelerating the iteration in future works.

    1 Introduction 1 2 Graph Laplacian 3 2.1 Graph Laplacian 4 2.2 Laplacian System 8 3 Preconditioner 9 4 Other Choices 12 4.1 Weighted Preconditioners 12 4.2 Splittings 13 4.3 Different Polynomials 13 5 Experiments 15 5.1 Neumann Series 18 5.2 Weighted 24 5.3 Chebyshev Polynomial 32 5.4 Bernstein Polynomial 33 6 Summary 36

    O. G. Johnson, C. A. Micchelli and G. Paul, Polynomial Preconditioners for Conjugate Gradient Calculations, Society for Industrial and Applied Mathematics, SIAM Journal on Numerical Analysis, Vol. 20, No. 2 (1983), pp. 362-376.

    A. K. Nandi, Iterative Methods for Linear and Multilinear Systems Based on Splittings, Birla Institute of Technology and Science, Pilani.

    H. Wang, S. Xiang, On the convergence rates of Legendre approximation, Math. Computation, 81 (2012), pp. 861-877.

    J.-J. Climent, N. Thome and Y. Wei, A geometrical approach on generalized inverses by Neumann-type series, Linear Algebra and its Applications, 332–334 (2001), pp. 533-540.

    M.H. ,Mudde (2017), Chebyshev approximation, Master Thesis, University of Groningen, Faculty of Science and Engineering, Groningen.

    Weisstein, Eric W., Legendre Polynomial, MathWorld, https://mathworld.wolfram.com/LegendrePolynomial.html

    J. R Shewchuk (1994), An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, Technical Report, Carnegie Mellon University, USA.

    Y. Saad (2003), Iterative Method for Sparse Linear System 2nd, Society for Industrial and Applied Mathematics.

    A. Pyzara, B. Bylina and J. Bylina, The influence of a matrix condition number on iterative methods' convergence, Federated Conference on Computer Science and Information Systems (FedCSIS) (2011), pp. 459-464.

    O. Leary, P. Dianne (1991), Yet another polynomial preconditioner for the conjugate gradient algorithm, Linear Algebra and its Applications, pp. 377-388.

    G. Mayer, On the convergence of the Neumann series in interval analysis, Linear Algebra and its Applications 65 (1985), pp. 63-70.

    H. B. Jebreen, Y. Chalco-Cano (2018), An Improved Computationally Efficient Method for Finding the Drazin Inverse, Discrete Dynamics in Nature and Society.

    M. N. Bernstein (2020), it The Graph Laplacian, https://mbernste.github.io/posts/laplacian_matrix/

    K. C. Das, The Laplacian spectrum of a graph, Computers & Mathematics with Applications, Volume 48, Issues 5-6 (2004), pp. 715-724.

    N. K. Vishnoi, Lx = b Laplacian Solvers and Their Algorithmic Applications, Foundations and Trends in Theoretical Computer Science, Vol. 8, Nos. 1-2 (2012), pp. 1-141

    M. W. Mahoney, L. Orecchia, and N. K. Vishnoi, A spectral algorithm for improving graph partitions, Journal of Machine Learning Research, vol. 13 (2012), pp. 2339–2365.

    R. Bisseling, J.G. Vors t(1988), Parallel LU Decomposition on a Transputer Network, Shell Conference.

    Y. Saad (1984), Practical Use of Polynomial Preconditionings for the Conjugate Gradient Method, SIAM J. Sci. and Stat. Comput., 6(4), pp. 865-881.

    R.T. Farouki (2012), The Bernstein polynomial basis: A centennial retrospective, Comput. Aided Geom. Des., 29, pp 379-419.

    Y. Saad (1981), Krylov Subspace Methods for Solving Large Unsymmetric Linear Systems, Department of Computer Science, University of Illinois at Urbana-Champaign.

    Y. Saad and M. Sosonkina (2001), Enhanced preconditioners for large sparse least squares problems, Minnesota Supercomputer Institute, University of Minnesota, Minneapolis, MN.

    K. Wu, Y. Saad, and A. Stathopoulos (1998), Inexact Newton Preconditioning Techniques for Eigenvalue Problems, Minnesota Supercomputer Institute, University of Minnesota, Minneapolis, MN, ETNA, vol. 7, pp. 202-214.

    O. Axelsson, G. Lindskog, On the rate of convergence of the preconditioned conjugate gradient method, Numerische Mathematik 48.5 (1986), pp. 499-523.

    G. H. Golub, Q. Ye, Inexact preconditioned conjugate gradient method with inner-outer iteration, SIAM Journal on Scientific Computing 21.4 (1999), pp. 1305-1320.

    L. Y. Kolotilina, A. Y. Yeremin, Factorized Sparse Approximate Inverse Preconditionings I. Theory, SIAM J. Matrix Anal. Appl., 14(1), pp. 45-58.

    下載圖示
    QR CODE