RMVPIA: a new algorithm for computing the Lagrange multivariate polynomial interpolation

The problems of univariate polynomial interpolation of Lagrange or Hermite have been treated by several recent researches (Gasca and Lopez-Carmona J. Approx. Theory. 34 361–374 1982; Messaoudi et al. Numer. Algorithms J 80, 253–278 2019; Messaoudi and Sadok Numer. Algorithms J 76, 675–694 2017; Muhlbach Numer. Math. 31, 97–110 1978). The study of the multivariate polynomial interpolation is more difficult and the approaches are less obvious (Gasca and Lopez-Carmona J. Approx. Theory. 34, 361–374 1982; Gasca and Sauer 2000; Lorentz 2000; Muhlbach Numer. Math. 31, 97–110 1978; Neidinger Siam Rev. 61, 361–381 2019). In Gasca and Sauer (2000), there are a large number of interesting theoretical ideas developed around the theme in the last years of the last century. The numerical schemes proposed are based on the Newton formulas. Recently in (Siam Rev. 61, 361–381 2019), R.D Neidinger has studied the multivariate polynomial interpolation problem using the techniques of Newton’s polynomial interpolation and the divided difference. In this work, we propose another approach to study the problem of the Lagrange multivariate polynomial interpolation in a particular case where the set of the interpolation nodes is a grid. Indeed, to solve this problem, we will use the Schur complement (Brezinski J. Comput. Appl. Math. 9, 369–376 1983; Brezinski Linear Algebra Appl. 111, 231–247 1988; Cottle Linear Algebra Appl. 8, 189–211 1974; Ouellette Linear Algebra Appl. 36, 187–295 1981; Schur J. Reine. Angew. Math. 147, 205–232 1917) and we will give a new algorithm for computing the interpolating polynomial which will be called the Recursive MultiVariate Polynomial Interpolation Algorithm: RMVPIA. A simplified version and some properties of this algorithm will be also studied and some examples will be given.