Geometric weakly admissible meshes, discrete least squares approximations and approximate Fekete points

Bos, L.; Calvi, J.-P.; Levenberg, N.; Sommariva, A.; Vianello, M.

doi:10.1090/S0025-5718-2011-02442-7

Geometric weakly admissible meshes, discrete least squares approximations and approximate Fekete points
HTML articles powered by AMS MathViewer

by L. Bos, J.-P. Calvi, N. Levenberg, A. Sommariva and M. Vianello;

Math. Comp. 80 (2011), 1623-1638

DOI: https://doi.org/10.1090/S0025-5718-2011-02442-7

Published electronically: January 19, 2011

PDF | Request permission

Abstract:

Using the concept of Geometric Weakly Admissible Meshes (see §2 below) together with an algorithm based on the classical QR factorization of matrices, we compute efficient points for discrete multivariate least squares approximation and Lagrange interpolation.

References

R. Berman and S. Boucksom, D. Witt Nyström, Fekete points and convergence towards equilibrium measures on complex manifolds, arXiv:0907.2820 (Acta Math., to appear).
T. Bloom, L. Bos, C. Christensen, and N. Levenberg, Polynomial interpolation of holomorphic functions in $\textbf {C}$ and $\textbf {C}^n$, Rocky Mountain J. Math. 22 (1992), no. 2, 441–470. MR 1180711, DOI 10.1216/rmjm/1181072740
T. Bloom, L. Bos, N. Levenberg, and S. Waldron, On the convergence of optimal measures, Constr. Approx. 32 (2010), no. 1, 159–179. MR 2659752, DOI 10.1007/s00365-009-9078-7
Len Bos, Marco Caliari, Stefano De Marchi, Marco Vianello, and Yuan Xu, Bivariate Lagrange interpolation at the Padua points: the generating curve approach, J. Approx. Theory 143 (2006), no. 1, 15–25. MR 2271722, DOI 10.1016/j.jat.2006.03.008
L. P. Bos and N. Levenberg, On the calculation of approximate Fekete points: the univariate case, Electron. Trans. Numer. Anal. 30 (2008), 377–397. MR 2487768
Peter Businger and Gene H. Golub, Handbook series linear algebra. Linear least squares solutions by Householder transformations, Numer. Math. 7 (1965), 269–276. MR 176590, DOI 10.1007/BF01436084
M. Caliari, S. De Marchi and M. Vianello, Algorithm 886: Padua2D: Lagrange Interpolation at Padua Points on Bivariate Domains, ACM Trans. Math. Software 35-3 (2008).
Jean-Paul Calvi and Norman Levenberg, Uniform approximation by discrete least squares polynomials, J. Approx. Theory 152 (2008), no. 1, 82–100. MR 2419299, DOI 10.1016/j.jat.2007.05.005
Ali Çivril and Malik Magdon-Ismail, On selecting a maximum volume sub-matrix of a matrix and related problems, Theoret. Comput. Sci. 410 (2009), no. 47-49, 4801–4811. MR 2583677, DOI 10.1016/j.tcs.2009.06.018
Moshe Dubiner, Spectral methods on triangles and other domains, J. Sci. Comput. 6 (1991), no. 4, 345–390. MR 1154903, DOI 10.1007/BF01060030
Michael G. Duffy, Quadrature over a pyramid or cube of integrands with a singularity at a vertex, SIAM J. Numer. Anal. 19 (1982), no. 6, 1260–1262. MR 679664, DOI 10.1137/0719090
Jan S. Hesthaven and Tim Warburton, Nodal discontinuous Galerkin methods, Texts in Applied Mathematics, vol. 54, Springer, New York, 2008. Algorithms, analysis, and applications. MR 2372235, DOI 10.1007/978-0-387-72067-8
Maciej Klimek, Pluripotential theory, London Mathematical Society Monographs. New Series, vol. 6, The Clarendon Press, Oxford University Press, New York, 1991. Oxford Science Publications. MR 1150978
B. F. Logan and L. A. Shepp, Optimal reconstruction of a function from its projections, Duke Math. J. 42 (1975), no. 4, 645–659. MR 397240
Yvon Maday, Ngoc Cuong Nguyen, Anthony T. Patera, and George S. H. Pau, A general multipurpose interpolation procedure: the magic points, Commun. Pure Appl. Anal. 8 (2009), no. 1, 383–404. MR 2449115, DOI 10.3934/cpaa.2009.8.383
The Mathworks, MATLAB documentation set, 2008 version, (http://www.mathworks.com).
A. Narkhede and D. Manocha, Graphics Gems 5, Academic Press, 1995, pp. 394–397.
Richard Pasquetti and Francesca Rapetti, Spectral element methods on unstructured meshes: comparisons and recent advances, J. Sci. Comput. 27 (2006), no. 1-3, 377–387. MR 2285788, DOI 10.1007/s10915-005-9048-6
A. Sommariva and M. Vianello, Product Gauss cubature over polygons based on Green’s integration formula, BIT 47 (2007), no. 2, 441–453. MR 2334049, DOI 10.1007/s10543-007-0131-2
Alvise Sommariva and Marco Vianello, Computing approximate Fekete points by QR factorizations of Vandermonde matrices, Comput. Math. Appl. 57 (2009), no. 8, 1324–1336. MR 2512231, DOI 10.1016/j.camwa.2008.11.011
N. Sukumar and E. A. Malsch, Recent advances in the construction of polygonal finite element interpolants, Arch. Comput. Methods Engrg. 13 (2006), no. 1, 129–163. MR 2283620, DOI 10.1007/BF02905933
M. A. Taylor, B. A. Wingate, and R. E. Vincent, An algorithm for computing Fekete points in the triangle, SIAM J. Numer. Anal. 38 (2000), no. 5, 1707–1720. MR 1813252, DOI 10.1137/S0036142998337247
Mark A. Taylor, Beth A. Wingate, and Len P. Bos, A cardinal function algorithm for computing multivariate quadrature points, SIAM J. Numer. Anal. 45 (2007), no. 1, 193–205. MR 2285850, DOI 10.1137/050625801
T. Warburton, An explicit construction of interpolation nodes on the simplex, J. Engrg. Math. 56 (2006), no. 3, 247–262. MR 2292675, DOI 10.1007/s10665-006-9086-6
V.P. Zaharjuta, Transfinite diameter, Chebyshev constants and capacity for compacts in $\mathbb {C}^{n}$, Math. USSR Sbornik 25 (1975), 350–364.
P. Žitňan,, A stable collocation solution of the Poisson problems on planar domains, 2nd Dolomites Workshop on Constructive Approximation and Applications (DWCAA09), Alba di Canazei (Trento, Italy), Sept. 4-9 2009 (abstract online at: http://drna.di.univr.it).