1 Introduction

Trefftz methods are based on complete families of shape functions (or T-complete according to the terminology introduced by Herrera [33]) that are fully exact solutions of the partial differential equations (PDEs). Initiated a long time ago by Trefftz [87], they have been developed from the late seventies, see [43]. Since the PDE is automatically satisfied, only the discretization of the boundary is needed, which leads to strong reductions of the number of degrees of freedom (DOFs) as compared to other methods like the finite element method (FEM) or the finite difference method. Many informations about Trefftz methods can be found in several review papers, see for instance [33, 34, 46, 51, 73] and [35], or in some books, see [60, 72, 75] and [52] or in special issues of Advances in Engineering Software, Volume 24–1 (1995), of Engineering Analysis with Boundary Elements, Volume 36–1 (2012), and in several issues of Computer Assisted Methods in Engineering and Science. Many classes of shape functions are quoted in those papers, the most widespread being the harmonic polynomials [17] (i.e. \(1,Re(x+iy)^n,Im(x+iy)^n , n\ge 1\) for 2D Laplace equation), the fundamental solutions and several sorts of wave functions (plane, circular, spherical, corner, etc.). Most of the PDEs solved by Trefftz methods in the literature are linear, homogeneous with constant or piecewise constant coefficients. In this paper, extensions to any elliptic system of PDEs are discussed, especially in the non-linear range.

Another discretization technique, called Taylor meshless method (TMM), has been presented more recently in Zézé et al. [104] that relies on approximated solutions of the PDEs in the sense of Taylor series. When applied to a linear PDE with constant coefficients, it coincides with Trefftz method associated with harmonic polynomials. The calculation of a Taylor series amounts to compute derivatives and there are well established procedures known as algorithmic differentiation or automatic differentiation, see [29]. A generic method based on algorithmic differentiation has been proposed recently to solve any elliptic PDE in the sense of Taylor series, see [102]. Various applications to non-linear boundary value problems have been presented, from elementary ODEs in Zézé [103] and Tampango [83] to fully 2D and 3D non-linear large-scale systems of PDEs in Akpama et al. [1] and Yang et al. [102]. One central point of the present paper is the presentation and assessment of this approach to extend Trefftz methods in the non-linear range. In other words, one replaces the concept of a complete family of exact solutions by the concept of a “complete family of approximated solutions in the sense of Taylor series”. These shape functions are high degree polynomials and they are computed numerically by the technique of Taylor series. This procedure should permit extensions of Trefftz methods to any elliptic systems of PDEs.

Once the shape functions have been defined, the boundary and interface conditions have to be taken into account. Indeed in many cases, it is not possible to represent the whole solution by a single combination of shape functions and the domain has to be split in several subdomains. A perfect continuity across the interface is difficult to be achieved with shape functions that are not small degree polynomials, so this continuity is generally applied in a mean sense or at some specific collocation points. Many techniques have been used, sometimes with different names. Roughly boundary and interface conditions can be applied from a weak form, which requires to mesh the domain and to compute integrals, or from the strong form and a discretization by collocation. On one hand, Trefftz method may be considered as a variant of the FEM ([108] was talking about generalized FEM), the most representative one being the hybrid-Trefftz initiated in Jirousek and Leon [43] and Jirousek and Teodorescu [44] and Jirousek and Venkatesh [45]: in the hybrid-Trefftz method, the boundary and interface are split in elements, the main differences with FEM being the discontinuity of the main field and the possibility to choose larger elements because of the better accuracy of the approximation inside each subdomain. On the other hand, the Trefftz method can be applied in a meshless framework with a single approximation in the whole domain, which is often done within the method of fundamental solutions (MFS), see for instance [27] or [26]: among the notable exceptions to this one-domain MFS approach, there are some papers coupling MFS and hybrid-Trefftz method, see [93] or [94] and also the paper by Ingber et al. [39] who solved the diffusion equation by an iterative multi-domain procedure that was introduced earlier for radial basis functions. In this paper we shall not re-discuss in details all these strategies to account for boundary and interface conditions. Here as elsewhere, it does not seem possible to give a single and definitive answer to the famous question “to mesh or not to mesh” (see [38]), the two types of methods having their interest and their application fields.

The most significant advantage of Trefftz methods lies in a very strong reduction of the number of DOFs, due to the analytical solving inside each subdomain. Nevertheless according to Li et al. [59] , “the state-of-the-art of the analysis of Trefftz methods is behind that of the boundary element method (BEM)” and, at the same time, BEM [50, 69] is less popular than FEM. In other words, Trefftz methods are much less widespread than one might have thought by considering their excellent convergence properties. A first reason is the difficulty to control the matrix ill-conditioning generated by the interaction between many shape functions, which prevents applications to very large-scale problems. One can define “large-scale problems” as problems that cannot be treated or that could be very expensive within standard numerical techniques, say problems involving at least several hundred thousand unknowns within an equivalent FEM model. Most of the applications of Trefftz methods in the literature do not concern such problems, even if some recent results have shown that very large-scale problems can be solved in this framework, mainly for Helmoltz-type problems [80, 91], but also for non-linear PDEs [102]. This is an important point in view of applications to practical engineering problems and it will be re-discussed in this paper.

Another very important point is the treatment of non-linear PDEs. Essentially “typical PDEs addressed are linear, with piecewise-constant coefficients and homogeneous, i.e. with vanishing volume source” (from [35]). In fact a number of applications in the non-linear range have been presented in the literature, with two types of difficulties. First one has to find a particular solution and this is generally done by discretizing the domain by radial functions [27]. Second, because one does not have exact solutions of the tangent system, one uses an “analog operator” (concept introduced in Katsikadelis [48, 49]). These two ideas permit to solve non-linear PDEs, but the examples discussed in the literature do not highlight procedures sufficiently robust and efficient and permitting the treatment of large-scale industrial problems.

In this paper, a new attempt will be presented that is based on the concept of Taylor series. It should permit to solve any smooth elliptic system of PDEs, whether linear with constant coefficients, linear with variable coefficients or non-linear. Because the control of the matrix conditioning and round-off errors remains a central point in view of applications to large-scale problems and therefore to practical engineering problems, this point will be also revisited in the light of recent results. The paper will be split in two sections, the Sect. 2 focusing on linear problems and ill-conditioning and the Sect. 3 on non-linear equations.

2 About Trefftz Methods for Linear PDEs

Trefftz methods correspond to a very large class of numerical techniques with a lot of variants so that it seems impossible to summarize them in simple way. That is why we shall limit ourselves to a very selective review of research works of the literature by focusing on the techniques potentially useful for the numerical simulation of practical engineering applications. In this respect, the control of the conditioning, the ability to solve large-scale problems and the procedures for non-linear problems have a fundamental interest. Our discussion will be centered on these three points. In Sect. 2.1 the most popular shape functions will be presented briefly, especially the polynomials built by the method of Taylor series. Next a short summary of the discretization techniques of boundary and interface conditions is done in Sect. 2.2. The first key point is the treatment of large-scale problems and the control of matrix conditioning and it is discussed in Sect. 2.3. Finally an additional interest of Taylor series is mentioned in Sect. 2.4: there are a lot of hidden informations in a Taylor series, which permits ones to establish convergence acceleration procedures.

2.1 Exact and Approximated Shape Functions

Let us consider the example of Poisson equation with mixed Dirichlet–Neumann boundary conditions:

$$\begin{aligned} \mathcal {A}(u)= & {} \mathcal {L}u-f=-\varDelta u-f(\mathbf {x})=0\qquad in\quad \;\varOmega \end{aligned}$$
(1)
$$\begin{aligned} \mathcal {R}^u(u)= & {} u-u^{d}=0 \qquad on\quad \;\partial \varOmega _u \end{aligned}$$
(2)
$$\begin{aligned} \mathcal {R}^q(u)= & {} \frac{\partial u}{\partial n}-q^{d}=0 \qquad on\quad \;\partial \varOmega _q \end{aligned}$$
(3)

