Genetic programming for iterative numerical methods

Dominik Sobania1, Jonas Schmitt2, Harald Köstler2, Franz Rothlauf3
1Johannes Gutenberg-University Mainz, Mainz, Germany
2Friedrich Alexander University Erlangen-Nürnberg, Erlangen, Germany
3Johannes Gutenberg University Mainz, Mainz, Germany

Tóm tắt

AbstractWe introduce GPLS (Genetic Programming for Linear Systems) as a GP system that finds mathematical expressions defining an iteration matrix. Stationary iterative methods use this iteration matrix to solve a system of linear equations numerically. GPLS aims at finding iteration matrices with a low spectral radius and a high sparsity, since these properties ensure a fast error reduction of the numerical solution method and enable the efficient implementation of the methods on parallel computer architectures. We study GPLS for various types of system matrices and find that it easily outperforms classical approaches like the Gauss–Seidel and Jacobi methods. GPLS not only finds iteration matrices for linear systems with a much lower spectral radius, but also iteration matrices for problems where classical approaches fail. Additionally, solutions found by GPLS for small problem instances show also good performance for larger instances of the same problem.

Từ khóa


Tài liệu tham khảo

W.F. Ames, Numerical Methods for Partial Differential Equations (Academic press, 2014)

A. Amritkar et al., Recycling Krylov subspaces for CFD applications and a new hybrid recycling solver. J. Comput. Phys. 303, 222–237 (2015)

R. Barrett et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, Vol. 43 (SIAM, 1994)

D.S. Burke et al., Putting more genetics into genetic algorithms, in Evolutionary Computation 6.4 (1998), pp. 387–410

T.A. Davis, Direct Methods for Sparse Linear Systems, Vol. 2 (Society of Industrial and Applied Mathematics, 2006)

J.W. Demmel, Applied Numerical Linear Algebra, Vol. 56 (Society of Industrial and Applied Mathematics, 1997)

G.H. Golub, C.F. Van Loan, Matrix Computations, Vol. 3. (HU Press, 2012)

R.M. Gray, in Toeplitz and circulant matrices: a review (2006)

R.A. Horn, C.R. Johnson, Matrix Analysis, 2nd edn. (Cambridge University Press, Cambridge, 2012)

C. Johnson, Numerical Solution of Partial Differential Equations by the Finite Element Method (Courier Corporation, 2012)

W.M. Kahan, in Gauss–Seidel methods of solving large systems of linear equations (2002)

M. Keijzer, Improving symbolic regression with interval arithmetic and linear scaling, in European Conference on Genetic Programming (Springer, 2003), pp. 70–82

J.R. Koza, Genetic Programming Ii: Automatic Discovery of Reusable Programs (MIT Press, 1994)

J.R Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press, 1992)

R.G. Mahmoodabadi, H. Köstler, Genetic Programming Meets Linear Algebra: How Genetic Programming Can Be Used to Find Improved Iterative Numerical Methods, in Proceedings of the Genetic and Evolutionary Computation Conference Companion. GECCO ’17. Berlin, Germany: ACM (2017), pp. 1403–1406

D.J. Montana, Strongly typed genetic programming, in Evolutionary computation 3.2 (1995), pp. 199–230

K.W. Morton, D.F. Mayers, Numerical Solution of Partial Differential Equations: An Introduction (Cambridge university press, 2005)

R. Poli, W.B. Langdon, Nicholas Freitag McPhee. A field guide to genetic programming. (With contributions by J. R. Koza). Published via http://lulu.com (2008)

R. Poli, Nicholas Freitag McPhee. Parsimony Pressure Made Easy, in Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation. GECCO ’08. Atlanta, GA, USA: ACM (2008), pp. 1267–1274

H. Rittich, Extending and Automating Fourier Analysis for Multigrid Methods. Ph.D. thesis, University of Wuppertal, June (2017)

Y. Saad, Iterative Methods for Sparse Linear Systems, Vol. 82 (Society of Industrial and Applied Mathematics, 2003)

J. Schmitt, S. Kuckuk, H. Köstler, Constructing Efficient Multigrid Solvers with Genetic Programming, in Proceedings of the 2020 Genetic and Evolutionary Computation Conference. GECCO ’20. Cancún, Mexico: ACM (2020), pp. 1012–1020

G.D. Smith, Numerical Solution of Partial Differential Equations: Finite Difference Methods (Oxford university press, 1985)

R. Temam, Navier–Stokes Equations: Theory and Numerical Analysis, Vol. 343 (American Mathematical Soc., 2001)

L.N. Trefethen, D. Bau III, Numerical Linear Algebra, Vol. 50 (Society of Industrial and Applied Mathematics, 1997)

H.K. Versteeg, W. Malalasekera, An Introduction to Computational Fluid Dynamics: The Finite Volume Method (Pearson Education, 2007)

E.J. Vladislavleva, G.F. Smits, D.D. Hertog, Order of nonlinearity as a complexity measure for models generated by symbolic regression via pareto genetic programming, in IEEE Transactions on Evolutionary Computation 13.2 (2008), pp. 333–349

R. Wienands, W. Joppich, Practical Fourier Analysis for Multigrid Methods (CRC Press, 2004)

D.M. Young, Iterative Solution of Large Linear Systems (Elsevier, 2014)