An official website of the United States government
We review recent advances in algorithms for quadrature, transforms, differential equations and singular integral equations using orthogonal polynomials. Quadrature based on asymptotics has facilitated optimal complexity quadrature rules, allowing for efficient computation of quadrature rules with millions of nodes. Transforms based on rank structures in change-of-basis operators allow for quasi-optimal complexity, including in multivariate settings such as on triangles and for spherical harmonics. Ordinary and partial differential equations can be solved via sparse linear algebra when set up using orthogonal polynomials as a basis, provided that care is taken with the weights of orthogonality. A similar idea, together with low-rank approximation, gives an efficient method for solving singular integral equations. These techniques can be combined to produce high-performance codes for a wide range of problems that appear in applications.
more »
« less
A high-order meshless Galerkin method for semilinear parabolic equations on spheres
We describe a novel meshless Galerkin method for numerically solving semilinear parabolic equations on spheres. The new approximation method is based upon a discretization in space using spherical basis functions in a Galerkin approximation. As our spatial approximation spaces are built with spherical basis functions, they can be of arbitrary order and do not require the construction of an underlying mesh. We will establish convergence of the meshless method by adapting, to the sphere, a convergence result due to Thom\'ee and Wahlbin. To do this requires proving new approximation results, including a novel inverse or Nikolskii inequality for spherical basis functions. We also discuss how the integrals in the Galerkin method can accurately and more efficiently be computed using a recently developed quadrature rule. These new quadrature formulas also apply to Galerkin approximations of elliptic partial differential equations on the sphere. Finally, we provide several numerical examples, including the Allen-Cahn for the sphere.
more »
« less
- Award ID(s):
- 1514789
- PAR ID:
- 10100709
- Date Published:
- Journal Name:
- Numerische Mathematik
- Volume:
- 142
- Issue:
- 2
- ISSN:
- 0029-599X
- Page Range / eLocation ID:
- 383-149
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Trefftz methods are high-order Galerkin schemes in which all discrete functions are elementwise solution of the PDE to be approximated. They are viable only when the PDE is linear and its coefficients are piecewise-constant. We introduce a “quasi-Trefftz” discontinuous Galerkin (DG) method for the discretisation of the acoustic wave equation with piecewise-smooth material parameters: the discrete functions are elementwise approximate PDE solutions. We show that the new discretisation enjoys the same excellent approximation properties as the classical Trefftz one, and prove stability and high-order convergence of the DG scheme. We introduce polynomial basis functions for the new discrete spaces and describe a simple algorithm to compute them. The technique we propose is inspired by the generalised plane waves previously developed for time-harmonic problems with variable coefficients; it turns out that in the case of the time-domain wave equation under consideration the quasi-Trefftz approach allows for polynomial basis functions.more » « less
-
null (Ed.)The G-equation is a well-known model for studying front propagation in turbulent combustion. In this paper, we develop an efficient model reduction method for computing regular solutions of viscous G-equations in incompressible steady and time-periodic cellular flows. Our method is based on the Galerkin proper orthogonal decomposition (POD) method. To facilitate the algorithm design and convergence analysis, we decompose the solution of the viscous G-equation into a mean-free part and a mean part, where their evolution equations can be derived accordingly. We construct the POD basis from the solution snapshots of the mean-free part. With the POD basis, we can efficiently solve the evolution equation for the mean-free part of the solution to the viscous G-equation. After we get the mean-free part of the solution, the mean of the solution can be recovered. We also provide rigorous convergence analysis for our method. Numerical results for viscous G-equations and curvature G-equations are presented to demonstrate the accuracy and efficiency of the proposed method. In addition, we study the turbulent flame speeds of the viscous G-equations in incompressible cellular flows.more » « less
-
We provide a concise review of the exponentially convergent multiscale finite element method (ExpMsFEM) for efficient model reduction of PDEs in heterogeneous media without scale separation and in high-frequency wave propagation. The ExpMsFEM is built on the non-overlapped domain decomposition in the classical MsFEM while enriching the approximation space systematically to achieve a nearly exponential convergence rate regarding the number of basis functions. Unlike most generalizations of the MsFEM in the literature, the ExpMsFEM does not rely on any partition of unity functions. In general, it is necessary to use function representations dependent on the right-hand side to break the algebraic Kolmogorov n-width barrier to achieve exponential convergence. Indeed, there are online and offline parts in the function representation provided by the ExpMsFEM. The online part depends on the right-hand side locally and can be computed in parallel efficiently. The offline part contains basis functions that are used in the Galerkin method to assemble the stiffness matrix; they are all independent of the right-hand side, so the stiffness matrix can be used repeatedly in multi-query scenarios.more » « less
-
Abstract We present the first a priori error analysis of a new method proposed in Cockburn & Wang (2017, Adjoint-based, superconvergent Galerkin approximations of linear functionals. J. Comput. Sci., 73, 644–666), for computing adjoint-based, super-convergent Galerkin approximations of linear functionals. If $J(u)$ is a smooth linear functional, where $$u$$ is the solution of a steady-state diffusion problem, the standard approximation $$J(u_h)$$ converges with order $$h^{2k+1}$$, where $$u_h$$ is the Hybridizable Discontinuous Galerkin approximation to $$u$$ with polynomials of degree $k>0$. In contrast, numerical experiments show that the new method provides an approximation that converges with order $$h^{4k}$$, and can be computed by only using twice the computational effort needed to compute $$J(u_h)$$. Here, we put these experimental results in firm mathematical ground. We also display numerical experiments devised to explore the convergence properties of the method in cases not covered by the theory, in particular, when the solution $$u$$ or the functional $$J(\cdot )$$ are not very smooth. We end by indicating how to extend these results to the case of general Galerkin methods.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/doi:10.1007/s00211-018-01021-7
