In this paper, we analyze a method known as polynomial frame approximation for approximating smooth, multivariate functions defined on irregular domains in @math dimensions, where @math can be arbitrary. This method is simple, and relies only on orthogonal polynomials on a bounding tensor-product domain. In particular, the domain of the function need not be known in advance. When restricted to a subdomain, an orthonormal basis is no longer a basis, but a frame. Numerical computations with frames present potential difficulties, due to the near-linear dependence of the finite approximation system. Nevertheless, well-conditioned approximations can be obtained via regularization; for instance, truncated singular value decompositions. We comprehensively analyze such approximations in this paper, providing error estimates for functions with both classical and mixed Sobolev regularity, with the latter being particularly suitable for higher-dimensional problems. We also analyze the sample complexity of the approximation for sample points chosen randomly according to a probability measure, providing estimates in terms of the Nikolskii-type inequality for the domain. For a large class of nontrivial domains, we show that the sample complexity for points drawn from the uniform measure is quadratic in the dimension of the polynomial space, independently of @math .
The idea of approximating a function on an irregular domain by using an orthogonal basis on a tensor-product domain was considered within the context of embedded or fictitious domain methods in numerical PDEs @cite_3 (see also @cite_22 ). So-called or were studied in detail in @cite_44 @cite_30 . Applications to surface parametrization and numerical PDEs in complex geometries were considered in @cite_30 and @cite_6 @cite_8 @cite_31 respectively. Our work can be considered an extension of @cite_12 from the univariate to the multivariate setting, although we use algebraic as opposed to trigonometric polynomials since these are more common in applications such as UQ.
@cite_30 @cite_22 @cite_8 @cite_3 @cite_6 @cite_44 @cite_31 @cite_12
2138286512 1971181547 2080219236 2041410208 2036740708 2066313543 2113499611
We present a new method for construction of high-order parametrizations of surfaces: starting from point clouds, the method we propose can be used to produce full surface parametrizations (by sets of local charts, each one representing a large surface patch - which, typically, contains thousands of the points in the original point-cloud) for complex surfaces of scientific and engineering relevance. The proposed approach accurately renders both smooth and non-smooth portions of a surface: it yields super-algebraically convergent Fourier series approximations to a given surface up to and including all points of geometric singularity, such as corners, edges, conical points, etc. In view of their C^ smoothness (except at true geometric singularities) and their properties of high-order approximation, the surfaces produced by this method are suitable for use in conjunction with high-order numerical methods for boundary value problems in domains with complex boundaries, including PDE solvers, integral equation solvers, etc. Our approach is based on a very simple concept: use of Fourier analysis to continue smooth portions of a piecewise smooth function into new functions which, defined on larger domains, are both smooth and periodic. The ''continuation functions'' arising from a function f converge super-algebraically to f in its domain of definition as discretizations are refined. We demonstrate the capabilities of the proposed approach for a number of surfaces of engineering relevance. A simple way to solve a partial differential equation in a non-rectangular domain @W is to embed the domain in a rectangle B and solve the problem (more easily) in the rectangle. To apply a Fourier spectral method on the rectangle, it is necessary to extend the inhomogeneous term in the PDE, f(x,y), to B in such a way that the extended function g(x,y) is periodic and infinitely differentiable, and yet is equal to f(x,y) everywhere in the irregular domain @W. If the boundary of @W, @[email protected], is defined as the zero isoline of a function @F(x,y), then a suitable extension is g(x,y)=f(x,y)H([email protected](x,y) constant) where H is a smoothed approximation to the step function which is defined in the main text. We introduce a new methodology for the numerical solution of Partial Differential Equations in general spatial domains: our algorithms are based on the use of the well-known Alternating Direction Implicit (ADI) approach in conjunction with a certain "Fourier continuation" (FC) method for the resolution of the Gibbs phenomenon. Unlike previous alternating direction methods of order higher than one, which can only deliver unconditional stability for rectangular domains, the present high-order algorithms possess the desirable property of unconditional stability for general domains; the computational time required by our algorithms to advance a solution by one time-step, in turn, grows in an essentially linear manner with the number of spatial discretization points used. In this paper we demonstrate the FC-AD methodology through a variety of examples concerning the Heat and Laplace Equations in two and three-dimensional domains with smooth boundaries. Applications of the FC-AD methodology to Hyperbolic PDEs together with a theoretical discussion of the method will be put forth in a subsequent contribution. The numerical examples presented in this text demonstrate the unconditional stability and high-order convergence of the proposed algorithms, as well the very significant improvements they can provide (in one of our examples we demonstrate a one thousand improvement factor) over the computing times required by some of the most efficient alternative general-domain solvers. We present a Fourier continuation (FC) algorithm for the solution of the fully nonlinear compressible Navier-Stokes equations in general spatial domains. The new scheme is based on the recently introduced accelerated FC method, which enables use of highly accurate Fourier expansions as the main building block of general-domain PDE solvers. Previous FC-based PDE solvers are restricted to linear scalar equations with constant coefficients. The FC methodology presented in this text thus constitutes a significant generalization of the previous FC schemes, as it yields general-domain FC solvers for nonlinear systems of PDEs. While not restricted to periodic boundary conditions and therefore applicable to general boundary value problems on arbitrary domains, the proposed algorithm inherits many of the highly desirable properties arising from rapidly convergent Fourier expansions, including high-order convergence, essentially spectrally accurate dispersion relations, and much milder CFL constraints than those imposed by polynomial-based spectral methods-since, for example, the spectral radius of the FC first derivative grows linearly with the number of spatial discretization points. We demonstrate the accuracy and optimal parallel efficiency of the algorithm in a variety of scientific and engineering contexts relevant to fluid-dynamics and nonlinear acoustics. The range of Fourier methods can be significantly increased by extending a nonperiodic function f(x) to a periodic function f? on a larger interval. When f(x) is analytically known on the extended interval, the extension is straightforward. When f(x) is unknown outside the physical interval, there is no standard recipe. Worse still, like a radarless aircraft groping through fog, the algorithm may wreck on the “mountain-in-fog” problem: a function f(x) which is perfectly well behaved on the physical interval may very well have singularities in the extended domain. In this article, we compare several algorithms for successfully extending a function f(x) into the “fog” even when the analytic extension is singular. The best third-kind extension requires singular value decomposition with iterative refinement but achieves accuracy close to machine precision. A new PDE solver was introduced recently, in Part I of this two-paper sequence, on the basis of two main concepts: the well-known Alternating Direction Implicit (ADI) approach, on one hand, and a certain ''Fourier Continuation'' (FC) method for the resolution of the Gibbs phenomenon, on the other. Unlike previous alternating direction methods of order higher than one, which only deliver unconditional stability for rectangular domains, the new high-order FC-AD (Fourier-Continuation Alternating-Direction) algorithm yields unconditional stability for general domains-at an O(Nlog(N)) cost per time-step for an N point spatial discretization grid. In the present contribution we provide an overall theoretical discussion of the FC-AD approach and we extend the FC-AD methodology to linear hyperbolic PDEs. In particular, we study the convergence properties of the newly introduced FC(Gram) Fourier Continuation method for both approximation of general functions and solution of the alternating-direction ODEs. We also present (for parabolic PDEs on general domains, and, thus, for our associated elliptic solvers) a stability criterion which, when satisfied, ensures unconditional stability of the FC-AD algorithm. Use of this criterion in conjunction with numerical evaluation of a series of singular values (of the alternating-direction discrete one-dimensional operators) suggests clearly that the fifth-order accurate class of parabolic and elliptic FC-AD solvers we propose is indeed unconditionally stable for all smooth spatial domains and for arbitrarily fine discretizations. To illustrate the FC-AD methodology in the hyperbolic PDE context, finally, we present an example concerning the Wave Equation-demonstrating sixth-order spatial and fourth-order temporal accuracy, as well as a complete absence of the debilitating ''dispersion error'', also known as ''pollution error'', that arises as finite-difference and finite-element solvers are applied to solution of wave propagation problems. An effective means to approximate an analytic, nonperiodic function on a bounded interval is by using a Fourier series on a larger domain. When constructed appropriately, this so-called Fourier extension is known to converge geometrically fast in the truncation parameter. Unfortunately, computing a Fourier extension requires solving an ill-conditioned linear system, and hence one might expect such rapid convergence to be destroyed when carrying out computations in finite precision. The purpose of this paper is to show that this is not the case. Specifically, we show that Fourier extensions are actually numerically stable when implemented in finite arithmetic, and achieve a convergence rate that is at least superalgebraic. Thus, in this instance, ill-conditioning of the linear system does not prohibit a good approximation. In the second part of this paper we consider the issue of computing Fourier extensions from equispaced data. A result of (SIAM Rev. 53(2):308---318, 2011) states that no method for this problem can be both numerically stable and exponentially convergent. We explain how Fourier extensions relate to this theoretical barrier, and demonstrate that they are particularly well suited for this problem: namely, they obtain at least superalgebraic convergence in a numerically stable manner.