Adaptive Sparse Grid Discontinuous Galerkin Method:Review and Software Implementation

This paper reviews the adaptive sparse grid discontinuous Galerkin(aSG-DG)method for computing high dimensional partial differential equations(PDEs)and its software implementation.The C++software package called AdaM-DG,implementing the aSG-DG method,is available on GitHub at https://github.com/JuntaoHuang/adaptive-multiresolution-DG.The package is capable of treating a large class of high dimensional linear and nonlinear PDEs.We review the essential components of the algorithm and the functionality of the software,including the multiwavelets used,assembling of bilinear operators,fast matrix-vector product for data with hierarchical structures.We further demonstrate the performance of the package by reporting the numerical error and the CPU cost for several benchmark tests,including linear transport equations,wave equations,and Hamilton-Jacobi(HJ)equations.

Uncertain eigenvalue analysis by the sparse grid stochastic collocation method

In this paper, the eigenvalue problem with multiple uncertain parameters is analyzed by the sparse grid stochastic collocation method. This method provides an interpolation approach to approximate eigenvalues and eigenvectors＇ functional dependencies on uncertain parame- ters. This method repetitively evaluates the deterministic solutions at the pre-selected nodal set to construct a high- dimensional interpolation formula of the result. Taking advantage of the smoothness of the solution in the uncer- tain space, the sparse grid collocation method can achieve a high order accuracy with a small nodal set. Compared with other sampling based methods, this method converges fast with the increase of the number of points. Some numerical examples with different dimensions are presented to demon- strate the accuracy and efficiency of the sparse grid stochastic collocation method.

Sparse-Grid Implementation of Fixed-Point Fast Sweeping WENO Schemes for Eikonal Equations

Fixed-point fast sweeping methods are a class of explicit iterative methods developed in the literature to efficiently solve steady-state solutions of hyperbolic partial differential equations(PDEs).As other types of fast sweeping schemes,fixed-point fast sweeping methods use the Gauss-Seidel iterations and alternating sweeping strategy to cover characteristics of hyperbolic PDEs in a certain direction simultaneously in each sweeping order.The resulting iterative schemes have a fast convergence rate to steady-state solutions.Moreover,an advantage of fixed-point fast sweeping methods over other types of fast sweeping methods is that they are explicit and do not involve the inverse operation of any nonlinear local system.Hence,they are robust and flexible,and have been combined with high-order accurate weighted essentially non-oscillatory(WENO)schemes to solve various hyperbolic PDEs in the literature.For multidimensional nonlinear problems,high-order fixed-point fast sweeping WENO methods still require quite a large amount of computational costs.In this technical note,we apply sparse-grid techniques,an effective approximation tool for multidimensional problems,to fixed-point fast sweeping WENO methods for reducing their computational costs.Here,we focus on fixed-point fast sweeping WENO schemes with third-order accuracy(Zhang et al.2006[41]),for solving Eikonal equations,an important class of static Hamilton-Jacobi(H-J)equations.Numerical experiments on solving multidimensional Eikonal equations and a more general static H-J equation are performed to show that the sparse-grid computations of the fixed-point fast sweeping WENO schemes achieve large savings of CPU times on refined meshes,and at the same time maintain comparable accuracy and resolution with those on corresponding regular single grids.

Efficient Sparse-Grid Implementation of a Fifth-Order Multi-resolution WENO Scheme for Hyperbolic Equations

High-order accurate weighted essentially non-oscillatory(WENO)schemes are a class of broadly applied numerical methods for solving hyperbolic partial differential equations(PDEs).Due to highly nonlinear property of the WENO algorithm,large amount of computational costs are required for solving multidimensional problems.In our previous work(Lu et al.in Pure Appl Math Q 14:57–86,2018;Zhu and Zhang in J Sci Comput 87:44,2021),sparse-grid techniques were applied to the classical finite difference WENO schemes in solving multidimensional hyperbolic equations,and it was shown that significant CPU times were saved,while both accuracy and stability of the classical WENO schemes were maintained for computations on sparse grids.In this technical note,we apply the approach to recently developed finite difference multi-resolution WENO scheme specifically the fifth-order scheme,which has very interesting properties such as its simplicity in linear weights’construction over a classical WENO scheme.Numerical experiments on solving high dimensional hyperbolic equations including Vlasov based kinetic problems are performed to demonstrate that the sparse-grid computations achieve large savings of CPU times,and at the same time preserve comparable accuracy and resolution with those on corresponding regular single grids.

