Search

In this paper, we propose, analyze, and implement a new reduced basis method (RBM) tailored for the linear (ordinary and partial) differential equations driven by arbitrary (i.e. not necessarily Gaussian) types of noise. There are four main ingredients of our algorithm. First, we propose a new space-time-like treatment of time in the numerical schemes for ODEs and PDEs. The second ingredient is an accurate yet efficient compression technique for the spatial component of the space-time snapshots that the RBM is adopting as bases. The third ingredient is a non-conventional “parameterization” of a non-parametric problem. The last is a RBM that is free of any dedicated offline procedure yet is still efficient online. The numerical experiments verify the effectiveness and robustness of our algorithms for both types of differential equations.

The Reduced Basis Method (RBM) is a rigorous model reduction approach for solving parametrized partial differential equations. It identifies a low-dimensional subspace for approximation of the parametric solution manifold that is embedded in high-dimensional space. A reduced order model is subsequently constructed in this subspace. RBM relies on residual-based error indicators or {\em a posteriori} error bounds to guide construction of the reduced solution subspace, to serve as a stopping criteria, and to certify the resulting surrogate solutions. Unfortunately, it is well-known that the standard algorithm for residual norm computation suffers from premature stagnation at the level of the square root of machine precision. In this paper, we develop two alternatives to the standard offline phase of reduced basis algorithms. First, we design a robust strategy for computation of residual error indicators that allows RBM algorithms to enrich the solution subspace with accuracy beyond root machine precision. Secondly, we propose a new error indicator based on the Lebesgue function in interpolation theory. This error indicator does not require computation of residual norms, and instead only requires the ability to compute the RBM solution. This residual-free indicator is rigorous in that it bounds the error committed by the RBM approximation, but up to an uncomputable multiplicative constant. Because of this, the residual-free indicator is effective in choosing snapshots during the offline RBM phase, but cannot currently be used to certify error that the approximation commits. However, it circumvents the need for \textit{a posteriori} analysis of numerical methods, and therefore can be effective on problems where such a rigorous estimate is hard to derive.

The need for accelerating the repeated solving of certain parametrized systems motivates the development of more efficient reduced order methods. The classical reduced basis method is popular due to an offline-online decomposition and a mathematically rigorous {\em a posterior} error estimator which guides a greedy algorithm offline. For nonlinear and nonaffine problems, hyper reduction techniques have been introduced to make this decomposition efficient. However, they may be tricky to implement and often degrade the online computation efficiency. To avoid this degradation, reduced residual reduced over-collocation (R2-ROC) was invented integrating empirical interpolation techniques on the solution snapshots and well-chosen residuals, the collocation philosophy, and the simplicity of evaluating the hyper-reduced well-chosen residuals. In this paper, we introduce an adaptive enrichment strategy for R2-ROC rendering it capable of handling parametric fluid flow problems. Built on top of an underlying Marker and Cell (MAC) scheme, a novel hyper-reduced MAC scheme is therefore presented and tested on Stokes and Navier-Stokes equations demonstrating its high efficiency, stability and accuracy.

The task of repeatedly solving parametrized partial differential equations (pPDEs) in, e.g. optimization or interactive applications, makes it imperative to design highly efficient and equally accurate surrogate models. The reduced basis method (RBM) presents as such an option. Enabled by a mathematically rigorous error estimator, RBM constructs a low-dimensional subspace of the parameter-induced high fidelity solution manifold from which an approximate solution is computed. It can improve efficiency by several orders of magnitudes leveraging an offline-online decomposition procedure. However, this decomposition, usually through the empirical interpolation method (EIM) when the PDE is nonlinear or its parameter dependence nonaffine, is either challenging to implement, or severely degrades online efficiency. In this paper, we augment and extend the EIM approach as a direct solver, as opposed to an assistant, for solving nonlinear pPDEs on the reduced level. The resulting method, called Reduced Over-Collocation method (ROC), is stable and capable of avoiding the efficiency degradation inherent to a traditional application of EIM. Two critical ingredients of the scheme are collocation at about twice as many locations as the dimension of the reduced solution space, and an efficient L1-norm-based error indicator for the strategic selection of the parameter values to build the reduced solution space. Together, these two ingredients render the proposed L1-ROC scheme both offline- and online-efficient. A distinctive feature is that the efficiency degradation appearing in alternative RBM approaches that utilize EIM for nonlinear and nonaffine problems is circumvented, both in the offline and online stages. Numerical tests on different families of time-dependent and steady-state nonlinear problems demonstrate the high efficiency and accuracy of L1-ROC and its superior stability performance., 24 pages, 5 figures. arXiv admin note: substantial text overlap with arXiv:1906.07349

