Padua points and “fake” nodes for polynomial approximation: old, new and open problems. (English) Zbl 1499.41099

De Marchi, Stefano

Constr. Math. Anal. 5, No. 1, 14-36 (2022).

Summary: Padua points, discovered in 2005 at the University of Padua, are the first set of points on the square \([-1,1]^2\) that are explicitly known, unisolvent for total degree polynomial interpolation and with Lebesgue constant increasing like \(\log^2(n)\) of the degree. One of the key features of the Padua points is that they lie on a particular Lissajous curve. Other important properties of Padua points are

(1)

in two dimensions, Padua points are a WAM for interpolation and for extracting approximate Fekete points and discrete Leja sequences.

(2)

in three dimensions, Padua points can be used for constructing tensor product WAMs on different compacts.

Unfortunately, their extension to higher dimensions is still the biggest open problem.
The concept of mapped bases has been widely studied (cf. e.g. [S. De Marchi et al., J. Comput. Appl. Math. 364, Article ID 112347, 12 p. (2020; Zbl 1439.65010)] and references therein), which turns out to be equivalent to map the interpolating nodes and then construct the approximant in the classical form without the need of resampling. The mapping technique is general, in the sense that works with any basis and can be applied to continuous, piecewise or discontinuous functions or even images.
All the proposed methods show convergence to the interpolant provided that the function is resampled at the mapped nodes. In applications, this is often physically unfeasible. An effective method for interpolating via mapped bases in the multivariate setting, referred as Fake Nodes Approach (FNA), has been presented in [S. De Marchi et al., Appl. Math. Comput. 391, Article ID 125628, 18 p. (2021; Zbl 1474.65022)]. In this paper, some interesting connection of the FNA with Padua points and families of relatives nodes, that can be used as fake nodes for multivariate approximation, are presented and we conclude with some open problems.

MSC:

41A63

Multidimensional problems

Keywords:

Padua points; Lissajous curves and points; mapped polynomial basis

Citations:

Zbl 1439.65010; Zbl 1474.65022

Software:

Padua2DM; Matlab; Chebfun; GaussQR; FakeNodes; Padua2D

References:

[1]	B. Adcock, R. B. Platte: A mapped polynomial method for high-accuracy approximations on arbitrary grids, SIAM J. Numer. Anal., 54 (2016), 2256-2281. · Zbl 1342.65088
[2]	R. Archibald, A. Gelb and J. Yoon: Polynomial Fitting for Edge Detection in Irregularly Sampled Signals and Images, SIAM J. Numer. Analysis, 43 (1) (2005), 259-279. · Zbl 1093.41009
[3]	J. Baglama, D. Calvetti and L. Reichel: Fast Leja points, Electron. Trans. Numer. Anal., 7 (1998), 124-140. · Zbl 0912.65004
[4]	J.-P. Berrut, S. De Marchi, G. Elefante and F. Marchetti: Treating the Gibbs phenomenon in barycentric rational interpolation and approximationvia the S-Gibbs algorithm, Appl. Math. Letters, 103 (2020), 106196. · Zbl 1440.41004
[5]	L. Bos: On certain configurations of points in R^n which are unisolvent for polynomial interpolation, J. Approx. Theory, 64 (3) (1991), 271-280. · Zbl 0737.41002
[6]	L. Bos: Multivariate interpolation and polynomial inequalities, Ph.D. course held at the University of Padua (2001), unpublished.
[7]	L. Bos, M. Caliari, S. De Marchi and M. Vianello: A numerical study of the Xu interpolation formula, Computing, 76 (3-4) (2006), 311-324. · Zbl 1087.65009
[8]	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 (1) (2006), 15-25. · Zbl 1113.41001
[9]	L. Bos, J.-P. Calvi, N. Levenberg, A. Sommariva and M. Vianello: Geometric Weakly Admissible Meshes, Discrete Least Squares Approximations and Approximate Fekete Points, Math. Comp., 80 (2011), 1601-1621. · Zbl 1228.41002
[10]	L. Bos, S. De Marchi, M. Vianello and Y. Xu: Bivariate Lagrange interpolation at the Padua points: the ideal theory approach, Numer. Math., 108 (1) (2007), 43-57. · Zbl 1126.41002
[11]	L. Bos, S. De Marchi and S. Waldron: On the Vandermonde Determinant of Padua-like Points (on Open Problems section), Dolomites Res. Notes on Approx., 2 (2009), 1-15.
[12]	L. Bos, S. De Marchi, A. Sommariva and M. Vianello: Weakly Admissible Meshes and Discrete Extremal Sets, Numer. Math. Theory Methods Appl., 4 (2011), 1-12. · Zbl 1249.65014
[13]	L. Bos, S. De Marchi, A. Sommariva and M. Vianello: Computing multivariate Fekete and Leja points by numerical linear algebra, SIAM J. Num. Anal., 48 (5) (2010), 1984-1999. · Zbl 1221.41005
[14]	L. Bos, N. Levenberg: On the Approximate Calculation of Fekete Points: the Univariate Case, Elec. Trans. Numer. Anal., 30 (2008), 377-397. · Zbl 1176.41001
[15]	L. Bos, A. Sommariva and M. Vianello: Least-squares polynomial approximation on weakly admissible meshes: disk and triangle, J. Comput. Appl. Math., 235 (2010), 660-668. · Zbl 1200.65010
[16]	L. Bos, M. A. Taylor and B. A. Wingate: Tensor product Gauss-Lobatto points are Fekete points for the cube, Math. Comp., 70 (2001), 1543-1547. · Zbl 0985.41007
[17]	L. Brutman: Lebesgue functions for polynomial interpolation: a survey, Ann. Numer. Math., 4 (1997), 111-127. · Zbl 0888.41001
[18]	M. D. Buhmann: Radial Basis Functions: Theory and Implementation, Cambridge Monogr. Appl. Comput. Math., Vol. 12, Cambridge Univ. Press, Cambridge, (2003). · Zbl 1038.41001
[19]	CAA: Padova-Verona Research Group on Constructive Approximation webpage: https://sites.google.com/view/caa-padova-verona/home
[20]	M. Caliari, S. De Marchi and M. Vianello: Bivariate polynomial interpolation on the square at new nodal sets, Appl. Math. Comput., 165 (2) (2005), 261-274. · Zbl 1081.41001
[21]	M. Caliari, S. De Marchi, M. Vianello: Algorithm 886: Padua2D: Lagrange Interpolation at Padua Points on Bivariate Domains, ACM Trans. Math. Software, 35 (3) (2008), 1-11.
[22]	M. Caliari, S. De Marchi and M. Vianello: Bivariate Lagrange interpolation at the Padua points: computational aspects, J. Comput. Appl. Math., 221 (2008), 284-292. · Zbl 1152.65018
[23]	M. Caliari, S. De Marchi, A. Sommariva and M. Vianello: Padua2DM: fast interpolation and cubature at Padua points in Matlab/Octave, Numer. Algorithms, 56 (1) (2011), 45-60. · Zbl 1206.65028
[24]	J. Canny: A Computational Approach to Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8 (6) (1986), 679-698.
[25]	J. P. Calvi, N. Levenberg: Uniform approximation by discrete least squares polynomials, J. Approx. Theory, 152 (2008), 82-100. · Zbl 1145.41001
[26]	W. Cheney, W. Light: A Course on Approximation Theory, AMS, Vol. 101, (2009). · Zbl 1167.41001
[27]	K. C. Chung, T. H. Yao: On lattices adimmitting unique Lagrange interpolations, SIAM J. Numer. Anal., 14 (1977), 735-743. · Zbl 0367.65003
[28]	P. Davis: Interpolation and Approximation, Blaisdell Pub Company, New York, (1963). · Zbl 0111.06003
[29]	A. Cuyt, I. Yaman, B. A. Ibrahimoglu and B. Benouahmane: Radial orthogonality and Lebesgue constants on the disk, Numer. Algorithms, 61 (2) (2012), 291-313. · Zbl 1259.65011
[30]	C. de Boor: A Practical Guide to Splines, revised edition, Springer, New York, (2001). · Zbl 0987.65015
[31]	A. P. de Camargo, S. De Marchi: A few remarks on “On certain Vandermonde determinants whose variables separate”, Dolomites Res. Notes Approx., 8 (2015), 1-11. · Zbl 1370.15004
[32]	S. De Marchi: On Leja sequences: some results and applications, Appl. Math. Comput., 152 (3) (2004), 621-647. · Zbl 1077.41001
[33]	S. De Marchi, G. Elefante and F. Marchetti: Stable discontinuous mapped bases: the Gibbs-Runge-Avoiding Stable Polynomial Approximation (GRASPA) method, Comput. Appl. Math., 40:299 (2021). · Zbl 1499.65029
[34]	S. De Marchi, G. Elefante, E. Perracchione and D. Poggiali: Quadrature at fake nodes, Dolomites Res. Notes Approx., 14 Special Issue MATA2020 (2021), 39-45. · Zbl 1474.65022
[35]	S. De Marchi, F. Marchetti, E. Perracchione and D. Poggiali: Polynomial interpolation via mapped bases without resampling, J. Comput. Appl. Math., 364 (2020), 112347. · Zbl 1439.65010
[36]	S. De Marchi, W. Erb and F. Marchetti: Lissajous sampling and spectral filtering in MPI applications: the reconstruction algorithm for reducing the Gibbs phenomenon, 2017 International Conference on Sampling Theory and Applications SampTA (2017), 580-584.
[37]	S. De Marchi, F. Marchetti, E. Perracchione and D. Poggiali: Multivariate approximation at fake nodes, Appl. Math. Comput., 391 (2021), 125628. · Zbl 1474.65022
[38]	S. De Marchi,W. Erb, F. Marchetti, E. Perracchione and M. Rossini: Shape-Driven Interpolation with Discontinuous Kernels: Error Analysis, Edge Extraction and Applications in Magnetic Particle Imaging, SIAM J. Sci. Comput., 42 (2) (2020), B472-B491. · Zbl 1444.65006
[39]	S. De Marchi, A. Sommariva and M. Vianello: Multivariate Christoffel functions and hyperinterpolation, Dolomites Res. Notes Approx., 7 (2014), 36-33.
[40]	S. De Marchi, R. Schaback and H. Wendland: Near-Optimal Data-Independent Point Locations for Radial Basis Function Interpolation, Adv. Comput. Math., 23 (3) (2005), 317-330. · Zbl 1070.65008
[41]	S. De Marchi, F. Piazzon, A. Sommariva and M. Vianello: Polynomial Meshes: Computation and Approximation, Proceedings of the 15th International Conference on Computational and Mathematical Methods in Science and Engineering CMMSE (2015), 414-425.
[42]	S. De Marchi, K. Usevich: On certain multivariate Vandermonde determinants whose variables separate, Linear Alg. Appl., 449 (2014), 17-27. · Zbl 1303.15008
[43]	S. De Marchi, M. Vianello: Polynomial approximation on pyramids, cones and solids of rotation, Dolomites Res. Notes Approx., Proceedings DWCAA12, 6 (2013), 20-26.
[44]	F. Dell’Accio, F. Di Tommaso and F. Nudo: Generalizations of the constrained mock-Chebyshev least squares in two variables: Tensor product vs total degree polynomial interpolation, Appl. Math. Letters, 125 (2022), 107732. · Zbl 1487.65016
[45]	M. Dubiner: The theory of multi-dimensional polynomial approximation, J. Anal. Math., 67 (1995), 39-116. · Zbl 0857.41006
[46]	W. Erb, C. Kathner, P. Denker and M. Alhborg: A survey on bivariate Lagrange interpolation on Lissajous nodes, Dolomites Res. Notes Approx., 8 (2015), 23-36. · Zbl 1370.41006
[47]	G. E. Fasshauer: Meshfree Approximation Methods with Matlab,World Scientific Publishing, Interdisciplinary Mathematical Sciences, Vol. 6, Singapore, (2007). · Zbl 1123.65001
[48]	G. E. Fasshauer, M. J. McCourt: Kernel-based Approximation Methods Using Matlab, World Scientific Publishing, Interdisciplinary Mathematical Sciences, Vol. 17, Singapore, (2015). · Zbl 1318.00001
[49]	L. Fernández, T. E. Pérez and M. A. Piãr: On Koornwinder classical orthogonal polynomials in two variables, J. Comput. Appl. Math., 236 (2012), 3817-3826. · Zbl 1262.42007
[50]	G. J. Gassner, F. Lörcher, C.-D. Munz and J. S. Hesthaven: Polymorphic nodal elements and their application in discontinuous Galerkin methods, J. Comput. Phys., 228 (2009), 1573-1590. · Zbl 1267.76062
[51]	J. W. Gibbs: Fourier’s Series, Nature, 59 (1898), 200. · JFM 30.0240.04
[52]	R. L. Hardy: Multiquadric equations of topography and other irregular surfaces, J. Geophys. Res., 76 (1971), 1905-1915.
[53]	N. J. Higham: The numerical stability of barycentric Lagrange interpolation, IMA J. Numer. Anal., 24 (2004), 547-556. · Zbl 1067.65016
[54]	K. Hormann, G. Klein and S. De Marchi: Barycentric rational interpolation at quasi-equidistant nodes, Dolomites Res. Notes Approx., 5 (2012), 1-6. · Zbl 1252.41003
[55]	E. J. Kansa: Application of Hardy’s multiquadric interpolation to hydrodynamics, Proceeding Multiconference on Computer Simulation: Aerospace, San Diego (1986), 111-117.
[56]	M. Krebsbach, B. Trauzette and A. Calzona: Optimization of Richardson extrapolation for quantum error mitigation, preprint on ResearchGate (21 January 2022).
[57]	D. Kosloff, H. Tal-Ezer: A modified Chebyshev pseudospectral method with an O(N^{-1}) time step restriction, J. Comput. Phys., 104 (1993), 457-469. · Zbl 0781.65082
[58]	M. Koushki, E. Jabbari and M. Ahmadinia: Evaluating RBF methods for solving PDEs using Padua points distribution, Alexandria Eng. J., 59 (5) (2020), 2999-3018.
[59]	O. Landon-Cardinal, L. C. G. Govia and A. A. Clerk: Quantitative Tomography for Continuous Variable Quantum Systems, Phys. Rev. Lett., 120 (9) (2018), 090501.
[60]	N. T. Lloyd: Approximation Theory and Approximation Practice, SIAM, (2013). · Zbl 1264.41001
[61]	G. Mastroianni, D. Occorsio: Optimal systems of nodes for Lagrange interpolation on bounded intervals. A survey., J. Comput. Appl. Math., 134 (1-2) (2001), 325-341. · Zbl 0990.41003
[62]	J. C. Merino: Lissajous Figures and Chebyshev Polynomials, College Math. J., 32 (2) (2003), 122-127.
[63]	C. R. Morrow, T. N. L. Patterson: Construction of Algebraic Cubature Rules Using Polynomial Ideal Theory, SIAM J. Numer. Anal., 15 (5) (1978), 953-976. · Zbl 0402.65013
[64]	Numerical computing with functions: Chebfun. www.chebfun.org
[65]	R. Pachón, L. N. Trefethen: Barycentric-Remez algorithms for best polynomial approximation in the chebfun system, BIT Numer. Math., 49 (2009), 721-741. · Zbl 1179.65012
[66]	D. Poggiali, D. Cecchin, C. Campi and S. De Marchi: Oversampling errors in multimodal medical imaging are due to the Gibbs effect, Mathematics, 9 (12) (2021), 1348.
[67]	L. Qu: Copula density estimation by Lagrange interpolation at the Padua points, Conference on Data Science, Statistics & Visualization 2017, Book of abstacts p. 67.
[68]	T. Rivlin: An Introduction to the Approximation of Functions, Dover Pub. Inc, (1969). · Zbl 0189.06601
[69]	G. Rodeghiero, Y. Zhong et al.: An efficient interpolation for calculation of the response of composite layered material and its implementation in MUSIC imaging, Proceedings 19th Conference on the Computation of Electromagnetic Fields COMPUMAG, Budapest (Hungary) (2013).
[70]	L. Romani, M. Rossini and D. Schenone: Edge detection methods based on RBF interpolation, J. Comput. Applied Math., 349 (2019), 532-547. · Zbl 1440.65026
[71]	C. Runge: Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten, Zeit. Math. Phys., 46 (1901), 224-243. · JFM 32.0272.02
[72]	B. Schölkopf, A. J. Smola: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, MA, USA, (2002).
[73]	I. J. Schoenberg: Metric spaces and completely monotone functions, Ann. of Math., 39 (1938), 811-841. · JFM 64.0617.03
[74]	L. L. Schumaker: Spline Functions - Basic Theory, Wiley-Interscience, New York, (1981). · Zbl 0449.41004
[75]	A. Sommariva, M. Vianello: Computing approximate Fekete points by QR factorizations of Vandermonde matrices, Comp. Math. App., 57 (2009), 1324-1336. · Zbl 1186.65028
[76]	A. Sommariva, M. Vianello and R. Zanovello: Nontensorial Clenshaw-Curtis cubature, Numer. Algorithms, 49 (2008), 409-427. · Zbl 1167.65350
[77]	I. H. Sloan, R. S. Womersley: Extremal systems of points and numerical integration on the sphere. Adv. Comput. Math., 21 (2004), 107-125. · Zbl 1055.65038
[78]	M. A. Taylor, B. A. Wingate and R. E. Vincent: An algorithm for computing Fekete points in the triangle, SIAM J. Numer. Anal., 38 (5) (2000), 1707-1720. · Zbl 0986.65017
[79]	P. Vértesi: On the Lebesgue function and Lebesgue constant: a tribute to Paul Erdös, Bolyai Society of Mathematical Studies, Vol. 11, Budapest, Janos Bolyai Math. Soc., (2002), 705-728. · Zbl 1163.41302
[80]	H. Wendland: Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics, Cambridge Univ. Press, (2005). · Zbl 1075.65021
[81]	Wikipedia: Padua points https://en.wikipedia.org/wiki/Padua_points
[82]	Y. Xu: Christoffel functions and Fourier series for multivariate orthogonal polynomials, J. Approx. Theory, 82 (1995), 205-239. · Zbl 0874.42018
[83]	P. Zitnan: The collocation solution of Poisson problems based on approximate Fekete points, Eng. Anal. Bound. Elem., 35 (2011) 594-599. · Zbl 1259.65176