where the data are the functions \(f(\mathbf {x}),u^{d}(\mathbf {x}),q^{d}(\mathbf {x})\). Thus one has to vanish the domain residual \(\mathcal {A}(u)\) and the boundary residual \((\mathcal {R}^u(u),\mathcal {R}^q(u))\). Within Trefftz methods, the unknown is sought as a linear combination of shape functions that are exact solutions of the homogeneous equation, here \(\varDelta u=0\). In other words, the domain residual is exactly zero in the case of a homogeneous equation (i.e. \(f=0\) in Eq. 1) while the remaining Eqs. (2) and (3) will be taken into account by various techniques described in Sect. 2.2. Many such shape functions (called Trefftz functions) have been used in the literature and a complete list can be found in the references previously quoted. In this paper we mainly discuss three classes of Trefftz functions recalled in the Table 1: first the polynomials considered in the initial papers on the topics [43]; second the fundamental solutions studied by a large community; third the wave functions applied in vibro-acoustics, the-state-of-the-art permitting nowadays to solve practical engineering problems. But a great merit of Trefftz methods is to offer many possible shape functions that can be adapted to each particular situation. For instance Bessel and Hankel functions appear naturally for 2D Helmoltz equation, singular functions as \((r^\alpha cos(n\theta ), r^\alpha sin(n\theta ),\alpha \notin \mathbb {N} )\) can be very important near crack tips and corners, see [59], and there are specific functions for exterior domains.

Table 1 The most popular shape functions
Full size table

In the more general case of inhomogeneous equations (i.e. \(f\ne 0\)), one needs to define a particular solution \(\breve{u}(\mathbf {x})\) of Eq. (1) and this is not an obvious task except in some cases (e.g. if \(f(\mathbf {x})\) is constant or a Dirac function). That is why one has to give up building exact solutions of the PDE (1) and one solves it numerically. The most widely used method to build particular solutions is based on radial functions and this will be re-discussed shortly in Sect. 3.2.

Here we recall the method of Taylor series [99, 104] that permits to build both the particular solution and the general solution of the associated homogeneous equation. To explain this old procedure, let us consider first a simple ordinary differential equation (ODE):

$$\begin{aligned} \mathcal {A}(u)=-\frac{d^2u}{dx^2}+u-f(x)=0 \end{aligned}$$
(4)

The general solution of the ODE (4) is sought in the form of a Taylor series centered here at the point \(x=x_0\) and truncated at the order p:

$$\begin{aligned} \ u(x)=\sum _{n=0}^{p}\bar{u}(n)(x-x_0)^n \end{aligned}$$
(5)

So within the approach by Taylor series, the unknown u(x) is represented by the set of coefficients \(\bar{u}(n)\), \(0\le n \le p\). The given function f(x) and the domain residual \(\mathcal {A}(u)\) are represented in the same way by a set of Taylor coefficients. The technique consists in cancelling the Taylor coefficients of the residual up to the order \(p-2\):

$$\begin{aligned} \bar{\mathcal {A}}(n)=-(n+2)(n+1)\bar{u}(n+2)+\bar{u}(n)-\bar{f}(n)=0,\quad \forall {n} \in [0,p-2] \end{aligned}$$
(6)

Thus the Eq. (6) yields a recurrence formula permitting to express all the Taylor coefficients of the unknown as a function of the first two ones \(\bar{u}_{0}\) and \(\bar{u}_{1}\):

$$\begin{aligned} u(x)=\breve{u}(x)+\bar{u}_{0}N_1(x)+\bar{u}_{1}N_2(x) \end{aligned}$$
(7)

Hence this simple procedure yields a particular solution \(\breve{u}(x)\) and two Trefftz functions \(N_1(x)\) and \(N_2(x)\), these three functions being polynomials of degree p. In the case \(f(x)=1\), one can check easily that the exact solution is \(u(x)=1+\bar{u}_{0}\cosh {(x)}+\bar{u}_{1}\sinh {(x)}\) and that the so computed functions \((\breve{u}(x),N_1(x),N_2(x))\) are the truncated Taylor series of the exact solutions \((1,\cosh (x),\sinh (x)\)). This well-known analytical procedure was applied for a numerical purpose and in a multi-domain framework, see for instance [77, 103] or [83].

In addition, the Taylor series method is easily applied to inhomogeneous equations. Let us consider the following ODE that contains a variable coefficient:

$$\begin{aligned} \mathcal {A}(u)=-\frac{d^2u}{dx^2}+(1+x)u-f(x)=0 \end{aligned}$$
(8)

The Eq. (8) can be solved in the same way as Eq. (4) with only a slight modification in the recurrence formula:

$$\begin{aligned} \bar{\mathcal {A}}(n)=-(n+2)(n+1)\bar{u}(n+2)+(1+x_0)\bar{u}(n)+\bar{u}(n-1)- \bar{f}(n)=0 \end{aligned}$$
(9)

The procedure has been extended to some 2D [104] and 3D [99] equations in a relatively simple way. To illustrate it, let us consider the following 2D equation where a is a given constant:

$$\begin{aligned} \mathcal {A}(u)=-\varDelta u+au-f(x,y)=0 \end{aligned}$$
(10)

Here the unknown u(x, y) is written as a bi-variate truncated Taylor series:

$$\begin{aligned} \ u(x,y)=\sum _{n=0}^{p}\sum _{m=0}^{p-n}\bar{u}(m,n)(x-x_0)^m (y-y_0)^n \end{aligned}$$
(11)

So this function is represented by a set of coefficients with two indices \(\bar{u}(m,n)\). The given function f(x, y) is represented in the same manner. The coefficients of the Taylor series of the residual are given by:

$$\begin{aligned} \bar{\mathcal {A}}(m,n)=-(m+2)(m+1)\bar{u}(m+2,n)-(n+2)(n+1)\bar{u}(m,n+2) +a\bar{u}(m,n)-\bar{f}(m,n)=0 \end{aligned}$$
(12)

Thus one has obtained a recurrence formula (12) that permits to compute all the Taylor coefficients of u(x, y) as a function of \(N=2p+1\) coefficients

$$\begin{aligned} \mathbf {c}=\{\bar{u}(0,0),\bar{u}(0,1),\ldots , \bar{u}(0,p), \bar{u}(1,0),\bar{u}(1,1),\ldots , \bar{u}(1,p-1)\}\in \mathcal {R}^N \end{aligned}$$
(13)

The particular solution and the set of polynomial solutions of the homogeneous equations are easily deduced from the recurrence formula (12): the particular solution by choosing \(\mathbf {c}=0\), the first shape function \(N_1(x,y)\) by choosing \(f=0, c_1 =1, c_n =0\) for \(n\ge 2\), the second shape function \(N_2(x,y)\) by choosing \(f=0, c_2 =1, c_n =0\) for \(n\ne 2\), etc. Finally the sought solution of Eq. (10) is a linear combination of these \(2p+2\) polynomial solutions:

$$\begin{aligned} \ u(x,y)=\breve{u}(x,y) +\sum _{k=1}^{N}c_kN_k(x,y)=\breve{u}(x,y) +\mathbf {c}.\mathbf {N}(x,y) \end{aligned}$$
(14)

The final form (14) depends on the unknown vector \(\mathbf {c}\in \mathcal {R}^N\) and it is exactly the same as in other variants of the Trefftz method. From Eq. (14), one deduces easily the corresponding expression of the flux \(q=\frac{\partial u}{\partial n}\), whatever the type of the Trefftz functions:

$$\begin{aligned} \ q(x,y)=\breve{q}(x,y) +\mathbf {c}.\mathbf {Q}(x,y) \end{aligned}$$
(15)

We have just described the simplest way to build approximate solutions by using the polynomials issued from one Taylor series. A well-known improvement consists in replacing the polynomials by equivalent rational fractions called Padé approximants, an example being presented in Sect. 2.4. It is also possible to combine several Taylor series in an approach called “multi-point Taylor series”. Up to now, these multi-point series were only applied to ODEs, see [62, 105]. Typical results are presented in Fig. 1, where the simple ODE (4) is solved with \(f(x)=1\) and the boundary conditions \(u(-3)=u(3)=0\). One sees that the two-point Taylor series gives more accurate results than a one-point Taylor series leading to about the same global degree. Moreover there are cases where the two-point series converges while the one-point diverges. We refer to López et al. [62], Zézé et al. [105] for more information about this promising technique.

Fig. 1
figure 1

Accuracy of Taylor two-point versus Taylor one-point. Note that the degree of a two-point approximation for \(p=5\) is about the same as a one-point Taylor series for \(p=10\)

Full size image

2.2 Main Boundary Discretization Techniques