Fractional Laplace equations are becoming important tools for mathematical modeling and prediction. Recent years have shown much progress in developing accurate and robust algorithms to numerically...

We present this special issue of the Journal of Scientific Computing to celebrate Bernardo Cockburn’s sixtieth birthday. The theme of this issue is discontinuous Galerkin methods, a hallmark of Bernardo’s distinguished professional career. This foreword provides an informal but rigorous account of what enabled Bernardo’s achievements, based on the concluding presentation he gave at the the IMA workshop “Recent Advances and Challenges in Discontinuous Galerkin Methods and Related Approaches” on July 1, 2017 which was widely deemed as the best lecture of his career so far.

We propose a novel numerical algorithm utilizing model reduction for computing solutions to stationary partial differential equations involving the spectral fractional Laplacian. Our approach utilizes a known characterization of the solution in terms of an integral of solutions to classical elliptic problems. We reformulate this integral into an expression whose continuous and discrete formulations are stable; the discrete formulations are stable independent of all discretization parameters. We subsequently apply the reduced basis method to accomplish model order reduction for the integrand. Our choice of quadrature in discretization of the integral is a global Gaussian quadrature rule that we observe is more efficient than previously proposed quadrature rules. Finally, the model reduction approach enables one to compute solutions to multi-query fractional Laplace problems with order of magnitude less cost than a traditional solver., 26 pages, 7 figures

The need for multiple interactive, real-time simulations using different parameter values has driven the design of fast numerical algorithms with certifiable accuracies. The reduced basis method (RBM) presents itself as such an option. RBM features a mathematically rigorous error estimator which drives the construction of a low-dimensional subspace. A surrogate solution is then sought in this low-dimensional space approximating the parameter-induced high fidelity solution manifold. However when the system is nonlinear or its parameter dependence nonaffine, this efficiency gain degrades tremendously, an inherent drawback of the application of the empirical interpolation method (EIM). In this paper, we augment and extend the EIM approach as a direct solver, as opposed to an assistant, for solving nonlinear partial differential equations on the reduced level. The resulting method, called Reduced Over-Collocation method (ROC), is stable and capable of avoiding the efficiency degradation. Two critical ingredients of the scheme are collocation at about twice as many locations as the number of basis elements for the reduced approximation space, and an efficient error indicator for the strategic building of the reduced solution space. The latter, the main contribution of this paper, results from an adaptive hyper reduction of the residuals for the reduced solution. Together, these two ingredients render the proposed R2-ROC scheme both offline- and online-efficient. A distinctive feature is that the efficiency degradation appearing in traditional RBM approaches that utilize EIM for nonlinear and nonaffine problems is circumvented, both in the offline and online stages. Numerical tests on different families of time-dependent and steady-state nonlinear problems demonstrate the high efficiency and accuracy of our R2-ROC and its superior stability performance.

The reduced basis method (RBM) is a popular certified model reduction approach for solving parametrized partial differential equations. One critical stage of the offline portion of the algorithm is a greedy algorithm, requiring maximization of an error estimate over parameter space. In practice this maximization is usually performed by replacing the parameter domain continuum with a discrete “training” set. When the dimension of parameter space is large, it is necessary to significantly increase the size of this training set in order to effectively search parameter space. Large training sets diminish the attractiveness of RBM algorithms since this proportionally increases the cost of the offline phase. In this work we propose novel strategies for offline RBM algorithms that mitigate the computational difficulty of maximizing error estimates over a training set. The main idea is to identify a subset of the training set, a “surrogate training set” (STS), on which to perform greedy algorithms. The STS we construct is much smaller in size than the full training set, yet our examples suggest that it is accurate enough to induce the solution manifold of interest at the current offline RBM iteration. We propose two algorithms to construct the STS: our first algorithm, the successive maximization method, is inspired by inverse transform sampling for non-standard univariate probability distributions. The second constructs an STS by identifying pivots in the Cholesky decomposition of an approximate error correlation matrix. We demonstrate the algorithm through numerical experiments, showing that it is capable of accelerating offline RBM procedures without degrading accuracy, assuming that the solution manifold has rapidly decaying Kolmogorov width.