Sparse grid-based polynomial chaos expansion for aerodynamics of an airfoil with uncertainties

The uncertainties can generate fluctuations with aerodynamic characteristics. Uncertainty Quantification（UQ） is applied to compute its impact on the aerodynamic characteristics.In addition, the contribution of each uncertainty to aerodynamic characteristics should be computed by uncertainty sensitivity analysis. Non-Intrusive Polynomial Chaos（NIPC） has been successfully applied to uncertainty quantification and uncertainty sensitivity analysis. However, the non-intrusive polynomial chaos method becomes inefficient as the number of random variables adopted to describe uncertainties increases. This deficiency becomes significant in stochastic aerodynamic analysis considering the geometric uncertainty because the description of geometric uncertainty generally needs many parameters. To solve the deficiency, a Sparse Grid-based Polynomial Chaos（SGPC） expansion is used to do uncertainty quantification and sensitivity analysis for stochastic aerodynamic analysis considering geometric and operational uncertainties. It is proved that the method is more efficient than non-intrusive polynomial chaos and Monte Carlo Simulation（MSC） method for the stochastic aerodynamic analysis. By uncertainty quantification, it can be learnt that the flow characteristics of shock wave and boundary layer separation are sensitive to the geometric uncertainty in transonic region. The uncertainty sensitivity analysis reveals the individual and coupled effects among the uncertainty parameters.

A SPARSE GRID STOCHASTIC COLLOCATION AND FINITE VOLUME ELEMENT METHOD FOR CONSTRAINED OPTIMAL CONTROL PROBLEM GOVERNED BY RANDOM ELLIPTIC EQUATIONS

In this paper, a hybird approximation scheme for an optimal control problem governed by an elliptic equation with random field in its coefficients is considered. The random coefficients are smooth in the physical space and depend on a large number of random variables in the probability space. The necessary and sufficient optimality conditions for the optimal control problem are obtained. The scheme is established to approximate the optimality system through the discretization by using finite volume element method for the spatial space and a sparse grid stochastic collocation method based on the Smolyak approximation for the probability space, respectively. This scheme naturally leads to the discrete solutions of an uncoupled deterministic problem. The existence and uniqueness of the discrete solutions are proved. A priori error estimates are derived for the state, the co-state and the control variables. Numerical examples are presented to illustrate our theoretical results.

Selected Recent Applications of Sparse Grids

Sparse grids have become a versatile tool for a vast range of applications reaching from interpolation and numerical quadrature to data-driven problems and uncertainty quantification.We review four selected real-world applications of sparse grids:financial product pricing with the Black-Scholes model,interactive explo-ration of simulation data with sparse-grid-based surrogate models,analysis of simu-lation data through sparse grid data mining methods,and stability investigations of plasma turbulence simulations.

An ADI Sparse Grid method for Pricing Efficiently American Options under the Heston Model

One goal of financial research is to determine fair prices on the financial market.As financial models and the data sets on which they are based are becoming ever larger and thus more complex,financial instruments must be further developed to adapt to the new complexity,with short runtimes and efficient use of memory space.Here we show the effects of combining known strategies and incorporating new ideas to further improve numerical techniques in computational finance.In this paper we combine an ADI(alternating direction implicit)scheme for the temporal discretization with a sparse grid approach and the combination technique.The later approach considerably reduces the number of“spatial”grid points.The presented standard financial problem for the valuation of American options using the Heston model is chosen to illustrate the advantages of our approach,since it can easily be adapted to other more complex models.

A Numerical Comparison Between Quasi-Monte Carlo and Sparse Grid Stochastic Collocation Methods

Quasi-Monte Carlo methods and stochastic collocation methods based on sparse grids have become popular with solving stochastic partial differential equations.These methods use deterministic points for multi-dimensional integration or interpolation without suffering from the curse of dimensionality.It is not evident which method is best,specially on random models of physical phenomena.We numerically study the error of quasi-Monte Carlo and sparse gridmethods in the context of groundwater flow in heterogeneous media.In particular,we consider the dependence of the variance error on the stochastic dimension and the number of samples/collocation points for steady flow problems in which the hydraulic conductivity is a lognormal process.The suitability of each technique is identified in terms of computational cost and error tolerance.