Once the PDE has been solved exactly or approximately, one has to account for the boundary conditions (2) and (3). In most of the papers in the literature, a multi-domain approach has to be considered, which implies to satisfy also transmission conditions, i.e. the continuity of the main field u and of the flux q. The simplest way is the collocation technique. To account for the boundary conditions, one chooses M points on the boundary \(\mathbf {x}_j,1\le j\le M\) (\(M_1\) points are on \(\partial \varOmega _u\), \(M_2=M-M_1\) points on \(\partial \varOmega _q\)). Next one requires that the boundary conditions are exactly satisfied on this cloud of points [60]:

$$\begin{aligned} u(\mathbf {x}_j)=u^{d}(\mathbf {x}_j),\quad 1\le j\le M_1, \qquad \ q(\mathbf {x}_k)=q^{d}(\mathbf {x}_k),\quad M_1+1\le k\le M \end{aligned}$$
(16)

In general, this simple approach fails and this is easily understood in the case of a circular boundary and of a discretization by harmonic polynomials: then the sum (14) becomes a Fourier series and one knows that it is not possible to identify a Fourier series from a too small data set. That is why it is recommended to use more collocation points than DOFs (\(N<M\)), see for instance [51]. In a similar way, a least-square collocation technique was proposed in Zézé et al. [104] to account for the boundary conditions within the framework of the Taylor meshless method. This leads to minimize the following function:

$$\begin{aligned} \mathcal {J}(\mathbf {c})=\sum _{j=1}^{M_1}\left| u(\mathbf {x}_j)-u^{d}(\mathbf {x}_j) \right| ^2+w\sum _{k=M_{1}+1}^{M}\left| q(\mathbf {x}_k)-q^{d}(\mathbf {x}_k)\right| ^2 \end{aligned}$$
(17)

A free weighting parameter w has been introduced for a better control of the matrix conditioning. The minimization of the function (17) leads to a classical linear problem \(\mathbf {K.c}=\mathbf {F}\), where the matrix \(\mathbf {K}\) is symmetric and positive definite. Many authors prefer to solve directly the overdeterminated problem (16) with \(M>N\) by the Singular Value Decomposition (SVD) that is available for instance in Matlab and that permits to use easily some regularization methods, see [63]. Li et al. [59] recommend this procedure rather than the least-square technique because the condition number is much better: indeed [59, 60] prove that the condition number issued from least-squares is the square of that of the initial problem (16). This is right, but it is not clear whether SVD remains efficient as a linear solver for large-scale problems. Note that this discussion between least-squares and overdeterminated system is not new, see [14, 96, 97].

In the case of a splitting in two subdomains \(\varOmega _1\) and \(\varOmega _2\), one needs \(M_r\) additional collocation points on the interface (\(\mathbf {y}_{m}\), \(1\le m \le M_{r}\)), the function to be minimized being modified as follows:

$$\begin{aligned} \mathcal {F}(\mathbf {c_1,c_2})=\mathcal {J}_1(\mathbf {c_1})+\mathcal {J}_2 (\mathbf {c_2})+w_1\sum _{m=1}^{M_r}\left| u_{1}(\mathbf {y}_m)-u_{2}(\mathbf {y}_m) \right| ^2+w_2\sum _{m=1}^{M_r}\left| q_{1}(\mathbf {y}_m)-q_{2}(\mathbf {y}_m)\right| ^2 \end{aligned}$$
(18)

where \(\mathcal {J}_1(\mathbf {c_1})\) and \(\mathcal {J}_2(\mathbf {c_2})\) are the functions as in Eq. (17) and defined on the two subdomains. Variants based on Lagrange multipliers have been proposed in Tampango et al. [85] and numerical tests in Yang et al. [101] have established that they have about the same efficiency as the least-square collocation based on Eq. (18).

Often the boundary discretization within Trefftz methods is deduced from a weak form of the boundary and interface conditions and a lot of variants have been proposed in the literature. Roughly, they can be grouped into two main categories: the hybrid-Trefftz method that introduces an independent unknown field on the interface and the methods coupling directly the fields lying on the two sides of an interface. For instance the boundary conditions can be treated from a Galerkin method as:

$$\begin{aligned} \int _{\partial \varOmega _{u}}\mathcal {R}^u q^{*}dS-\int _{\partial \varOmega _{q}}\mathcal {R}^q u^{*}dS=0 \end{aligned}$$
(19)

but also by least-square method or various variational formulations [51, 58]. The same holds for transmission conditions. The latter class of methods was called “frameless methods” in Pluymers et al. [70] in contrast to Hybrid-Trefftz methods based on a frame consisting on an independent field defined on the interfaces as skeched in Fig. 2. Generally the transmission conditions within wave-based methods [80, 91] are discretized by such frameless techniques.

In this paper, we did not try to compare the respective performance of collocation, frameless weak forms and hybrid methods. Indeed it seems difficult to find in the literature a reasoned discussion on this topics, each paper limiting generally to validate its own procedure.

Fig. 2
figure 2

A classical description of an hybrid-Trefftz element \(\varOmega _{e}\) in 2D . The unknown function on each segment of the boundary \(\partial \varOmega _{e}\) is described as for 1D finite element interpolation. Hierarchical polynomials can also be used, see [21]. Inside the element, another independent function is obtained by local solution of the PDE as in (14)

Full size image

2.3 Matrix Conditioning and Application to Large-Scale Problems

All variants of Trefftz methods have excellent properties of rapid convergence and of reduction of the number of DOFs and, from this point of view, they should be widely used for engineering simulations. Actually this is not exactly the case: indeed it remains difficult to apply them to large-scale problems because the matrices become more and more ill-conditioned when the size of the model increases. In this section, we discuss this crucial question of the application of Trefftz methods to large-scale problems. Of course the term “large-scale” has no mathematical definition. In this paper a numerical model will be considered as large-scale when the equivalent finite element model is beyond 100 000 DOFs, this limit being quite modest by comparison with the current state-of-the-art in computational engineering. Moreover the concept of “equivalent FEM model” is not completely clear. For instance we have got an error of \(10^{-2.98}\) with a FEM-mesh and of \(10^{-3.2}\) with a much finer mesh: in such a case, what is the equivalent mesh size to get error less than \(10^{-3}\)? Similarly one cannot define the concept of relevant benchmark in a absolutely indisputable way. Nevertheless such comparisons between numerical methods are essential for evaluating their efficiency and they are too rare in the literature concerning Trefftz methods

It is widely accepted that matrix ill-conditioning is the main cause of loss of accuracy of discretization techniques observed when increasing the number of DOFs. However, there is no direct relation between the condition number and the maximum inaccuracy that may occur in an algorithm. This fact can be illustrated by a very simple change of variables used recently to improve the conditioning within Extended FEM, see [4] and [31]. Let us consider a linear problem \(\mathbf {K.c}=\mathbf {F}\), where the square matrix \(\mathbf {K}\) is symmetric and positive definite. Thus these authors define, first a diagonal matrix \(\mathbf {D}\) whose elements are \(d_{ii}=\frac{1}{\sqrt{k_{ii}}}\) (no summation), second a “scaled matrix” \(\mathbf {H}=\mathbf {D.K.D}\) and finally a change of variables:

$$\begin{aligned} \mathbf {H}. \mathbf {c}^{new}=\mathbf {F}^{new},\qquad \mathbf {c}=\mathbf {D}.\mathbf {c}^{new},\qquad \mathbf {F}^{new}=\mathbf {D}.\mathbf {F} \end{aligned}$$
(20)

In this way the scaled matrix \(\mathbf {H}\) has diagonal terms equal to 1 and a condition number lower than the one of the initial matrix \(\mathbf {K}\). One might wonder which condition number ( \(\mathbf {H}\) or \(\mathbf {K}\)) is the most influencing for the stability of the numerical solving. Morever with the change of variables (20), one deals with a better conditioned matrix, what will be evaluated later.

