Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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.

References [Enhancements On Off] (What's this?)

  • [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 $ \mathbb{C}$ and $ \mathbb{C}^{n}$, 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, (
  • [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 $ \mathbb{C}^{n}$, 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:

Similar Articles

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

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

American Mathematical Society