×

Computing approximate Fekete points by QR factorizations of Vandermonde matrices. (English) Zbl 1186.65028

Summary: We propose a numerical method (implemented in Matlab) for computing approximate Fekete points on compact multivariate domains. It relies on the search of maximum volume submatrices of Vandermonde matrices computed on suitable discretization meshes, and uses a simple greedy algorithm based on QR factorization with column pivoting. The method gives also automatically an algebraic cubature formula, provided that the moments of the underlying polynomial basis are known. Numerical tests are presented for the interval and the square, which show that approximate Fekete points are well suited for polynomial interpolation and cubature.

MSC:

65D30 Numerical integration
65F25 Orthogonalization in numerical linear algebra
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Sommariva, A.; Vianello, M., Product Gauss cubature over polygons based on Green’s integration formula, BIT, 47, 441-453 (2007) · Zbl 1122.65027
[2] A. Sommariva, M. Vianello, Gauss-Green cubature and moment computation over arbitrary geometries, preprint, 2008 (available online at: http://www.math.unipd.it/ marcov/publications.html; A. Sommariva, M. Vianello, Gauss-Green cubature and moment computation over arbitrary geometries, preprint, 2008 (available online at: http://www.math.unipd.it/ marcov/publications.html · Zbl 1170.65017
[3] Björk, A., Numerical Methods for Least Squares Problems (1996), SIAM
[4] Golub, G. H.; Van loan, C. F., Matrix Computations (1996), Johns Hopkins University Press · Zbl 0865.65009
[5] The Mathworks, MATLAB documentation set 2007 version (available online at: http://www.mathworks.com); The Mathworks, MATLAB documentation set 2007 version (available online at: http://www.mathworks.com)
[6] Gautschi, W., Moments in quadrature problems, Comput. Math. Appl., 33, 105-118 (1997) · Zbl 0930.65011
[7] Businger, P. A.; Golub, G. H., Linear least-squares solutions by householder transformations, Numer. Math., 7, 269-276 (1965) · Zbl 0142.11503
[8] LAPACK Users’ Guide (1999), SIAM, (available online at http://www.netlib.org/lapack)
[9] Bos, L.; Levenberg, N., On the calculation of approximate Fekete points: the univariate case, Electron. Trans. Numer. Anal., 30, 377-397 (2008) · Zbl 1176.41001
[10] Krylov, V. I., Approximate Calculation of Integrals (1962), Macmillan · Zbl 0111.31801
[11] Rivlin, T. J., An Introduction to the Approximation of Functions (1969), Dover · Zbl 0189.06601
[12] Mason, J. C.; Handscomb, D. C., Chebyshev Polynomials (2003), Chapman & Hall · Zbl 1015.33001
[13] A. Civril, M. Magdon-Ismail, Finding maximum volume sub-matrices of a matrix, Technical Report 07-08, Dept. of Comp. Sci., RPI, 2007 (available online at: www.cs.rpi.edu/research/pdf/07-08.pdf); A. Civril, M. Magdon-Ismail, Finding maximum volume sub-matrices of a matrix, Technical Report 07-08, Dept. of Comp. Sci., RPI, 2007 (available online at: www.cs.rpi.edu/research/pdf/07-08.pdf) · Zbl 1259.68086
[14] Quintana-Ortí, G.; Sun, X.; Bischof, C. H., A BLAS-3 version of the QR factorization with column pivoting, SIAM J. Sci. Comput., 19, 1486-1494 (1998) · Zbl 0912.65034
[15] Dubiner, M., The theory of multidimensional polynomial approximation, J. Anal. Math., 67, 39-116 (1995) · Zbl 0857.41006
[16] Reimer, M., Multivariate Polynomial Approximation (2003), Birkhäuser · Zbl 1038.41002
[17] Sündermann, B., Lebesgue constants in Lagrangian interpolation at the Fekete points, Mitt. Math. Ges. Hamburg, 11, 204-211 (1983) · Zbl 0547.41002
[18] Bos, L.; Levenberg, N.; Waldron, S., On the spacing of Fekete points for a sphere, ball or simplex, Indag. Math., 19, 163-176 (2008) · Zbl 1161.41001
[19] Taylor, M. A.; Wingate, B. A.; Vincent, R. E., An algorithm for computing Fekete points in the triangle, SIAM J. Numer. Anal., 38, 1707-1720 (2000) · Zbl 0986.65017
[20] Pasquetti, R.; Rapetti, F., Spectral element methods on unstructured meshes: Comparisons and recent advances, J. Sci. Comput., 27, 377-387 (2006) · Zbl 1102.65119
[21] J. Burkardt, Fekete: High order interpolation and quadrature in triangles, Matlab/Fortran90/C++ libraries (available online at: http://people.scs.fsu.edu/ burkardt/m_src/fekete/fekete.html; J. Burkardt, Fekete: High order interpolation and quadrature in triangles, Matlab/Fortran90/C++ libraries (available online at: http://people.scs.fsu.edu/ burkardt/m_src/fekete/fekete.html
[22] Sloan, I. H.; Womersley, R. S., Extremal systems of points and numerical integration on the sphere, Adv. Comput. Math., 21, 107-125 (2004) · Zbl 1055.65038
[23] Cools, R., An encyclopedia of cubature formulas, J. Complexity, 19, 445-453 (2003) · Zbl 1061.41020
[24] Taylor, M. A.; Wingate, B. A.; Bos, L., A cardinal function algorithm for computing multivariate quadrature points, SIAM J. Numer. Anal., 45, 193-205 (2007) · Zbl 1142.65028
[25] Kövari, T.; Pommerenke, C., On the distribution of Fekete points, Mathematika, 15, 70-75 (1968) · Zbl 0159.36201
[26] Fasino, D.; Inglese, G., On the spectral condition of rectangular Vandermonde matrices, Calcolo, 29, 291-300 (1992) · Zbl 0795.15003
[27] Gautschi, W., How (un)stable are Vandermonde systems?, (Wong, R., Asymptotic and Computational Analysis. Asymptotic and Computational Analysis, Lecture Notes in Pure and Applied Mathematics, vol. 124 (1990), Marcel Dekker), 193-210
[28] Giraud, L.; Langou, J.; Rozloznik, M.; van den Eshof, J., Rounding error analysis of the classical Gram-Schmidt orthogonalization process, Numer. Math., 101, 87-100 (2005) · Zbl 1075.65060
[29] Dunkl, C. F.; Xu, Y., (Orthogonal Polynomials of Several Variables. Orthogonal Polynomials of Several Variables, Encyclopedia of Mathematics and its Applications, vol. 81 (2001), Cambridge University Press) · Zbl 0964.33001
[30] Bos, L.; Levenberg, N.; Waldron, S., Metrics associated to multivariate polynomial inequalities, (Neamtu, M.; Saff, E. B., Advances in Constructive Approximation (2004), Nashboro Press: Nashboro Press Nashville), 133-147 · Zbl 1068.41022
[31] Bos, L.; Levenberg, N.; Waldron, S., Pseudometrics, distances and multivariate polynomial inequalities, J. Approx. Theory, 153, 80-96 (2008) · Zbl 1154.41007
[32] L. Bos, Multivariate interpolation and polynomial inequalities, Ph.D. course held at the University of Padua, 2001, unpublished; L. Bos, Multivariate interpolation and polynomial inequalities, Ph.D. course held at the University of Padua, 2001, unpublished
[33] Caliari, M.; De Marchi, S.; Vianello, M., Bivariate polynomial interpolation on the square at new nodal sets, Appl. Math. Comput., 161, 261-274 (2005) · Zbl 1081.41001
[34] Bos, L.; Taylor, M. A.; Wingate, B. A., Tensor product Gauss-Lobatto points are Fekete points for the cube, Math. Comp., 70, 1543-1547 (2001) · Zbl 0985.41007
[35] Calvi, J. P.; Levenberg, N., Uniform approximation by discrete least squares polynomials, J. Approx. Theory, 152, 82-100 (2008) · Zbl 1145.41001
[36] Bos, L.; Caliari, M.; De Marchi, S.; Vianello, M.; Xu, Y., Bivariate Lagrange interpolation at the Padua points: The generating curve approach, J. Approx. Theory, 143, 15-25 (2006) · Zbl 1113.41001
[37] Bos, L.; De Marchi, S.; Vianello, M.; Xu, Y., Bivariate Lagrange interpolation at the Padua points: The ideal theory approach, Numer. Math., 108, 43-57 (2007) · Zbl 1126.41002
[38] Caliari, M.; De Marchi, S.; Vianello, M., Bivariate Lagrange interpolation at the Padua points: Computational aspects, J. Comput. Appl. Math., 221, 284-292 (2008) · Zbl 1152.65018
[39] Caliari, M.; De Marchi, S.; Vianello, M., Padua2D: Bivariate Lagrange interpolation at Padua points on bivariate domains, ACM Trans. Math. Software, 35-3 (2008)
[40] Sommariva, A.; Vianello, M.; Zanovello, R., Nontensorial Clenshaw-Curtis cubature, Numer. Algorithms, 49, 409-427 (2008) · Zbl 1167.65350
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.