Let us consider a significant example within 3D linear isotropic elasticity, from Yang et al. [99]. The domain is the unit ball, the exact solution is a fundamental solution with a source point at \(\mathbf {X}_{0}\) and one considers a Dirichlet boundary value problem. This problem is solved by combining harmonic polynomials of degree p on the whole domain with the boundary collocation technique (17). Three cases have been studied: a very flat response for \(\mathbf {X}_{0}=[100, 100, 100]\), a response with stronger gradients for \(\mathbf {X}_{0}=[1, 1, 1]\) and a middle case for \(\mathbf {X}_{0}=[2, 2, 2]\). The maximal relative error is plotted in Fig. 3 as a function of the condition number of the scaled matrix \(\mathbf {H}\). Twelve values of the degree have been chosen from \(p=5\) up to \(p=60\). The flat function is recovered very accurately for a small degree at a level very close to the unit round-off error within the double precision format ( \(1.1 \times 10^{-16}\)). Next the error increases with the degree due to the propagation of the round-off approximations. It increases more or less linearly with the condition number in a log-log plot. In the two other cases, one observes first an exponential convergence, as expected for a Taylor series, up to an accuracy reversal point that occurs for \(p=25\) and \(p=40\) respectively. Very similar behaviors have been documented, e.g. by Schaback [81] and Cheng et al. [16] in the case of radial shape functions, by Pluymers et al. [70] with wave functions or by Ku et al. [53] with alternative shape functions (see the Fig. 2 in the latter paper): a very rapid convergence for a rather small number of DOFs is followed by an accuracy reversal beyond which the accuracy deteriorates because of the propagation of round-off errors and the strong influence of matrix ill-conditioning. So the challenge is clear: to what extent these losses of accuracy due to ill-conditioning perturb the responses for large numbers of DOFs? This phenomenon of accuracy reversal was called “Schaback uncertainty principle” in Cheng et al. [16].

Fig. 3
figure 3

Accuracy reversal within 3D linear elasticity. One tries to recover the fundamental solution at the source point \(\mathbf {X}_{0}\) by combining harmonic polynomials whose degree varies from \(p=5\) to \(p=60\). The maximal error is plotted as a function of the condition number of the scaled matrix. Three locations of the source \(\mathbf {X}_{0}=[1,1,1]\), \(\mathbf {X}_{0}=[2,2,2]\), \(\mathbf {X}_{0}=[100,100,100]\) and twelve values of the degree from \(p=5\) up to \(p=60\) are considered

Full size image

Despite this difficulty, some large-scale problems have been solved recently by Trefftz methods, most of them concerning 3D Helmoltz equations and wave-based (WB) shape functions to compute the response of vibrating systems coupling fluids and solids. The challenge is the medium-frequency range, small frequencies being easily treated by FEM and large frequencies by acoustic models. In Van Genechten et al. [91] only the fluid is represented in a one-domain approach and tremendous gains have been obtained, with a ratio larger than 100 in terms of DOFs (4500 for WB and 572,000 for FEM) and also important gains in terms of computation time. In Riou et al. [80] and Cattabiani [13], the method is called “Variational Theory of Complex Rays”, the fluid and the containing shells are coupled and the studied systems are complex and of industrial interest. The equivalent FEM models, when they were able to be solved, contain much more than \(10^{5}\) DOFs and the gains in terms of DOFs and computation time are of the same order as in Van Genechten et al. [91]. Let us specify that [13] (PhD, chapter 5) solved a problem with 20,800 DOFs distributed in 40 subdomains, which corresponds certainly to more than 1 million DOFs in an equivalent FEM model. The same order of magnitude is mentionned in a recent contribution [55]. Hence it appears clearly that large-scale problems can be solved by wave-based methods, but despite these excellent results, the matrices remain generally very ill-conditioned, which is detailed in the previously quoted papers and also in Riou [79] and Hiptmair et al. [36]. If these wave-based methods have achieved such performances since few years, they have been developed since a long time and are the results of long research works, see for instance [24, 54, 56, 57, 70] or [23].

Table 2 Laplace problem in a large box \(25\times 25\times 1\)
Full size table

To our best knowledge, the solution of large-scale problems by alternative Trefftz methods was obtained only recently and by the method of Taylor series [99]. These authors simply combine 3D harmonic polynomials with the multi-domain boundary collocation technique summarized by the formula (18). The numerical tests concern the Laplace equation in a cuboid of dimensions \(\ell _{x}\times \ell _{y }\times 1\). The exact solution is \(u(x,y,z)=\sin (\pi x)\sin (\pi y)\frac{\sinh (\sqrt{2} \pi z)}{\sinh (\sqrt{2} \pi )}\) and it serves as Dirichlet data. The domain is split in cubes (“elements”) of size \(1\times 1 \times 1\) and the series have been computed up to the degree \(p=10\). The computations have been performed with a commercial software (MATLAB R2012b) in a personal computer under the system Windows 10 with intel(R) core(TM) i5-4310U type CPU and 16GB computer memory.

This comparison Taylor/FEM is summarized in Table 2. The first significant information is the number of DOFs of the finite element model: more than 3 millions. Second information: the computation times obtained with the two methods are of the same order. The most important result may be the condition number of the initial matrix that remains under control, its value \(10^{10}\) being widely acceptable by the modern linear solvers. This means that large-scale computations can be performed by Trefftz methods provided that the local number of DOFs is not too large (here \((10+1)^{2}=121\)) and the number of subdomains is sufficiently large. Let us now focus more on the crucial problem of conditioning. In this respect, one increases the size of the domain, the subdomains (unit cubes), the degree and the sought solution remaining the same, see Table 3. The most surprising result is the invariance of the condition number when the domain size increases and this applies both for the initial matrix and for the scaled matrix. As a consequence, the accuracy does not seem influenced by the size of the domain. In other words, Trefftz methods could be much more widely used for large-scale problems provided that the domain is split into a sufficiently large number of subdomains. Let us remark also the size of the largest solved Trefftz problem: more than hundred thousand DOFs, corresponding to more than 4.5 millions DOFs in an equivalent finite element calculation. A similar result was obtained recently by Chu et al. [18] with radial basis functions, with a similar conclusion as here: “the more subdomains, the smaller the condition number”. The h-convergence yields another test to assess the ability of Taylor/Trefftz method to solve large-scale problems. One considers the same Laplace problem in a box \(10 \times 10\times 1\) with a degree \(p=8\) and one increases the number of subdomains. The condition number of the initial matrix remains under control (\(10^{14}\)) even for the largest model (72,900 DOFs) while the condition number of the scaled matrix remains almost constant at a low level (\(10^{5}-10^{6}\)), see Table 4. At the same time, the accuracy improves, but much more slowly as with p-convergence, which is quite usual. This confirms once more that the ill-conditioning is not directly related to the size of the global problem, but only to the number of DOFs in each element.

A last test is presented to check the p-convergence, see Table 5. The result is consistent with previous results, see [99] or Fig. 3: one converges very rapidly with the degree up to a point of accuracy reversal occuring here at about \(p=20\). At the same time, the condition number increases dramatically with the initial matrix as well as with the scaled matrix. Once again this is the paradox known as Schaback uncertainty principle: the number of local shape functions is the best way to increase the accuracy, but there is a limit due to ill-conditioning beyond which the convergence is stopped. Here this limit occurs for 441 DOFs, [76] said that he was not able to compute for 1000 DOFs, a similar limit is often mentioned with wave-based methods even if [91] solved Helmholtz equation with 4500 DOFs in one domain, but with a condition number of \(10^{20}\). Hence there is a sort of glass ceiling of some hundreds DOFs, sometimes more, that limits the size of the local model, but we did not see such a limit for the number of subdomains and the size of the full model.

The interest for a subdivision in subdomains to bypass the problem of ill-conditioning is not new. The first papers [39, 47, 61, 98, 106] were based on Schwarz iterative method. Note that [39] did the same remark as here: “the higher the order of the basis functions, the worse the condition number, and the better the accuracy”. Various techniques are available to join the solutions in several subdomains, as sketched in Sect. 2.2. The numerical tests in the present paper were obtained with a relatively simple least-square collocation technique. Unfortunately we did not see in the literature any detailed comparison between these discretization techniques. Likely the existence of a splitting in a sufficiently large number of subdomains is more important than the choice among all these coupling methods and most of the existing methods should permit to solve large-scale problems when associated with a suitable splitting in subdomains.

Table 3 Stability of Taylor meshless method with respect to the size of the domain
Full size table
Table 4 Convergence with the number of subdomains (h-convergence) within Taylor meshless method and control of the condition number when the size of the problem increases
Full size table
Table 5 Convergence with the degree within Taylor meshless method
Full size table

2.4 A Taylor Series is not Only a Polynomial

