Adaptive partition of unity methods for Chebyshev polynomial approximation and nonlinear additive Schwarz preconditioning
Date
2019
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
If a function is analytic on and around an interval, then Chebyshev polynomial interpolation provides spectral convergence. However, if the function has a singularity close to the interval, the rate of convergence is near unity. In these cases splitting the interval and using piecewise interpolation can accelerate convergence. Chebfun includes a splitting mode that finds an optimal splitting through recursive bisection, but the result has no global smoothness unless conditions are imposed explicitly at the breakpoints. We developed a new technique where we split the domain into overlapping intervals and use an infinitely smooth partition of unity to blend the local Chebyshev interpolants. ☐ We construct the partition of unity approximations with a simple divide-and-conquer algorithm similar to Chebfun’s splitting mode, which can be used to find an overlapping splitting adapted to features of the function. Our algorithm implicitly constructs the partition of unity over the subdomains, without the need of explicitly keeping track of neighboring subdomains. This allows us to use a partition of unity method within an adaptive framework. We applied this technique explicitly on given functions as well as to the solutions of singularly perturbed boundary value problems. ☐ The extension of the Chebfun technique to two-dimensional and three-dimensional functions on hyperrectangles has mainly focused on low-rank approximation. While this method is very effective for some functions, it is highly anisotropic and unacceptably slow for many functions of potential interest. We developed a method based on automatic recursive domain splitting, with a partition of unity to define the global approximation that is easy to construct and manipulate. Our experiments show it to be as fast as existing software for many low-rank functions, and much faster on other examples, even in serial computation. It is also much less sensitive to alignment with coordinate axes. We utilized the tree structure to develop fast algorithms for interpolation, integration and differentiation. In particular, we developed a fast and efficient scheme for arithmetically combining partition of unity approximations using the tree representations that would have not been possible with approximations represented with graphs. We took steps to develop approximations of functions on nonrectangular domains, by using least-squares polynomial approximations in a manner similar to Fourier extension methods, with promising results. ☐ The additive Schwarz method is usually presented as a preconditioner for a PDE linearization based on overlapping subsets of nodes from a global discretization. It has previously been shown how to apply Schwarz preconditioning to a nonlinear problem using subdomains with a shared global grid. We expand on these ideas by first replacing the original global PDE with the Schwarz overlapping problem, where each subdomain has an independent grid, whose unknowns do not need to be shared. This allows us to avoid restrictive-type updates since subdomains need to communicate only via interface interpolations. Our new preconditioner can be applied linearly or nonlinearly. In the latter case we solve nonlinear subdomain problems independently in parallel. With our new nonlinear preconditioned method, the frequency and amount of interprocess communication is greatly reduced compared to linearized preconditioning. Our method allows us to adapt to the features of a PDE solution, as shown in an extended application to the numerical solutions of fourth order tear film models, which are both stiff and highly nonlinear.
Description
Keywords
Chebyshev polynomials, Nonlinear preconditioning, Partition of unity