The reduced basis method (RBM) empowers repeated and rapid evaluation of parametrized partial differential equations through an offline-online decomposition, a.k.a. a learning-execution process. A key feature of the method is a greedy algorithm repeatedly scanning the training set, a fine discretization of the parameter domain, to identify the next dimension of the parameter-induced solution manifold along which we expand the surrogate solution space. Although successfully applied to problems with fairly high parametric dimensions, the challenge is that this scanning cost dominates the offline cost due to it being proportional to the cardinality of the training set which is exponential with respect to the parameter dimension. In this work, we review three recent attempts in effectively delaying this curse of dimensionality, and propose two new hybrid strategies through successive refinement and multilevel maximization of the error estimate over the training set. All five offline-enhanced methods and the original greedy algorithm are tested and compared on {two types of problems: the thermal block problem and the geometrically parameterized Helmholtz problem.

We design and analyze the first hybridizable discontinuous Galerkin methods for stationary, third-order linear equations in one-space dimension. The methods are defined as discrete versions of characterizations of the exact solution in terms of local problems and transmission conditions. They provide approximations to the exact solution u u and its derivatives q := u ′ q:=u’ and p := u p:=u which are piecewise polynomials of degree k u k_u , k q k_q and k p k_p , respectively. We consider the methods for which the difference between these polynomial degrees is at most two. We prove that all these methods have superconvergence properties which allows us to prove that their numerical traces converge at the nodes of the partition with order at least 2 k + 1 2\,k+1 , where k k is the minimum of k u , k q k_u,k_q , and k p k_p . This allows us to use an element-by-element post-processing to obtain new approximations for u , q u, q and p p converging with order at least 2 k + 1 2k+1 uniformly. Numerical results validating our error estimates are displayed.

We present a certified version of the Natural-Norm Successive Constraint Method (cNNSCM) for fast and accurate Inf-Sup lower bound evaluation of parametric operators. Successive Constraint Methods (SCM) are essential tools for the construction of a lower bound for the inf-sup stability constants which are required in a posteriori error analysis of reduced basis approximations. They utilize a Linear Program (LP) relaxation scheme incorporating continuity and stability constraints. The natural-norm approach linearizes a lower bound of the inf-sup constant as a function of the parameter. The Natural-Norm Successive Constraint Method (NNSCM) combines these two aspects. It uses a greedy algorithm to select SCM control points which adaptively construct an optimal decomposition of the parameter domain, and then apply the SCM on each domain.Unfortunately, the NNSCM produces no guarantee for the quality of the lower bound. Through multiple rounds of optimal decomposition, the new cNNSCM provides an upper bound in addition to the lower bound and lets the user control the gap, thus the quality of the lower bound. The efficacy and accuracy of the new method is validated by numerical experiments.

The nonintrusive generalized polynomial chaos (gPC) method is a popular computational approach for solving partial differential equations with random inputs. The main hurdle preventing its efficient direct application for high-dimensional input parameters is that the size of many parametric sampling meshes grows exponentially in the number of inputs (the “curse of dimensionality''). In this paper, we design a weighted version of the reduced basis method (RBM) for use in the nonintrusive gPC framework. We construct an RBM surrogate that can rigorously achieve a user-prescribed error tolerance and ultimately is used to more efficiently compute a gPC approximation nonintrusively. The algorithm is capable of speeding up traditional nonintrusive gPC methods by orders of magnitude without degrading accuracy, assuming that the solution manifold has low Kolmogorov width. Numerical experiments on our test problems show that the relative efficiency improves as the parametric dimension increases, demonstrating the p...

In this paper, we extend the recently developed reduced collocation method [3] to the nonlinear case, and propose two analytical preconditioning strategies. One is parameter independent and easy to implement, the other one has the traditional affinity with respect to the parameters, which allows an efficient implementation through an offline–online decomposition. Overall, preconditioning improves the quality of the error estimation uniformly on the parameter domain, and speeds up the convergence of the reduced solution to the truth approximation.

In this paper, we provide a projection-based analysis of the hversion of the hybridizable discontinuous Galerkin methods for convectiondiffusion equations on semimatching nonconforming meshes made of simplexes; the degrees of the piecewise polynomials are allowed to vary from element to element. We show that, for approximations of degree k on all elements, the order of convergence of the error in the diffusive flux is k+ 1 and that that of a projection of the error in the scalar unknown is 1 for k = 0 and k + 2 for k > 0. We also show that, for the variable-degree case, the projection of the error in the scalar variable is h-times the projection of the error in the vector variable, provided a simple condition is satisfied for the choice of the degree of the approximation on the elements with hanging nodes. These results hold for any (bounded) irregularity index of the nonconformity of the mesh. Moreover, our analysis can be extended to hypercubes.

In a posteriori error analysis of reduced basis approximations to affinely parametrized partial differential equations, the construction of lower bounds for the coercivity and inf-sup stability constants is essential. In (Huynh et al., C. R. Acad. Sci. Paris Ser. I Math. 345 (2007) 473-478), the authors presented an efficient method, compatible with an off-line/on-line strategy, where the on- line computation is reduced to minimizing a linear functional under a few linear constraints. These constraints depend on nested sets of parameters obtained iteratively using a greedy algorithm. We improve here this method so that it becomes more efficient and robust due to two related properties: (i) the lower bound is obtained by a monotonic process with respect to the size of the nested sets; (ii) less eigen-problems need to be solved. This improved evaluation of the inf-sup constant is then used to consider a reduced basis approximation of a parameter dependent electromagnetic cavity problem both for the greedy construction of the elements of the basis and the subsequent validation of the reduced basis approximation. The problem we consider has resonance features for some choices of the parameters that are well captured by the methodology.

We propose and study an adaptive version of the discontinuous Galerkin method for Hamilton–Jacobi equations. It works as follows. Given the tolerance and the degree of the polynomial of the approximate solution, the adaptive algorithm finds a mesh on which the approximate solution has an L 1 -distance to the viscosity solution no bigger than the prescribed tolerance. The algorithm uses three main tools. The first is an iterative solver combining the explicit Runge–Kutta discontinuous Galerkin method and the implicit Newton’s method that enables us to solve the Hamilton–Jacobi equations efficiently. The second is a new a posteriori error estimate based on the approximate resolution of an approximate problem for the actual error. The third is a method that allows us to find a new mesh as a function of the old mesh and the ratio of the a posteriori error estimate to the tolerance. We display extensive numerical evidence that indicates that, for any given polynomial degree, the method achieves its goal with optimal complexity independently of the tolerance. This is done in the framework of one-dimensional steady-state model problems with periodic boundary conditions.

The Centers for Medicare and Medicaid Services (CMS) has made public a data set showing what hospitals charged and what Medicare paid for the one hundred most common inpatient stays. Here we present the application of Reduced Basis Decomposition (RBD), an efficient novel dimension reduction algorithm for data processing, to the CMS data. This was paired with a comparative visual exploration of the results when put into context with characteristics of the hospitals and marketplaces in which they operate. We used Weave Analyst, a new web-based analysis and visualization environment, to visualize the relationship between the hospital groups, their charge levels, and distinguishing indicator variables. Particular insights to the relatively small number of underlying factors that exert greatest influence on hospital pricing surfaced thanks to the combined synergetic integration of the modeling, reduction, and visualization techniques.

Dimension reduction is often needed in the area of data mining. The goal of these methods is to map the given high-dimensional data into a low-dimensional space preserving certain properties of the initial data. There are two kinds of techniques for this purpose. The first, projective methods, builds an explicit linear projection from the high-dimensional space to the low-dimensional one. On the other hand, the nonlinear methods utilizes nonlinear and implicit mapping between the two spaces. In both cases, the methods considered in literature have usually relied on computationally very intensive matrix factorizations, frequently the Singular Value Decomposition (SVD). The computational burden of SVD quickly renders these dimension reduction methods infeasible thanks to the ever-increasing sizes of the practical datasets. In this paper, we present a new decomposition strategy, Reduced Basis Decomposition (RBD), which is inspired by the Reduced Basis Method (RBM). Given $X$ the high-dimensional data, the method approximates it by $Y \, T (\approx X)$ with $Y$ being the low-dimensional surrogate and $T$ the transformation matrix. $Y$ is obtained through a greedy algorithm thus extremely efficient. In fact, it is significantly faster than SVD with comparable accuracy. $T$ can be computed on the fly. Moreover, unlike many compression algorithms, it easily finds the mapping for an arbitrary ``out-of-sample'' vector and it comes with an ``error indicator'' certifying the accuracy of the compression. Numerical results are shown validating these claims.

The authors discuss multiple solutions for thenth-order singular boundary value problems of nonlinear integrodifferential equations in Banach spaces by means of the fixed point theorem of cone expansion and compression. An example for infinite system of scalar third-order singular nonlinear integrodifferential equations is offered.

We propose and test the first Reduced Radial Basis Function Method (R$^2$BFM) for solving parametric partial differential equations on irregular domains. The two major ingredients are a stable Radial Basis Function (RBF) solver that has an optimized set of centers chosen through a reduced-basis-type greedy algorithm, and a collocation-based model reduction approach that systematically generates a reduced-order approximation whose dimension is orders of magnitude smaller than the total number of RBF centers. The resulting algorithm is efficient and accurate as demonstrated through two- and three-dimensional test problems.

The boundary value problems of a class of th-order nonlinear integrodifferential equations of mixed type in Banach space are considered, and the existence of three solutions is obtained by using the fixed-point index theory.

In this paper, we present the first reduced basis method well-suited for the collocation framework. Two fundamentally different algorithms are presented: the so-called Least Squares Reduced Collocation Method (LSRCM) and Empirical Reduced Collocation Method (ERCM). This work provides a reduced basis strategy to practitioners who {prefer} a collocation, rather than Galerkin, approach. Furthermore, the empirical reduced collocation method eliminates a potentially costly online procedure that is needed for non-affine problems with Galerkin approach. Numerical results demonstrate the high efficiency and accuracy of the reduced collocation methods, which match or exceed that of the traditional reduced basis method in the Galerkin framework.

We study nontrivial applications of the reduced basis method (RBM) for electromagnetic applications with an emphasis on scattering and the estimation of radar cross section (RCS). The method and several extensions are explained with two examples with different characteristics. Parameters that are allowed to vary within the model include frequency, incident angle and measurement angle as well as the geometry of the scatterers. With appropriate applications of the empirical interpolation method (EIM), transformation of the domain, configuration of perfectly matched layer, exponential convergence of the reduced basis solution over the entire parameter domain is achieved. Moreover, we demonstrate that this approach allows for the effective capture of the critical behavior, in this case through shapes that minimize scattering. This further highlights the robustness and quality of the greedy approximation and the reduced basis method approach. (C) 2012 Elsevier B.V. All rights reserved.

We present a reduced basis element method (RBEM) for the time-harmonic Maxwell’s equation. The RBEM is a Reduced Basis Method (RBM) with parameters describing the geometry of the computational domain, coupled with a domain decomposition method. The basic idea is the following. First, we decompose the computational domain into a series of subdomains, each of which is deformed from some reference domain. Then, we associate with each reference domain precomputed solutions to the same governing partial differential equation, but with different choices of deformations. Finally, one seeks the approximation on a new domain as a linear combination of the corresponding precomputed solutions on each subdomain. Unlike the work on RBEM for thermal fin and fluid flow problems, we do not need a mortar type method to “glue” the various local functions. This “gluing” is done “automatically” thanks to the use of a discontinuous Galerkin method. We present the rationale for the method together with numerical results showing exponential convergence for the simulation of a metallic pipe with both ends open.

We propose certified reduced basis methods for the efficient and reliable evaluation of a general output that is implicitly connected to a given parameterized input through the harmonic Maxwell's equations. The truth approximation and the development of the reduced basis through a greedy approach is based on a discontinuous Galerkin approximation of the linear partial differential equation. The formulation allows the use of different approximation spaces for solving the primal and the dual truth approximation problems to respect the characteristics of both problem types, leading to an overall reduction in the off-line computational effort. The main features of the method are the following: (i) rapid convergence on the entire representative set of parameters, (ii) rigorous a posteriori error estimators for the output, and (iii) a parameter independent off-line phase and a computationally very efficient on-line phase to enable the rapid solution of many-query problems arising in control, optimization, and design. The versatility and performance of this approach is shown through a numerical experiment, illustrating the modeling of material variations and problems with resonant behavior.

For accurate a posteriori error analysis of the reduced basis method for coercive and non-coercive problems, a critical ingredient lies in the evaluation of a lower bound for the coercivity or inf-sup constant. In this short Note, we generalize and improve the successive constraint method first presented by Huynh (2007) by providing a monotonic version of this algorithm that leads to both more stable evaluations and fewer offline computations. To cite this article: Y Chen et al., C. R. Acad. Sci. Paris, Ser. I 346 (2008). (C) 2008 Academie des sciences. Published by Elsevier Masson SAS. All rights reserved.

In this paper, the author discusses the multiple positive solutions for an infinite three-point boundary value problem of first-order impulsive superlinear singular integro-differential equations on the half line in a Banach space by means of the fixed-point theorem of cone expansion and compression with norm type. MSC: 45J05; 34G20; 47H10