In the case of shape functions generated by the method of Taylor series, these shape functions appear as high degree polynomials. But it is known that “a reasonable number of terms of a perturbation series will reveal part of the analytic structure of the solution”, see [90]. For instance within the Asymptotic Numerical Method [20], one computes a solution path in terms of a Taylor series with respect to a path parameter. It has been established that an a posteriori analysis of this series provides an accurate estimate of the radius of convergence, even for a vectorial series of large dimension, see [25]. More simply one can estimate the interval where the series is very accurate and in this way define an automatic continuation procedure that works even for FEM models involving millions of DOFs, see [64]. Moreover there are many acceleration procedures permitting to improve the solution by a posteriori calculations, see [8]. It would be not easy to apply these ideas inside a generic numerical procedure. Here one just illustrates this concept of hidden information and the possibility of acceleration procedure in the case of a Laplace problem \(\varDelta u=0\) in the unit disk \(\varOmega =\{(x,y) \; \vert \; x^2+y^2\le 1\}\). The problem is solved by combining harmonic polynomials centered in \(x=y=0\). The exact solution is \(u_{ex} =\frac{x-x_0}{(x-1.2)^2+(y-0.3)^2}\) and it serves as a Dirichlet data.

The Taylor series converges very slowly because the solution has a singular point (1.2, 0.3) rather close to the domain. A truncation at the order \(p=12\) leads to an error in the range 5–10% in a large part of the domain and to an error more than 50% in the direction of the singular point \(\theta _0=\arctan (\frac{1}{4})\). This series has been analyzed in Tampango et al. [84]. The bivariate function u(x, y) becomes univariate along rays \((x,y)=t(\cos \theta , \sin \theta )\). Each series in t has been transformed in an asymptotically equivalent rational fraction that is known as Padé approximants, see [5]. By this simple and very classical procedure, one gets an accurate solution with an error less than \(10^{-4}\) in a large part of the domain and of about 0.1% near the singularity, see Table 6 for the details concerning this convergence acceleration. This illustrates clearly that a Taylor series represents much more than a polynomial approximation because a poor polynomial approximation contains accurate rational fractions. Moreover [84] were also able to recover very accurately the location of the singularity \((x_0,y_0)=(1.2,0.3)\) from this Taylor series at the order \(p=12\).

In summary, a Taylor series may contain a lot of informations that can be extracted by clever manipulations, see [5, 84, 90]. Likely some additional efforts should be necessary to define robust numerical procedures to achieve this extraction.

Table 6 Convergence acceleration along rays by Padé approximants from a series at order \(\hbox {p}=12\)
Full size table

3 Trefftz Methods for Non-Linear PDEs

In the previous part, we have seen that Trefftz methods could be much more widely applied, especially to large-scale problems, if one is able to control matrix ill-conditioning by using appropriate domain decompositions. In the present part, we are discussing a second important topics: the application to non-linear problems. If the previous discussion about conditioning could concern many variants of Trefftz methods, here we mainly focus on Taylor series that yields a systematic procedure to get quasi-exact solutions of linearized PDEs. As recalled in Sect. 2.1, the computation of shape functions by Taylor series is a generic procedure that can be applied to many PDEs and this advantage seems difficult to be extended to other Trefftz methods.

3.1 Linearization Algorithms

Let us consider a class of non-linear PDEs that can be written in a general form as:

$$\begin{aligned} \mathcal {R}(u,\lambda )=0 \end{aligned}$$
(21)

where u is the unknown field, \(\mathcal {R}\) is the domain residual and \(\lambda\) is a real number. This PDE can be completed by boundary conditions as in the Eqs. (2) and (3). Newton iterative method is the simplest and most widespread algorithm to solve non-linear equations (the parameter \(\lambda\) can be omitted here):

$$\begin{aligned} \begin{aligned} &\mathcal {L}_{t}(u^{(i)})v= -\mathcal {R}({u^{(i)}}) \\ & u{^{(i+1)}}=u^{(i)}+v \end{aligned} \end{aligned}$$
(22)

where \(\mathcal {L}_{t}(u^{(i)})\) is the tangent operator at the point \(u^{(i)}\). For instance, if we apply it to the following PDE

$$\begin{aligned} -\varDelta u+u^{3}=g(\mathbf {x}) \end{aligned}$$
(23)

where \(g(\mathbf {x})\) is a given function, the incremental equation (22) reads

$$\begin{aligned} \begin{aligned}&\mathcal {L}_{t}v=-\varDelta v+3(u^{(i)})^{2}v=\mathcal {R}(\mathbf {x}) \\&\mathcal {R} (\mathbf {x})=g(\mathbf {x})-u^{(i)3}+\varDelta u^{(i)} \end{aligned} \end{aligned}$$
(24)

Newton method has excellent properties of convergence and robustness. Many variants (modified Newton, Picard, etc.) have been proposed to relax the requirement of one matrix inversion per iteration, but such procedures are not very popular within the finite element community because of poor convergence properties and mostly a lack of reliability.

A very important improvement is the Newton–Raphson method that is a continuation method taking advantage of the presence of the scalar parameter \(\lambda\). From a starting point \((u_{0},\lambda _{0})\) considered as a quasi-exact solution of Eq. (21), one first uses a tangent approximation as:

$$\begin{aligned} &\mathcal {L}_{t}(u_{0},\lambda _{0})\varDelta u= {} -\frac{\partial \mathcal {R}}{\partial \lambda }(u_{0},\lambda _{0})\varDelta \lambda \nonumber \\ & u^{pred}= {} u_{0}+\varDelta u \nonumber \\ & \lambda ^{pred}= {} \lambda _{0}+\varDelta \lambda \end{aligned}$$
(25)

This approximate “prediction solution” \((u^{pred},\lambda ^{pred})\) has to be corrected by Newton iterations as in Eq. (22). The main advantage of the method is its robustness and flexibility, what can be further improved by the so-called arc length techniques [78].

Of course the latter class of methods is very widely applied and is the default procedure in the most popular commercial finite element packages. A difficulty with such methods is the necessity to choose a priori the step length \(\varDelta \lambda\). This difficulty is removed with the Asymptotic Numerical Method that relies on Taylor series with respect to a scalar parameter like \(\lambda\), see for example [19, 20, 25, 64]. Let us consider for instance this simple two-point boundary value problem in the interval [0, 1] and depending on a scalar parameter \(\lambda\):

$$\begin{aligned} &\mathcal {R}(u)= {} -\frac{d^2u}{dx^2}+u^{2}-\lambda =0 \qquad x\in [0,1] \nonumber \\ & u(0)= {} u(1)=0 \end{aligned}$$
(26)

ANM relies on Taylor series with respect to a scalar parameter, for instance the scalar parameter \(\lambda\) appearing in the ODE (26). In fact it is often more efficient to choose another parameter “a” that will be specified later. So the unknown function and the parameter \(\lambda\) are expanded in Taylor series:

$$\begin{aligned} u(x)-u_{0}(x)= & {} \sum _{n=0}^{N}a^{n}u_{n}(x) \end{aligned}$$
(27)
$$\begin{aligned} \lambda -\lambda _{0}= & {} \sum _{n=0}^{N}a^{n}\lambda _{n} \end{aligned}$$
(28)

An usual identification of the Taylor coefficients leads to a recurrent family of ODEs characterizing each term of the Taylor series (27) and (28):

$$\begin{aligned}&-\frac{d^2u_{n}}{dx^2}+2u_{0}(x)u_{n}(x)+f_{n}(x)-\lambda _{n}=0 \end{aligned}$$
(29)
$$\begin{aligned}&f_{n}(x)=\sum _{k=1}^{n-1}u_{k}(x)u_{n-k}(x) \end{aligned}$$
(30)

Thus one gets a family of equations with variable coefficients in a very similar way as with the Newton iterative algorithm (22), where the unknowns are the Taylor coefficients \(u_{n}(x)\). Note that one equation is lacking to define the Taylor coefficient \(\lambda _{n}\) of the parameter; this point will be explained in Sect. 3.4. The series (27)–(30) characterizes one ANM-step and it is easy to deduce the range of validity of this Taylor approximation, which defines a posteriori the step length, see [19] and Sect. 3.4.

In the next sections, we re-discuss briefly some methods to discretize such equations with variable coefficients.

3.2 Trefftz Method and Non-Linear Problems in the Literature

Likely the most widely applied models in mechanical engineering concern fluid dynamics, plastic behavior and large strain solid mechanics, but there are very few applications of Trefftz methods to these fields. Hyper-elasticity is the simplest class of models in non-linear solid mechanics, but it seems that the only applications of Trefftz methods to hyper-elasticity are in Akpama et al. [1] and Askour et al. [3], one significant result being recalled in Sect. 3.6. The first paper about Trefftz methods applied to plastic bodies is due to Zieliński [107] and it was published about 30 years ago, but it has been followed by less than ten other papers, see [6, 9, 22, 40, 41, 74, 82, 95], to be compared with the hundreds of papers published each year in the field of computational plasticity. Concerning fluid flows, the linear Stokes problem was studied a long time ago by Poitou et al. [71], but non-linear fluid models have been addressed more recently. One can mention some interesting papers about Navier-Stokes equations [10, 11, 28, 66], mainly with applications to a classical benchmark called “lid-driven cavity”, especially thanks to a domain decomposition approach. Likely these few papers are the most significant applications of Trefftz method to non-linear engineering problems involving relatively large-scale models. Nevertheless these tests concerns only the 2D lid-driven cavity, the equivalent finite element calculations needing only a few tens of thousands DOFs, see [12].

