An LP empirical quadrature procedure for parametrized functions

Patera, Anthony T.; Yano, Masayuki

Comptes Rendus. Mathématique, Tome 355 (2017) no. 11, pp. 1161-1167.

Nous étendons la procédure de quadrature empirique par programmation linéaire proposée dans [9] et par la suite dans [3] au cas où les fonctions à intégrer sont associées à une variété paramétrique. Nous posons un problème de programmation linéaire discret et semi-infini : nous minimisons la fonction objectif, qui est la somme des poids (positifs) de quadrature, qui constitue une norme ${\ell }_1$ menant à des solutions parcimonieuses et assurant la stabilité, les contraintes d'inégalité requises étant que les intégrales de J fonctions échantillonnées à partir de la variété soient évaluées à une précision $\overline{\delta }$. Nous fournissons un estimateur d'erreur a priori et des résultats numériques qui démontrent que, sous certaines conditions de régularité, toute fonction de la variété est évaluée par la méthode de quadrature empirique avec précision $\overline{\delta }$ quand $J\to \infty$. Nous présentons deux exemples numériques : une transformée inverse de Laplace et un traitement par base réduite d'une équation aux dérivées partielles non linéaire.

We extend the linear program empirical quadrature procedure proposed in [9] and subsequently [3] to the case in which the functions to be integrated are associated with a parametric manifold. We pose a discretized linear semi-infinite program: we minimize as objective the sum of the (positive) quadrature weights, an ${\ell }_1$ norm that yields sparse solutions and furthermore ensures stability; we require as inequality constraints that the integrals of J functions sampled from the parametric manifold are evaluated to accuracy $\overline{\delta }$. We provide an a priori error estimate and numerical results that demonstrate that under suitable regularity conditions, the integral of any function from the parametric manifold is evaluated by the empirical quadrature rule to accuracy $\overline{\delta }$ as $J\to \infty$. We present two numerical examples: an inverse Laplace transform; reduced-basis treatment of a nonlinear partial differential equation.

[1] An, S.S.; Kim, T.; James, D.L. Optimizing cubature for efficient integration of subspace deformations, ACM Trans. Graph., Volume 27 (2008) no. 5

[2] Barrault, M.; Maday, Y.; Nguyen, C.N.; Patera, A.T. An empirical interpolation method: application to efficient reduced-basis discretization of partial differential equations, C. R. Acad. Sci. Paris, Ser. I, Volume 339 (2004), pp. 667-672

[3] R. DeVore, S. Foucart, G. Petrova, P. Wojtaszczyk, Computing a quantity of interest from observational data, preprint, 2017.

[4] Dossal, C. A necessary and sufficient condition for exact sparse recovery by ${\ell }_1$ minimization, C. R. Acad. Sci. Paris, Ser. I, Volume 350 (2012) no. 1–2, pp. 117-120

[5] Elad, M. Sparse and Redundant Representations, Springer, 2010

[6] Farhat, C.; Chapman, T.; Avery, P. Structure-preserving, stability, and accuracy properties of the energy-conserving sampling and weighting method for the hyper reduction of nonlinear finite element dynamic models, Int. J. Numer. Methods Eng., Volume 102 (2015), pp. 1077-1110

[7] Foucart, S.; Rauhut, H. A Mathematical Introduction to Compressive Sensing, Birkhäuser, 2013

[8] Rozza, G.; Huynh, D.B.P.; Patera, A.T. Reduced basis approximation and a posteriori error estimation for affinely parametrized elliptic coercive partial differential equations; application to transport and continuum mechanics, Arch. Comput. Methods Eng., Volume 15 (2008), pp. 229-275

[9] Ryu, E.K.; Boyd, S.P. Extensions of Gauss quadrature via linear programming, Found. Comput. Math., Volume 15 (2015), pp. 953-971