Smolyak Type Sparse Grid Collocation Method for Uncertainty Quantification of Nonlinear Stochastic Dynamic Equations

This paper develops a Smolyak-type sparse-grid stochastic collocation method(SGSCM) for uncertainty quantification of nonlinear stochastic dynamic equations.The solution obtained by the method is a linear combination of tensor product formulas for multivariate polynomial interpolation.By choosing the collocation point sets to coincide with cubature point sets of quadrature rules,we derive quadrature formulas to estimate the expectations of the solution.The method does not suffer from the curse of dimensionality in the sense that the computational cost does not increase exponentially with the number of input random variables.Numerical analysis of a nonlinear elastic oscillator subjected to a discretized band-limited white noise process demonstrates the computational efficiency and accuracy of the developed method.

A SPARSE-GRID METHOD FOR MULTI-DIMENSIONAL BACKWARD STOCHASTIC DIFFERENTIAL EQUATIONS

A sparse-grid method for solving multi-dimensional backward stochastic differential equations （BSDEs） based on a multi-step time discretization scheme [31] is presented. In the multi-dimensional spatial domain, i.e. the Brownian space, the conditional mathe- matical expectations derived from the original equation are approximated using sparse-grid Gauss-Hermite quadrature rule and （adaptive） hierarchical sparse-grid interpolation. Error estimates are proved for the proposed fully-discrete scheme for multi-dimensional BSDEs with certain types of simplified generator functions. Finally, several numerical examples are provided to illustrate the accuracy and efficiency of our scheme.

Robust Topology Optimization of Periodic Multi-Material Functionally Graded Structures under Loading Uncertainties