A consistent linearization of a non-linear PDE leads naturally to non homogeneous equations like Eq. (24), i.e. equations such that it is generally not possible to get analytically an exact particular solution and a fortiori a T-complete family of exact solutions of the associated homogeneous equations. Generally this particular solution is obtained by radial functions, see for instance [26, 27], the r.h.s. being interpolated in the form:

$$\begin{aligned} \mathcal {R}(\mathbf {x})\approx \sum _{k=1}^{ndom} d^{k}f_{k} \end{aligned}$$
(31)

where \(f_{k}=f(r_{k}(\mathbf {x}))\) are a family of radial functions as the multiquadrics (\(f(r)=(r^{2}+c^{2})^{-1/2}, r_{k}=|\mathbf {x}-\mathbf {x}_{k}|\), see Table 1) defined from a cloud of collocation points \(\mathbf {x}_{k}\) distributed in the body. If most of the applications in the literature are based on these radial functions, alternative shape functions have been proposed, like the ones introduced by Moldovan [65] to solve instationary problems. In this form, the method (generally referred as MFS-MPS [88, 89]) will involve two matrices, the first one to define the coefficients \(d^{k}\) of the interpolation (31) from the residual \(\mathcal {R}(\mathbf {x})\), the second one to account for the boundary conditions. If one iterates from \(u_{(i)}=0\) in Eq. (22) or if Picard method is used instead of Newton method, the two matrices can be inverted separately and, because of this uncoupling, MFS-MPS can be considered in this case as a boundary only method.

The latter method can be extended to problems where one does not know a complete family of solutions by using the so-called Analog Equation Method [48]. The method introduces an “analog operator” like \(\mathcal {L}^*=-\varDelta\) and rewrites the Eq. (1) as

$$\begin{aligned} \mathcal {L}^*v=f-(\mathcal {L}-\mathcal {L}^*)v \end{aligned}$$
(32)

Often the Eq. (32) is solved iteratively, but such an iterative procedure is hazardous and the convergence is ensured only for small problems or for cases where the preconditioner \(\mathcal {L}^*\) is not too different from the initial operator \(\mathcal {L}\). Anyway such techniques, based on the inversion of a matrix that is not the consistent tangent matrix, are rarely used in the most common finite element packages, because of their lack of reliability. Note that the most recent papers [2, 42] about non-linear meshless methods do not use a consistent tangent matrix and there is no evidence that their methods could be extended to large-scale problems.

A more general procedure, called one-stage method, has been proposed in Balakrishnan and Ramachandran [7] and Wang and Qin [92] and Chen et al. [15]. The idea is to combine linearly two classes of shape functions: the solutions \(\mathbf {N}\) of the homogeneous problem as previously and a family of radial functions \(\mathbf {M}\) to balance the r.h.s. as in Eq. (31):

$$\begin{aligned} \ v(\mathbf {x})=\mathbf {c}.\mathbf {N}(\mathbf {x}) + \mathbf {d}.\mathbf {M}(\mathbf {x}) \end{aligned}$$
(33)

where, for instance, the radial functions \(M_{k}(\mathbf {x})\) are obtained analytically from \(f_{k}(\mathbf {x})\) via the analog operator: \(\mathcal {L}^*(M_{k})=f_{k}\). The global problem combines the boundary conditions and the interpolation inside the domain as in Eq. (31). In other words, the shape functions \(\mathbf {N}(\mathbf {x})\) and \(\mathbf {M}(\mathbf {x})\) follow from the analog operator while the discretized system follows from the consistent tangent operator. This one-stage method is generic and it works well, but it is no longer boundary-only because Eq. (33) couples the boundary variables \(\mathbf {c}\) and the volume variables \(\mathbf {d}\). Therefore it looses the first advantage of Trefftz method that is to avoid the domain discretization. In the next section, it will be shown that this drawback can be bypassed by using the Taylor series method that permits to solve the PDE analytically.

3.3 Generic Procedures to Solve Non-Linear PDEs by Taylor Series

One now describes the method of Taylor series to solve linearized PDEs, as previously presented in Sect. 2.1. More precisely, one tries to compute the particular solution and the T-complete family of solutions of the associated homogeneous problem, these solutions being approximated in the sense of Taylor series. The principle is to vanish the truncated Taylor series of the residual. For instance if one comes back to the non-linear Poisson Eq. (23) and one linearizes it as in Eq. (24), one needs to compute the Taylor series of the residual (24), i.e. the Taylor series of the given function \(g(\mathbf {x})\), of the Laplacian \(\varDelta u_{(i)}\) and of products like \(w={(u^{(i)})}^{2}\), vw, \({(u^{(i)})}^{3}=wu^{(i)}\). Each field is represented by a truncated series, here written in the 3D case:

$$\begin{aligned} u(x,y,z)=\sum _{m_{1}=0}^{p}\sum _{m_{2}=0}^{p-m_{1}}\sum _{m_{3}=0}^{p-m_{1}-m_{2}} \bar{u}(m_{1},m_{2},m_{3})(x-x_0)^{m_{1}}(y-y_0)^{m_{2}}(z-z_0)^{m_{3}} \end{aligned}$$
(34)

The latter representation (34) can be written in a more compact form by using multi-indices \(m=(m_{1},m_{2},m_{3})\) as in Neidinger [67]

$$\begin{aligned} u(\mathbf {x})=\sum _{|m|=0}^{p}\bar{u}(m)(\mathbf {x}-\mathbf {x_0})^{m} \end{aligned}$$
(35)

where \(|m|=m_{1}+m_{2}+m_{3}\).

In the solving method by Taylor series, one vanishes the Taylor series of the residual. For instance in the case of the equation (24), the Taylor coefficients of the residual of the linearized equation can be written as:

$$\begin{aligned} \overline{\mathcal {L}_{t}v}(m)=-\overline{\varDelta v}(m)+3\overline{{u^{(i)}}^{2}v}(m)=\overline{\mathcal {R}}(m), \qquad 0 \le |m| \le p \end{aligned}$$
(36)

The calculations of derivatives, as in the first term \(\overline{\varDelta v}(m)\) are straightforward:

$$\begin{aligned} \begin{aligned} \overline{\varDelta v}(m_{1},m_{2},m_{3})&=(m_{1}+2)(m_{1}+1) \overline{v}(m_{1}+2,m_{2},m_{3})\\&\quad +(m_{2}+2)(m_{2}+1)\overline{v}(m_{1},m_{2}+2,m_{3}) \\&\quad +(m_{3}+2)(m_{3}+1) \overline{v}(m_{1},m_{2},m_{3}+2) \end{aligned} \end{aligned}$$
(37)

As for the non-linear terms as \({(u^{(i)})}^{2}\), \({(u^{(i)})}^{2} \times v\), \({(u^{(i)})}^{2}\times u^{i}\), etc, they can be easily deduced from the following product formula:

$$\begin{aligned} \begin{aligned} (vw)(m)=&\sum _{j \le m}v(j)w(m-j) \\ =&\sum _{j_{1}=0}^{m_{1}} \sum _{j_{2}=0}^{m_{2}} \sum _{j_{3}=0}^{m_{3}} v(j_{1}, j_{2},j_{3})w(m_{1}-j_{1},m_{2}-j_{2},m_{3}-j_{3}) \end{aligned} \end{aligned}$$
(38)

where \(j \le m\) means “\(j_{1} \le m_{1}\) and \(j_{2} \le m_{2}\) and \(j_{3} \le m_{3}\)”. By combining with Eqs. (37) and (38), the Eq. (36) yields a recurrence formula permitting to compute all the Taylor coefficients \(\bar{u}(m_{1},m_{2},m_{3})\) as a function of the first ones \(\bar{u}(m_{1},m_{2},0)\) and \(\bar{u}(m_{1},m_{2}, 1)\), i.e. of all the bidimensional Taylor coefficients of \((x,y) \rightarrow u(x,y,z_{0})\) and \((x,y) \rightarrow \frac{\partial u}{\partial z}(x,y,z_{0})\). As explained in Sect. 2.1, the polynomial-particular-solution and all the polynomials-Trefftz-functions can be extracted from the recurrence formula (36). Recently the Föppl-Von Karman plate equations have been solved in this manner, see [86].

