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.

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.