This paper presents a robust topology optimization design approach for multi-material functional graded structures under periodic constraint with load uncertainties.To characterize the random-field uncertainties with a reduced set of random variables,the Karhunen-Lo`eve(K-L)expansion is adopted.The sparse grid numerical integration method is employed to transform the robust topology optimization into a weighted summation of series of deterministic topology optimization.Under dividing the design domain,the volume fraction of each preset gradient layer is extracted.Based on the ordered solid isotropic microstructure with penalization(Ordered-SIMP),a functionally graded multi-material interpolation model is formulated by individually optimizing each preset gradient layer.The periodic constraint setting of the gradient layer is achieved by redistributing the average element compliance in sub-regions.Then,the method of moving asymptotes(MMA)is introduced to iteratively update the design variables.Several numerical examples are presented to verify the validity and applicability of the proposed method.The results demonstrate that the periodic functionally graded multi-material topology can be obtained under different numbers of sub-regions,and robust design structures are more stable than that indicated by the deterministic results.

Variance-Based Global Sensitivity Analysis via Sparse-Grid Interpolation and Cubature

The stochastic collocation method using sparse grids has become a popular choice for performing stochastic computations in high dimensional(random)parameter space.In addition to providing highly accurate stochastic solutions,the sparse grid collocation results naturally contain sensitivity information with respect to the input random parameters.In this paper,we use the sparse grid interpolation and cubature methods of Smolyak together with combinatorial analysis to give a computationally efficient method for computing the global sensitivity values of Sobol’.This method allows for approximation of all main effect and total effect values from evaluation of f on a single set of sparse grids.We discuss convergence of this method,apply it to several test cases and compare to existing methods.As a result which may be of independent interest,we recover an explicit formula for evaluating a Lagrange basis interpolating polynomial associated with the Chebyshev extrema.This allows one to manipulate the sparse grid collocation results in a highly efficient manner.

An Adaptive Multiresolution Ultra-weak Discontinuous Galerkin Method for Nonlinear Schrödinger Equations

This paper develops a high-order adaptive scheme for solving nonlinear Schrödinger equa-tions.The solutions to such equations often exhibit solitary wave and local structures,which make adaptivity essential in improving the simulation efficiency.Our scheme uses the ultra-weak discontinuous Galerkin(DG)formulation and belongs to the framework of adaptive multiresolution schemes.Various numerical experiments are presented to demon-strate the excellent capability of capturing the soliton waves and the blow-up phenomenon.

Sequential Multiscale Modeling Using Sparse Representation

The main obstacle in sequential multiscale modeling is the pre-computation of the constitutive relationwhich often involvesmany independent variables.The constitutive relation of a polymeric fluid is a function of six variables,even after making the simplifying assumption that stress depends only on the rate of strain.Precomputing such a function is usually considered too expensive.Consequently the value of sequential multiscale modeling is often limited to“parameter passing”.Here we demonstrate that sparse representations can be used to drastically reduce the computational cost for precomputing functions of many variables.This strategy dramatically increases the efficiency of sequential multiscale modeling,making it very competitive in many situations.

A Comparison of Deterministic, Reliability-Based Topology Optimization under Uncertainties

Reliability and optimization are two key elements for structural design. The reliability~ based topology optimization （RBTO） is a powerful and promising methodology for finding the optimum topologies with the uncertainties being explicitly considered, typically manifested by the use of reliability constraints. Generally, a direct integration of reliability concept and topol- ogy optimization may lead to computational difficulties. In view of this fact, three methodologies have been presented in this study, including the double-loop approach （the performance measure approach, PMA） and the decoupled approaches （the so-called Hybrid method and the sequential optimization and reliability assessment, SORA）. For reliability analysis, the stochastic response surface method （SRSM） was applied, combining with the design of experiments generated by the sparse grid method, which has been proven as an effective and special discretization technique. The methodologies were investigated with three numerical examples considering the uncertainties including material properties and external loads. The optimal topologies obtained using the de- terministic, RBTOs were compared with one another; and useful conclusions regarding validity, accuracy and efficiency were drawn.

TWO-SCALE FINITE ELEMENT DISCRETIZATIONS FOR PARTIAL DIFFERENTIAL EQUATIONS

Some two-scale finite element discretizations are introduced for a class of linear partial differential equations. Both boundary value and eigenvalue problems are studied. Based on the two-scale error resolution techniques, several two-scale finite element algorithms are proposed and analyzed. It is shown that this type of two-scale algorithms not only significantly reduces the number of degrees of freedom but also produces very accurate approximations.

A Stochastic Collocation Method for Delay Differential Equations with Random Input

In this work,we concern with the numerical approach for delay differential equations with random coefficients.We first show that the exact solution of the problem considered admits good regularity in the random space,provided that the given data satisfy some reasonable assumptions.A stochastic collocation method is proposed to approximate the solution in the random space,and we use the Legendre spectral collocation method to solve the resulting deterministic delay differential equations.Convergence property of the proposed method is analyzed.It is shown that the numerical method yields the familiar exponential order of convergence in both the random space and the time space.Numerical examples are given to illustrate the theoretical results.

Efficient Solution of Ordinary Differential Equations with High-Dimensional Parametrized Uncertainty

The important task of evaluating the impact of random parameters on the output of stochastic ordinary differential equations(SODE)can be computationally very demanding,in particular for problems with a high-dimensional parameter space.In this work we consider this problem in some detail and demonstrate that by combining several techniques one can dramatically reduce the overall cost without impacting the predictive accuracy of the output of interests.We discuss how the combination of ANOVA expansions,different sparse grid techniques,and the total sensitivity index(TSI)as a pre-selective mechanism enables the modeling of problems with hundred of parameters.We demonstrate the accuracy and efficiency of this approach on a number of challenging test cases drawn from engineering and science.

A Comparative Study of Stochastic Collocation Methods for Flow in Spatially Correlated Random Fields

Stochastic collocation methods as a promising approach for solving stochastic partial differential equations have been developed rapidly in recent years.Similar to Monte Carlo methods,the stochastic collocation methods are non-intrusive in that they can be implemented via repetitive execution of an existing deterministic solver without modifying it.The choice of collocation points leads to a variety of stochastic collocation methods including tensor product method,Smolyak method,Stroud 2 or 3 cubature method,and adaptive Stroud method.Another type of collocation method,the probabilistic collocation method(PCM),has also been proposed and applied to flow in porous media.In this paper,we discuss these methods in terms of their accuracy,efficiency,and applicable range for flow in spatially correlated random fields.These methods are compared in details under different conditions of spatial variability and correlation length.This study reveals that the Smolyak method and the PCM outperform other stochastic collocation methods in terms of accuracy and efficiency.The random dimensionality in approximating input random fields plays a crucial role in the performance of the stochastic collocation methods.Our numerical experiments indicate that the required random dimensionality increases slightly with the decrease of correlation scale and moderately from one to multiple physical dimensions.