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)

go to the previous chapter
go to the next chapter
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)