×

The collocation basis of compact finite differences for moment-preserving interpolations: review, extension and applications. (English) Zbl 1482.65018

Summary: The diagnostic of the performance of numerical methods for physical models, like those in computational fluid mechanics and other fields of continuum mechanics, rely on the preservation of statistical moments of extensive quantities. Dynamic and adaptive meshing often use interpolations to represent fields over a new set of elements and require to be conservative and moment-preserving. Denoising algorithms should not affect moment distributions of data. And numerical deltas are described using the number of moments preserved. Therefore, all these methodologies benefit from the use of moment-preserving interpolations. In this article, we review the presentation of the piecewise polynomial basis functions that provide moment-preserving interpolations, better described as the collocation basis of compact finite differences, or Z-splines. We present different applications of these basis functions that show the improvement of numerical algorithms for fluid mechanics, discrete delta functions and denoising. We also provide theorems of the extension of the properties of the basis, previously known as the Strang and Fix theory, to the case of arbitrary knot partitions.

MSC:

65D05 Numerical interpolation
65D07 Numerical computation using splines
41A05 Interpolation in approximation theory
76M23 Vortex methods applied to problems in fluid mechanics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Peraire, J. Peiró, K. Morgan. Adaptive remeshing for three-dimensional flow computa-tions. J. of Comput. Phys., 103(2) (1992), pp. 269-285. · Zbl 0764.76037
[2] G. H. Cottet, P. Koumoutsakos. Vortex Methods -theory and practice. Cambridge Univ. Press. New York, NY, USA. (2000). · Zbl 0953.76001
[3] C. C. Pain, A. P. Umpleby, C. R. E. de Oliveira, A. J. H. Goddard. Tetrahedral mesh opti-misation and adaptivity for steady-state and transient finite element calculations. Comput. Methods Appl. Mech. Eng., 190 (20-30) (2001), pp. 3771-3796. · Zbl 1008.76041
[4] J. Donea, A. Huerta, J.-P. Ponthot, A. Rodríguez-Ferran. Arbitrary Lagrangian-Eulerian Methods, in Encyclopedia of Computational Mechanics (E. Stein, R. Borst and T.J.R. Hughes, eds) (2004).
[5] J. T. Becerra-Sagredo, C. Málaga, F. Mandujano. Moments Preserving and high-resolution Semi-Lagrangian Advection Scheme. SIAM J. Sci. Comput. 38(4) (2016), A2141-A2161. · Zbl 1342.76001
[6] P.E. Farrell, M.D. Piggott, C.C. Pain, G.J. Gorman, C.R. Wilson. Conservative interpolation between unstructured meshes via supermesh construction. Comput. Methods Appl. Mech. Eng., 198(33-36) (2009), pp. 2632-2642. · Zbl 1228.76105
[7] P.E. Farrell, J.R. Maddison. Conservative interpolation between volume meshes by local Galerkin projection. Comput. Methods Appl. Mech. Eng., 200 (1-4) (2011), pp. 89-100. · Zbl 1225.76193
[8] A. Adam, D. Pavlidis, J. R. Percival, P. Salinas, Z. Xie, F. Fang, C. C. Pain, A. H. Muggeridge, M. D. Jackson. Higher-order conservative interpolation between control-volume meshes: Application to advection and multiphase flow problems with dynamic mesh adaptivity. J. of Comput. Phys. 321 (2016), pp. 512-531. · Zbl 1349.76164
[9] J. K. Dukowicz, J. W. Kodis. Accurate Conservative Remapping (Rezoning) for Arbitrary Lagrangian-Eulerian Computations. SIAM J. Sci. and Stat. Comput., 8(3) (1987), pp. 305-32. · Zbl 0644.76085
[10] L.G. Margolin, M. Shashkov. Second-order sign-preserving conservative interpolation (remapping) on general grids. J. of Comp. Physics, 184(1) (2003), pp. 266-298. · Zbl 1016.65004
[11] S. Menon, D. P. Schmidt. Conservative interpolation on unstructured polyhedral meshes: An extension of the supermesh approach to cell-centered finite-volume variables. Computer Methods in Applied Mechanics and Engineering, 200(41-44) (2011), pp. 2797-2804. · Zbl 1230.76034
[12] A. López Ortega, G. Scovazzi. A geometrically-conservative, synchronized, flux-corrected remap for arbitrary Lagrangian-Eulerian computations with nodal finite elements. J. of Comp. Physics, 230 (17) (2011), pp. 6709-6741. · Zbl 1284.76255
[13] P. A. Ullrich, M.A. Taylor. Arbitrary-Order Conservative and Consistent Remapping and a Theory of Linear Maps: Part I. Mon. Wea. Rev., 143 (2015), pp. 2419-2440.
[14] B. Peng, C. Zhou, J. Ai. Solution Reconstruction on Unstructured Tetrahedral Meshes Us-ing P1-Conservative Interpolation. Advances in Applied Mathematics and Mechanics, 8(5) (2016), pp. 847-870. · Zbl 1499.65033
[15] G. Blanchard, R. Loubère. High order accurate conservative remapping scheme on polygo-nal meshes using a posteriori MOOD limiting. Computers & Fluids, 136 (2016), pp. 83-103. · Zbl 1390.65101
[16] D.E. Burton, N.R. Morgan, M.R.J. Charest, M.A. Kenamond, J. Fung. Compatible, energy conserving, bounds preserving remap of hydrodynamic fields for an extended ALE scheme. J. of Comp. Physics, 355 (2018), pp. 492-533. · Zbl 1380.76051
[17] A. Marboeuf, A. Claisse, P. Le Tallec. Conservative and entropy controlled remap for multi-material ALE simulations with space-staggered schemes. J. of Comp. Physics, 390 (2019), pp. 66-92. · Zbl 1452.76096
[18] K. Lipnikov, N. Morgan. A high-order conservative remap for discontinuous Galerkin schemes on curvilinear polygonal meshes, J. of Comp. Physics, 399 (2019), 108931. · Zbl 1453.65333
[19] P. H. Lauritzen, R. D. Nair, P. A. Ullrich. A conservative semi-Lagrangian multi-tracer trans-port scheme (CSLAM) on the cubed-sphere grid. J. of Comp. Physics, 229 (5) (2010), pp. 1401-1424. · Zbl 1329.65198
[20] H.Z. Tang, T. Tang. Multi-dimensional moving mesh methods for shock computations, in Recent Advances in Scientific Computing and Partial Differential Equations (Providence, USA) (S.Y. Cheng, C.-W. Shu, and T. Tang, eds.), Contemporary Mathematics, Vol. 330, AMS (2003), pp. 169-183. · Zbl 1034.76037
[21] T. Tang. Moving mesh methods for computational fluid dynamics, in Recent Advances in Adaptive Computations (Providence, USA) (Z. -C. Shi, Z. Cheng, T. Tang and D. Yu, eds.), Contemporary Mathematics, Vol. 383, AMS (2005), pp. 141-173. · Zbl 1179.76065
[22] G. Mastroianni, G. Milovanovic. Interpolation Processes: basic theory and applications. Springer-Verlag Berlin Heidelberg (2008). · Zbl 1154.41001
[23] E. Meijering. A Chronology of Interpolation: From Ancient Astronomy to Modern Signal and Image Processing. Proceedings of the IEEE 90(3) (2002), pp. 319-342.
[24] E. T. Whittaker. On the functions which are represented by the expansions of interpolation-theroy. Proc. R. Soc. Edinburgh, 35 (1915), pp. 181-194 · JFM 45.1275.02
[25] C. E. Shannon. Communication in the presence of noise. Proc. Inst. Radio Eng., 37(1) (1949), pp. 10-21.
[26] C. Hermite. Sur la formule d’interpolation de Lagrange. Journal für die Reine und Ange-wandte Mathematik, 84(1) (1878), pp. 70-79. · JFM 09.0312.02
[27] G. D. Birkhoff. General mean value and remainder theorems with applications to mechanical differentiation and quadrature. Trans. Amer. Math. Soc., 7(1) (1906), pp. 107-136. · JFM 37.0308.02
[28] F. W. Bessel. Anleitung und Tafeln die stündliche Bewegung des Mondes zu finden. As-tronomische Nachrichten, II(33) (1824), pp. 137-141.
[29] G. Strang, G. Fix. A Fourier analysis of the finite element variational method. Constructive Aspects of Functional Analysis. Rome, Italy: Edizioni Cremonese. Centro Internazionale Matematico Estivo, (1973), pp. 793-840. · Zbl 0272.65099
[30] J. T. Becerra Sagredo. Z-splines: Moment conserving spline interpolation of compact support for arbitrarily spaced data. SAM Report. 2003-10 D-MATH ETH Zürich C. H. (2003).
[31] J. T. Becerra Sagredo. High-order Semi-Lagrangian Numerical Method for Reactive Flows. ETH-Thesis No. 17319. D-MATH ETH Zürich C. H. (2007).
[32] C. V. Beccari, G. Casciola, L. Romani. Construction and characterization of non-uniform local interpolating polynomial splines. J. of Comput. and Applied Math. 240 (2012), pp. 5-19. · Zbl 1255.65035
[33] T. Ueno, S. Truscott, M. Okada. New spline basis functions for sampling approximations, Numer. Algorithms 45 (2007) 283-293. · Zbl 1125.65014
[34] I.J. Schoenberg. Cardinal Spline Interpolation. Philadelphia, PA, SIAM (1973). · Zbl 0264.41003
[35] J. Karup.Über eine neue mechanische Ausgleichungsmethode, in Transactions of the Second International Actuarial Congress (London, UK) (G. King, ed), Layton (1899), pp. 31-77.
[36] G. King. Notes on summation formulas of graduation, with certain new formulas for con-sideration. J. Inst. Actuar., Vol. 41 (1907), pp. 530-565.
[37] E. Catmull, R. Rom. A class of local interpolating splines, in Computer Aided Geometric Design (New York, USA) (R.E. Barnhill and R. F. Riesengeld, eds), Academic Press (1974), pp. 317-326.
[38] H. L. Seal. Graduation by piecewise cubic polynomials: A historical review. Blätter der DGVFM 15 (1981), pp. 89-114. · Zbl 0467.62090
[39] B. Csébfalvi. Fast Catmull-Rom Spline Interpolation for High-Quality Texture Sampling. Computer Graphics forum. 37 (2) (2018), pp. 455-462.
[40] J. J Monaghan. Extrapolating B-splines for interpolation. J. of Comput. Physics, 60 (2) (1985), pp. 253-262. · Zbl 0588.41005
[41] M. Lin, T. Lin, H. Zhang. Error analysis of an immersed finite element method for Euler-bernoulli beam interface problems. International journal of numerical analysis and model-ing, 14 (6) (2017), pp. 822-841. · Zbl 1375.74088
[42] R. Bulirsch, H. Rutishauser. Interpolation und genäherte Quadratur. Mathematische Hilfs-mittel des Ingenieurs (R. Sauer and I. Szabó, eds), Springer-Verlag, New York US A (1968).
[43] D. Nelson. The Penguin Dictionary of Mathematics. Fourth Edition. Penguin Books. London, U.K. (2008).
[44] N. Macon, A. Spitzbart. Inverses of Vandermonde Matrices. The American Mathematical Monthly. 65 (2) (1958), pp. 95-100. · Zbl 0081.01503
[45] D. E. Knuth. The art of computer programming. Third Edition. Addison Wesley Longman. Reading, Massachusetts, U. S. A. (1997).
[46] B. Fornberg. Generation of Finite Difference Formulas on Arbitrarily Spaced Grids. Mathe-matics of Computation 51(184) (1988), pp. 699-706. · Zbl 0701.65014
[47] I. S. Berezin, N. P. Zhidkov. Computing Methods. Pergamon Press Ltd., London, U.K. (1965). · Zbl 0122.12903
[48] C. de Boor. A Practical Guide to Splines. Springer Verl. New York U. S. A. (1978). · Zbl 0406.41003
[49] Y. Liu, Y. Mori. Properties of Discrete Delta Functions and Local Convergence of the Im-mersed Boundary Method. SIAM J. Numer. Anal., 50(6) (2012), pp. 2986-3015. · Zbl 1268.65143
[50] J. M. Whittaker. Interpolatory function theory. Cambridge Tracts in Mathematics and Math-ematical Physics. Cambridge Univ. Press, Cambridge, U.K., (1935). · Zbl 0012.15503
[51] V. A. Kotelnikov. On the transmission capacity of the “ether” and wire in electrocommuni-cations. Modern Sampling Theory: Mathematics and Applications, J. J. Benedetto and P. J. S. G. Ferreira, Eds. Birkhäuser, Boston MA,(2000), ch. 2, pp. 27-45.
[52] H. Nyquist. Certain topics in telegraph transmission theory. Trans. Amer. Inst. Electr. Eng., 47 (1928), pp. 617-644.
[53] K. Kamemoto, M. Tsutahara. Vortex Methods: selected papers of the First International Con-ference on Vortex Methods, Kobe, Japan, 4-5 November 1999. World Scientific, (2000).
[54] J. T. Becerra-Sagredo, C. Málaga, F. Mandujano. A GPU-based Multi-level Algorithm for Boundary Value Problems. J. of Comput. and Appl. Math. 368 (2020), DOI: 10.1016/j.cam.2019.112481. · Zbl 1433.78028
[55] M. L. Minion, D. L. Brown. Performance of Under-resolved Two-Dimensional Incompress-ible Flow Simulations, II. J. of Comp. Physics, 138 (1997), pp. 734-765. · Zbl 0914.76063
[56] T. Hashimoto, I. Tanno, Y. Tanaka, K. Morinishi, N. Satofuka. Simultaion of doubly periodic shear layers using Kinetically Reduced Local Navier-Stokes equations on a GPU. Computers and Fluids. 88 (2013), pp. 715-718. · Zbl 1391.76101
[57] M. Bergdorf and P. Koumoutsakos. A Lagrangian particle-wavelet method. SIAM Multiscale Model. Simul. 5(3) (2006), pp. 980-995. · Zbl 1122.65085
[58] W. M. van Rees, A. Leonard, D.I. Pullin, P. Koumoutsakos. A comparison of vortex and pseudo-spectral methods for the simulation of periodic vortical flows at high Reynolds num-bers, J. Comput. Physics 230 (2011), pp. 2794-2805. · Zbl 1316.76066
[59] G. H. Cottet, J. M. Etancelin, F. Perignon and C. Picard. High order Semi-Lagrangian parti-cles for transport equations: numerical analysis and implementation issues, ESAIM: Mathe-matical Modelling and Numerical Analysis, 48 (2014), pp. 1029-1060. · Zbl 1310.65134
[60] J. Jiménez. Turbulence and vortex dynamics. Notes. Ecolepolytechnique, Paris (2004).
[61] J. Z. Wu, H. Y. Ma, M. D. Zhou. Vortical Flows. Springer-Verlag Berlin Heidelberg, Germany (2015).
[62] G. B. Arfken, H. J. Weber. Mathematical Methods for Physicists. Fourth Edition. Academic Press. San Diego U. S. A. (1995).
[63] C. S. Peskin. The immersed boundary method, Acta Numer. 11 (2002), pp. 479-517. · Zbl 1123.74309
[64] J. M. Stockie. Analysis and computation of immersed boundaries, with application to pulp fibres, Ph. D. thesis, Institute of Applied Mathematics, University of British Columbia (1997).
[65] R. P. Beyer, R. J. Leveque. Analysis of a one-dimensional model for the immersed boundary method, SIAM J. Numer. Anal. 29(2) (1992), pp. 332-364. · Zbl 0762.65052
[66] A. K. Tornberg, B. Engquist. Numerical approximations of singular source terms in differen-tial equations, J. Comput. Phys. 200(2) (2004), pp. 462-488. · Zbl 1115.76392
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.