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

Authors:
L. Bos, J.-P. Calvi, N. Levenberg, A. Sommariva and M. Vianello

Journal:
Math. Comp. **80** (2011), 1623-1638

MSC (2010):
Primary 41A10, 41A63, 65D05, 65D15, 65Y20

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

Published electronically:
January 19, 2011

MathSciNet review:
2785471

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

**[1]**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).**[2]**T. Bloom, L. Bos, C. Christensen and N. Levenberg,*Polynomial interpolation of holomorphic functions in and*, Rocky Mtn. J. Math.**22**(1992), 441-470. MR**1180711 (93i:32016)****[3]**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****[4]**L. Bos, M. Caliari, S. De Marchi, M. Vianello and Y. Xu,*Bivariate Lagrange interpolation at the Padua points: the generating curve approach*, J. Approx. Theory**143**(2006), 15-25. MR**2271722 (2007h:41001)****[5]**L. Bos and N. Levenberg,*On the approximate calculation of Fekete points: the univariate case*, Electron. Trans. Numer. Anal.**30**(2008), 377-397. MR**2487768 (2010a:41001)****[6]**P.A. Businger and G.H. Golub,*Linear least-squares solutions by Householder transformations*, Numer. Math.**7**(1965), 269-276. MR**0176590 (31:862)****[7]**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).**[8]**J.P. Calvi and N. Levenberg,*Uniform approximation by discrete least squares polynomials*, J. Approx. Theory**152**(2008), 82-100. MR**2419299 (2009c:32020)****[9]**A. Civril and M. Magdon-Ismail,*On selecting a maximum volume sub-matrix of a matrix and related problems*, Theoretical Comp. Sci.**410**(2009), 4801-4811. MR**2583677****[10]**M. Dubiner,*Spectral methods on triangles and other domains*, J. Sci. Computing**6**, no. 4 (1991), 345-390. MR**1154903 (92k:76061)****[11]**M.G. Duffy,*Quadrature over a pyramid or cube of integrands with a singularity at a vertex*, SIAM J. Numer. Anal.**19**(1982), 1260-1262. MR**679664 (83k:65020)****[12]**J.S. Hesthaven and T. Warburton,*Nodal discontinuous Galerkin methods algorithms, analysis, and applications, Texts in Applied Mathematics, 54*, Springer, New York, 2008. MR**2372235 (2008k:65002)****[13]**M. Klimek,*Pluripotential Theory*, Oxford U. Press, 1991. MR**1150978 (93h:32021)****[14]**B.F. Logan and L.A. Shepp,*Optimal reconstruction of a function from its projections*, Duke Math. J.**42**(1975), 645-659. MR**0397240 (53:1099)****[15]**Y. Maday, N.C. Nguyen, A.T. Patera and G.S.H. Pau,*A general multipurpose interpolation procedure: the magic points*, Commun. Pure Appl. Anal.**8**(2009), 383-404. MR**2449115 (2009i:65016)****[16]***The Mathworks, MATLAB documentation set, 2008 version*, (http://www.mathworks.com).**[17]**A. Narkhede and D. Manocha, Graphics Gems 5, Academic Press, 1995, pp. 394-397.**[18]**R. Pasquetti and F. Rapetti,*Spectral element methods on unstructured meshes: comparisons and recent advances*, J. Sci. Comput.**27**(2006), 377-387. MR**2285788 (2008a:65235)****[19]**A. Sommariva and M. Vianello,*Product Gauss cubature over polygons based on Green's integration formula*, BIT Numerical Mathematics**47**(2007), 441-453. MR**2334049 (2008g:65046)****[20]**A. Sommariva and M. Vianello,*Computing approximate Fekete points by QR factorizations of Vandermonde matrices*, Comput. Math. Appl.**57**(2009), 1324-1336. MR**2512231****[21]**N. Sukumar and E.A. Malsch,*Recent advances in the construction of polygonal finite element interpolants*, Arch. Comput. Methods Engrg.**13**(2006), 129-163. MR**2283620 (2007m:65113)****[22]**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), 1707-1720. MR**1813252 (2001k:65042)****[23]**M.A. Taylor, B.A. Wingate and L.P. Bos,*A cardinal function algorithm for computing multivariate quadrature points*, SIAM J. Numer. Anal.**45**(2007), 193-205. MR**2285850 (2008i:65046)****[24]**T. Warburton,*An explicit construction of interpolation nodes on the simplex*, J. Engrg. Math.**56**(2006), 247-262. MR**2292675 (2008c:65022)****[25]**V.P. Zaharjuta,*Transfinite diameter, Chebyshev constants and capacity for compacts in*, Math. USSR Sbornik**25**(1975), 350-364.**[26]**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)*.

Retrieve articles in *Mathematics of Computation*
with MSC (2010):
41A10,
41A63,
65D05,
65D15,
65Y20

Retrieve articles in all journals with MSC (2010): 41A10, 41A63, 65D05, 65D15, 65Y20

Additional Information

**L. Bos**

Affiliation:
Department of Mathematics and Statistics, University of Calgary, Calgary, Alberta, Canada T2N 1N4

**J.-P. Calvi**

Affiliation:
Institut de Mathématiques de Toulouse, Université Paul Sabatier, 32062, Toulouse Cedex 9, France

**N. Levenberg**

Affiliation:
Department of Mathematics, Indiana University, Bloomington, Indiana, 47405

**A. Sommariva**

Affiliation:
Department of Pure and Applied Mathematics, University of Padova, 35121 Padova, Italy

**M. Vianello**

Affiliation:
Department of Pure and Applied Mathematics, University of Padova, 35121 Padova, Italy

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

Keywords:
Admissible meshes,
discrete least squares approximation,
approximate Fekete points,
multivariate polynomial interpolation

Received by editor(s):
February 10, 2009

Received by editor(s) in revised form:
April 18, 2010

Published electronically:
January 19, 2011

Additional Notes:
The first author was supported in part by NSERC.

The last three authors were supported by the “ex-$60%$” funds and by the project “Interpolation and Extrapolation: new algorithms and applications” (2009/10) of the University of Padova, and by the INdAM GNCS

Article copyright:
© Copyright 2011
American Mathematical Society