Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Computational Science, Engineering & Technology Series
COMPUTATIONAL METHODS FOR ENGINEERING TECHNOLOGY
Edited by: B.H.V. Topping and P. Iványi
On a Class of Inexact Type Methods Based on Generic Approximate Sparse Inverses Multigrid Method for Solving Nonlinear Partial Differential Equations
G.A. Gravvanis and C.K. Filelis-Papadopoulos
Department of Electrical and Computer Engineering, School of Engineering, Democritus University of Thrace, Xanthi, Greece
G.A. Gravvanis, C.K. Filelis-Papadopoulos, "On a Class of Inexact Type Methods Based on Generic Approximate Sparse Inverses Multigrid Method for Solving Nonlinear Partial Differential Equations", in B.H.V. Topping and P. Iványi, (Editor), "Computational Methods for Engineering Technology", Saxe-Coburg Publications, Stirlingshire, UK, Chapter 8, pp 191-221, 2014. doi:10.4203/csets.35.8
Keywords: nonlinear partial differential equations, inexact Newton’s method, inexact Broyden’s method, multigrid method, generalized approximate sparse inverses, finite difference method, inexact Jacobian-free Newton-multigrid, full approximation scheme, Krylov accelerated multigrid methods.
Many engineering and scientific problems are described by non-linear partial differential equations. This category of equations represents a large class of commonly occurring problems in Mathematical Sciences and Engineering. The numerical solution of nonlinear Partial Differential Equations requires a linearization method such as Inexact Newton’s or Inexact Broyden’s method and an efficient solver to compute the approximate solution in each step. Multigrid methods are considered efficient methods of near optimal complexity and in conjunction with Approximate Sparse Inverses have been experimentally proven to be effective for various classes of problems. Herewith, the Generic Approximate Sparse Inverse, based on Approximate Inverse Sparsity patterns, is used in conjunction with the multigrid method as an inner solver for Inexact Newton’s and Inexact Broyden’s method. Moreover, two new schemes based on Inexact Newton’s and Inexact Broyden’s method, in conjunction with the multigrid method based on Generic Approximate Sparse Inverses, are proposed. In the proposed schemes the approximate inverse is explicitly computed during the first iteration and is then updated for the following iterations until convergence. The update of the approximate inverse is carried out with a modified version of the Broyden’s formula targeting only the nonzeros. Furthermore, the Jacobian-Free Newton-Multigrid in conjunction with Generic Approximate Sparse Inverses is presented. The Jacobian- Free Newton-Multigrid method does not require the Jacobian matrix explicitly, instead the Jacobian ‘times’ a vector is approximated by finite differences. Moreover, the Full Approximation Scheme for non-linear systems of equations in conjunction with Generic Approximate Sparse Inverses is presented. The Full Approximation Scheme applies multigrid techniques to the solution of systems of non-linear equations. Implementation details and discussions concerning the various proposed schemes are provided. In order to increase robustness of the multigrid algorithms, the proposed schemes are accelerated with the use of a Krylov subspace iterative method. Moreover, the proposed schemes are compared by solving the Bratu problem and numerical results concerning the performance and convergence behaviour are given.
purchase the full-text of this chapter (price £20)