If the PDE involves more intricate functions \(u \rightarrow f(u)\), the implementation of derivation rules like Eq. (38) can be avoided by using the techniques of algorithmic differentiation, cf [29]. According to the method presented in Griewank et al. [30] and Neidinger [67], one can proceed in two stages. First the computation of multi-directional derivatives is split in a number of derivatives of univariate functions \(t\in R \rightarrow u_{\mathbf {d}}(t)=u(\mathbf {x}_{0}+t\mathbf {d})\), various directions \(\mathbf {d}\) being chosen. For instance the mixed second derivative \(\frac{\partial ^{2} u}{\partial x \partial y}\) can be obtained from derivatives in the three directions \(\mathbf {d}_{1}=(1,0)\), \(\mathbf {d}_{2}=(0,1)\) and \(\mathbf {d}_{3}=(1,1)\) :

$$\begin{aligned} \left[ \frac{d^{2}u_{\mathbf {d}_{3}}}{dt^{2}}(t) \right] _{t=0}=\left[ \frac{d^{2}u_{\mathbf {d}_{1}}}{dt^{2}}(t) \right] _{t=0}+\left[ \frac{d^{2}u_{\mathbf {d}_{2}}}{dt^{2}}(t) \right] _{t=0} +2\left[ \frac{\partial ^{2}u}{\partial x \partial y} \right] _{\mathbf {x}=\mathbf {x}_{0}} \end{aligned}$$
(39)

So we come to calculate the derivatives of univariate functions \(t \rightarrow f(u(t))\), where the function u(t) is given by its Taylor series and f(u) is a combination of elementary functions (as products, exponential, fraction, etc.) whose derivation rules are known, as explained in Table 7. The computation rules of some of these elementary functions is reported in this table in the case of the function \(f(u)=u^{2}/(1+e^{u})\) that combines five elementary operations. These elementary operations can be implemented directly from these formulae, but they can also be implemented once at all in a small library so that the combination of these elementary rules will be done automatically via the method of operator overloading, cf [29]. For instance, in the case of the function of Table 7, the user has only to implement \(u \rightarrow f(u)=u^{2}/(1+e^{u})\). We refer to Yang et al. [99] for more details and various applications.

Table 7 Five successive elementary operations are needed to define the function \(f(u)=u^{2}/(1+e^{u})\)
Full size table

3.4 A Simple Example Solved by Asymptotic Numerical Method

As a first non-linear application, we consider the simple boundary-value-problem (26) in the interval [0, 1] and we solved it by the Asymptotic Numerical Method. With account of the truncated series (27) and (28), this is equivalent to solving the linear ODEs (29) at each order n. Remark that an equation is lacking because the expansion parameter a has not yet been defined. The most used parameter is a sort of linearized arc-length introduced in Cochelin [19] that permits to compute responses including extrema of the function \(a\rightarrow \lambda (a)\):

$$\begin{aligned} a=\langle {u-u_{0},u_{1}}\rangle + (\lambda -\lambda _{0})\lambda _{1} \end{aligned}$$
(40)

where the bilinear form \(\langle {.,.}\rangle\) can be chosen in various ways. Here we defined it from a set of \(n_{b}\) points: \(\langle {u,v}\rangle =\sum _{i=1}^{n_{b}}u(x_{i})v(x_{i})\).

The expansions (27) and (28) are reported both in the boundary value problem (26) and in the arc-length Eq. (40). One deduces a family of equations at any order in the expansion with respect to the path parameter ”a”. At the first order O(a), the system is

$$\begin{aligned} {\left\{ \begin{array}{ll} -\dfrac{d^{2}u_{1}}{dx^{2}}+2u_{0}u_{1} = \lambda _{1} \\ u_{1}(0)=u_{1}(1) = 0 \\ \langle {u_{1},u_{1}}\rangle +\lambda _{1}^{2} = 1 \end{array}\right. } \end{aligned}$$
(41)

where the unknown is \(\{ u_{1},\lambda _{1} \}\) and the starting point of the ANM-step \(u_{0}(x)\) is assumed to be known. One can eliminate \(\lambda _{1}\) by letting \(u_{1}(x)=\lambda _{1}\hat{u}(x)\), and therefore \(\hat{u}(x)\) is the solution of

$$\begin{aligned} {\left\{ \begin{array}{ll} -\dfrac{d^{2}\hat{u}}{dx^{2}}+2u_{0}\hat{u} = 1 \\ \hat{u}(0)=\hat{u}(1) = 0 \end{array}\right. } \end{aligned}$$
(42)

Because of the Eq. (41), the first term of the expansion of the parameter \(\lambda\) is given by

$$\begin{aligned} \lambda _{1}^{2}=\frac{1}{1+\langle {\hat{u},\hat{u}}\rangle } \end{aligned}$$
(43)

the latter Eq. (43) having two solutions corresponding to backward and forward traveling direction. The system at order \(O(a^{n})\) is

$$\begin{aligned} {\left\{ \begin{array}{ll} -\dfrac{d^{2}u_{n}}{dx^{2}}+2u_{0}u_{n}+f_{n}(x) = \lambda _{n} \\ u_{n}(0)=u_{n}(1) = 0 \\ \langle {u_{1},u_{n}}\rangle +\lambda _{{1}}\lambda _{n} = 0 \end{array}\right. } \end{aligned}$$
(44)

where \(f_{n}(x)\) has been defined in Eq. (30) and depends on the solutions \(u_{k}(x), k\le n-1\) at the previous orders. Then the solution of the linear Eq. (44) can be written in the form \(u_{n}(x)=\lambda _{n}\hat{u}(x) +u_{n}^{nl}(x)\), where \(u_{n}^{nl}(x)\) is the solution of the following boundary value problem:

$$\begin{aligned} {\left\{ \begin{array}{ll} -\dfrac{d^{2}u_{n}^{nl}}{dx^{2}}+2u_{0}u_{n}^{nl}=-f_{n}(x) \\ u_{n}^{nl}(0)=u_{n}^{nl}(1) = 0 \end{array}\right. } \end{aligned}$$
(45)

and, from Eq. (44), the Taylor coefficient \(\lambda _{n}\) is given by

$$\begin{aligned} \lambda _{n}=-\dfrac{\langle {u_{n}^{nl},u_{1}}\rangle }{\langle {\hat{u},u_{1}}\rangle + \lambda _{{1}}} \end{aligned}$$
(46)

Next one has to solve the ODEs (42) and (45) and this is done by the Taylor meshless method. For this simple example, a single domain will be sufficient.

At this level, one has built a Taylor series with respect to the path parameter “a” \(a \rightarrow \{u(x,a),\lambda (a)\}\). An important advantage of ANM lies in the domain of validity \([0,a_{max}]\) that can be defined a posteriori and depends strongly on the radius of convergence of the series. A simple way to define this number \(a_{max}\) is to require that the last term of the series is small with respect to the first term, see [19]:

$$\begin{aligned} a_{max}=\left\{ \delta \dfrac{||u_{N}||}{||u_{1}||}\right\} ^{1/(N-1)} \end{aligned}$$
(47)

where \(\delta\) is a small and given accuracy parameter, typically \(\delta =10^{-6}\) or \(\delta =10^{-10}\). For the smallest values of \(\delta\), the number of steps is a bit larger, but the accuracy is excellent and, more importantly, the path-following is very reliable.

The results of the numerical tests for \(\lambda \in [0,60]\) are presented in Fig. 4. Five ANM-steps were necessary to achieve this non-linear computation. Here the step lengths obtained by the criterion (47) are more or less smoothly distributed in the interval [0, 60], but in other cases, for instance cases with bifurcation points as in Tian et al. [86], one finds very short steps close to the bifurcation and much larger steps elsewhere. On the right of Fig. 4, one has checked the accuracy of the solution measured by the residual. The accuracy increases very rapidly with the degree of the polynomial u(x), from a residual of about \(10^{-1}\) for a small degree \(p=5\) up to a very small residual (\(\sim 10^{-8}\)) for a degree \(p=30\), which is in agreement with the p-convergence of TMM observed in Sect. 2 for linear problems. Generally within ANM, the accuracy deteriorates slowly with the number of steps, which appears in Fig. 4 and was often observed with finite elements, see [19]. This slight loss of accuracy is easily controlled by limiting the step sizes via a relevant choice of the accuracy parameter \(\delta\) in the criterion (47).

Fig. 4
figure 4

Solution of the ODE (26) by coupling five ANM-steps and a TMM-discretization. On the left, solution in the center of the interval versus the parameter \(\lambda\). On the right, evolution of the residual according to the degree p

Full size image

3.5 Application to a Large-Scale Non-Linear Problem

In Sect. 2.3, it was established that large-scale problems can be solved by splitting the domain into hundreds subdomains, the solution technique having excellent computational properties: strong reduction of the number of DOFs by comparison with the finite element method, exponential convergence with the degree, moderate computational cost. Is it possible to extend these properties in the non-linear range?

Let us consider the non-linear Poisson Eq. (23) that can be seen as a non-linear version of the Laplace equation discussed in Sect. 2.3. The domain is the cuboid \(\ell _{x}\times \ell _{x }\times 1\), the exact solution is \(u_{ex}(x,y,z)=\sin (\pi x)\sin (\pi y)\frac{\sinh (\sqrt{2} \pi z)}{\sinh (\sqrt{2} \pi )}\) and the right-hand side is \(g(\mathbf {x})=(u_{ex})^{3}\). One tries to recover this function \(u_{ex}\) as the solution of a non-linear Dirichlet problem. The domain is split into cubic elements of size \(1\times 1 \times 1\). This non-linear problem is solved by the Newton method, the inhomogeneous equation obtained at each Newton iteration being solved with the help of a toolbox based on Algorithmic Differentiation, as explained in Sect. 3.3 and in Yang et al. [102].

First let us study the convergence with the degree for a domain \(10\times 10 \times 1\) split in 100 cubic elements. The accuracy of the computation, measured by the maximal error or the maximal residual, is presented in Table 8 for the degrees \(p=5\), 8, 10, 15 and 18. One recovers the same exponential convergence as for the linear case, the error varying from \(14\%\) for a degree \(p=5\) up to \(10^{-8.8}\) for \(p=18\). The same trend is found by looking at the residual. In this case, the number of Newton iterations is small and, of course, it is larger when one wants to obtain a very high accuracy.

Last one looks at the computation time to get an error lower than \(10^{-3}\), which requires a degree \(p=10\). Three domains were considered, where the solution with the largest domain requires about 4.5 millions of DOFs in an equivalent FEM-calculation (see Table 2). The convergence of the non-linear process is obtained after only two iterations. The CPU times necessary to achieve these non-linear calculations is presented in Table 9 and it is compared with an equivalent linear problem (Laplace equation as in Sect. 2.3). Thus the evolution of this non-linear computation time is quite similar to the linear case, with an additional cost of about 20–30% per iteration, which is probably due to the use of algorithmic differentiation.

Thus one can solve very efficiently non-linear Partial Differential Equations by combining linearization techniques as Newton algorithm and Taylor series to compute a Trefftz family of quasi-exact solutions of the linearized system. In the next section, an application to large elastic deformations is presented.

Table 8 The p-convergence of TMM for the non-linear Poisson Eq. (23) in the domain \(10\times 10\times 1\) cut in 100 subdomains. From Yang et al. [102]
Full size table
Table 9 Computation time of TMM for the non-linear Poisson Eq. (23) with a degree \(p=10\)
Full size table

3.6 Application to Large Strain of an Hyperelastic Body

After the two academic models of the Sects. 3.4 and 3.5, one applies the Taylor–Trefftz method to large strain elasticity, also called hyperelasticity, that has a very large field of applications to rubber, polymers or biological materials, see for example [68] and [37]. The simplest hyperelastic model is the so-called Saint Venant–Kirchhoff material, whose unknowns are the deformed position \(\mathbf {X}=[X,Y] \rightarrow \mathbf {x}(\mathbf {X})\), the Lagrange strain \(\mathbf {\gamma }\) and the Piola–Kirchhoff stress tensors \(\mathbf {P}\) and \(\mathbf {S}\). The governing equations are as follows:

$$\begin{aligned} {\left\{ \begin{array}{ll} 2\mathbf {\gamma }= ^{t}\mathbf { \nabla x} .\mathbf { \nabla x}-\mathbf {I} \\ \mathbf {S}=\lambda Tr(\mathbf {\gamma }) \mathbf {I} +2\mu \mathbf {\gamma } \\ \mathbf {P}=\mathbf { \nabla x}.\mathbf {S} \\ div\mathbf {P}+\mathbf {g}(\mathbf {X})=\mathbf {0} \end{array}\right. } \end{aligned}$$
(48)

With this Saint Venant-Kirchhoff material, the stress-strain law \(\mathbf {\gamma } \rightarrow \mathbf {S}\) is linear and isotropic, but there are many other constitutive laws in the literature, see [68] and [37]. The techniques of algorithmic differentiation, as sketched in Sect. 3.3 and in Yang et al. [102], could permit to compute easily the derivatives of these constitutive laws and thereby to solve the system (48) by Taylor series.

A benchmark was built, where the system (48) has an exact solution as follows:

$$\begin{aligned} \mathbf {x_{ex}}= \left( \begin{array}{cc} X+Xe^{-5Y} \\ Y+Ye^{-5Y} \end{array} \right) \end{aligned}$$
(49)

where the exact solution corresponds to the deformed shape pictured in Fig. 5: for instance the point \(\mathbf {X}=(1,0)\) moves to \(\mathbf {x}=(2,0)\) so that the length of the bottom side doubles. Here a Dirichlet boundary value problem is solved.

Thus this benchmark involves large deformations and it is no longer possible to solve it by the pure Newton algorithm that diverges. Hence we switch to the Newton–Raphson method that permits to reach the final state with a small number of steps (six to eight) and two to five iterations per step, the number of iterations depending on the required accuracy as mentioned in Table 8. The required discretization is quite simple, a single Taylor series being sufficient to recover accurately the exact solution. A curve “accuracy versus degree” is plotted in Fig. 5: once again, one converges exponentially with the degree, up to a very high accuracy (\(10^{-6}\)) for a degree \(p=20\), but a very small number of DOFs (\(4p+2=82\)).

This establishes that the Trefftz–Taylor discretization method is able to solve non-linear PDEs of practical interest, in cases where the simplest non-linear algorithms (Newton, Picard) fail. Of course this work has to be extended for 3D domains, alternative constitutive laws and for benchmarks needing much more unknowns.

Fig. 5
figure 5

A 2D hyperelastic benchmark. On the left: the rectangle \([0,1] \times [0, 0,5]\) is deformed, the length of the bottom side being doubled. On the right, the p-convergence curve ”error versus degree”

Full size image

4 Conclusion

Trefftz methods are discretization techniques for PDEs permitting very important reductions of the number of unknowns, but they remain unrecognized because of two difficulties that are discussed in this paper. First they are unable to solve large-scale problems due to a lack of control of matrix ill-conditioning. Second there are no relevant algorithms to solve non-linear engineering problems, especially algorithms based on the consistent tangent matrix.

This paper clearly established that most of the problems due to ill-conditioning may be bypassed by a suitable splitting into subdomains. Indeed in the case of shape functions computed by Taylor series, the ill-conditioning is mainly related to the degree that must be limited at a relatively large level (\(p \le 15\)) or (\(p \le 25\)), but such a limitation was never observed for the number of subdomains that can be chosen very large. That is why we were able to solve problems that need several millions of DOFs in an equivalent finite element calculation. Similar performances had been obtained with wave-based functions and likely comparable results could be obtained with alternative shape functions as the fundamental solutions.

The treatment of non-linear PDEs has also been discussed, mainly within the framework of the Taylor–Trefftz method, where the shape functions are polynomials built by vanishing the Taylor series of the residual: that is why this method is generic and can be applied to all the equations such that these derivatives of the residual can be computed. Three types of applications were presented: a simple differential equation linearized by the Asymptotic Numerical Method, a very large-scale problem in the case of a non-linear Poisson equation and a benchmark with large elastic deformations. There is no reason why the scope of the method could not be extended to other non-linear PDEs, for instance, to fluid flows, to hyperelasticity or to unilateral contact, etc.

In the case of polynomials shape functions, a limitation could come from the difficulty to account for singular solutions, but it seems that there are methods to remove it, see [100].