1 Introduction

Isogeometric Analysis (IgA) [1] can be considered as a natural extension of the Finite Element Method (FEM) to high-order B-spline basis functions. The use of these basis functions enables a highly accurate representation of the geometry. Furthermore, the higher continuity of the basis functions leads to a higher accuracy per degree of freedom compared to FEM [2]. Solving linear systems of equations for discretizations arising in IgA remains, however, a challenging task. The condition number of the system matrices increase exponentially with the approximation order p of the basis functions [3]. Therefore, (standard) iterative methods detoriate for higher values of p which has led to the development of efficient solvers for IgA [4, 5].

Multigrid methods [6, 7] are considered among the most efficient solution techniques for elliptic problems. Within h-multigrid methods, a hierarchy is constructed based on different mesh widths h. At the coarsest level, a correction is obtained by solving the residual equation, which is used to update the fine grid solution. At each level of the multigrid hierarchy, a basic iteration scheme is applied, also known as the smoother. The combination of coarse grid correction and smoothing leads to a highly efficient iterative solver, where the CPU time needed for convergence grows linearly with the number of degrees of freedom. In the context of Isogeometric Analysis, h-multigrid methods have been developed with enhanced smoothers to obtained convergence rates independent of both the mesh width h and approximation order p [8, 9].

As an alternative solution strategy, p-multigrid methods can be adopted. In contrast to h-multigrid methods, a multigrid hierarchy is constructed based on different values of p. As a result, the residual equation is solved at level p = 1, where B-spline basis functions coincide with Lagrangian P 1 basis functions, allowing the use of established solution techniques for standard FEM. Equiped with a smoother that is based on an Incomplete LU factorization [10], the resulting p-multigrid method shows convergence rates independent of both h and p [11]. Compared to h-multigrid methods, the coarse grid correction is obtained at p = 1. As a result, the overall assembly costs are lower for higher values of p due to a significant reduction of the number of non zero entries. For a detailed comparison with h-multigrid methods, the authors refer to [11].

In recent papers by the authors, a p-multigrid hierarchy has been constructed for all levels k, where 1 ≤ k ≤ p. However, the scheme could be adopted in which the residual at level p is directly projected to the coarse level (p = 1). In this paper, we compare both schemes in terms of spectral properties, iteration numbers and CPU times for both a single patch and multipatch geometry. This paper is organized as follows: Sect. 2 describes the considered model problem and IgA discretization. The p-multigrid method, together with the different projection schemes studied in this paper, are described in detail in Sect. 3. Numerical results for the considered benchmark problems, including a spectral analysis, iteration numbers and CPU times are presented in Sect. 4. Finally, conclusions are drawn in Sect. 5.

2 Model Problem and IgA Discretization

As a model problem, we consider the convection-diffusion-reaction (CDR) equation on a connected, Lipschitz domain \(\Omega \subset \mathbb {R}^2\). Defining \(\mathcal {V} = H^1_0(\Omega )\) as the Sobolev space H 1( Ω) with functions that vanish on ∂ Ω, the variational form of the CDR-equation becomes: Find \(u \in \mathcal {V}\) such that

(1)

where

(2)

Here, D denotes the diffusion tensor, v a divergence-free velocity field and R a reaction term. Furthermore, we have f ∈ L 2( Ω) and u = 0 on the boundary ∂ Ω. The physical domain Ω is then parameterized by a geometry map

(3)

The geometry map F describes an invertible mapping connecting the parameter domain \(\hat {\Omega } = (0,1)^2\) with the physical domain Ω. In case Ω cannot be described by a single geometry map, the domain is divided into a collection of non-overlapping subdomains Ω(d), where 1 ≤ d ≤ D. A family of geometry maps F (d) is then defined to parameterize each subdomain separately and we refer to Ω as a multipatch domain consisting of D patches.

In this paper, the tensor product of univariate B-spline functions of order p is used for the spatial discretization. Univariate B-spline basis functions are defined on the one-dimensional parameter domain \(\hat {\Omega } = (0,1)\) and are uniquely determined by a knot vector Ξ = {ξ 1, ξ 2, …, ξ N+p, ξ N+p+1}, consisting of a sequence of non-decreasing knots \(\xi _i \in \hat {\Omega }\) with, in this paper, constant knot span size or mesh width h. Here, N denotes the number of basis functions of order p defined by this knot vector. B-spline basis functions are defined recursively by the Cox de Boor formula [12]. The resulting B-spline basis functions \(\phi ^i_{h,p}\) are non-zero on the interval [ξ i, ξ i+p+1) and possess the partition of unity property. In this paper, an open knot vector is considered, implying that the first and last knots are repeated p + 1 times. As a consequence, the basis functions considered are globally C p−1 continuous and interpolatory only at the two end points; see also Fig. 1.

Fig. 1
figure 1

Univariate linear (left) and quadratic (right) B-spline basis functions based on the knot vectors \(\Xi _1 = \{0,0, \frac {1}{3}, \frac {2}{3},1,1\}\) and \(\Xi _2 = \{0,0,0, \frac {1}{3}, \frac {2}{3},1,1,1\}\), respectively

Full size image

The solution u of Eq. (1) is then approximated by a linear combination of bivariate B-spline basis functions:

$$\displaystyle \begin{aligned} u(\boldsymbol{\xi}) \approx u_{h,p}(\boldsymbol{\xi}) = \sum_{i=1}^{N_{\mathrm{dof}}} c^i \Phi^i_{h,p}(\boldsymbol{\xi}), \end{aligned} $$
(4)

where \(\Phi ^i_{h,p}(\boldsymbol {\xi }) = \phi ^{i_1}_{h,p}(\xi _1)\phi ^{i_2}_{h,p}(\xi _2)\) and N dof denotes the number of bivariate B-spline functions, where N dof = N 2. Defining \(\mathcal {V}_{h,p}\) as the span of all bivariate B-spline basis functions, the Galerkin formulation of (1) becomes: Find \(u_{h,p} \in \mathcal {V}_{h,p}\) such that

(5)

Equation (5) can be written as a linear system resulting from this discretization with B-spline basis functions of approximation order p and mesh width h. For a more detailed description of the spatial discretization in IgA, the authors refer to [1].

3 p-Multigrid Method

To solve Eq. (5) efficiently, a p-multigrid method is adopted. Starting from \(\mathcal {V}_{h,1}\), a sequence of spaces \(\mathcal {V}_{h,1}, \ldots , \mathcal {V}_{h,p}\) is obtained by applying refinement in p. As C p−1 continuous basis functions are considered on all levels of the multigrid hierarchy, these spaces are not nested.

Starting from an initial guess \({\mathbf {u}}_{h,p}^{(0)}\), a single step of the two-grid correction scheme for the p-multigrid method consists of the following steps [13]:

$$\displaystyle \begin{aligned} \begin{array}{rcl} {} {\mathbf{u}}_{h,p}^{(0)} & =&\displaystyle {\mathbf{u}}_{h,p}^{(0)} + \mathcal{S}_{h,p} \left ({\mathbf{f}}_{h,p} - {\mathbf{A}}_{h,p} {\mathbf{u}}_{h,p}^{(0)} \right ), \end{array} \end{aligned} $$
(6)
$$\displaystyle \begin{aligned} \begin{array}{rcl} {\mathbf{r}}_{h,p-1} & =&\displaystyle \mathcal{I}_{p}^{p-1} \left ( {\mathbf{f}}_{h,p} - {\mathbf{A}}_{h,p} {\mathbf{u}}_{h,p}^{(0)} \right ). \end{array} \end{aligned} $$
(7)
$$\displaystyle \begin{aligned} \begin{array}{rcl} {\mathbf{e}}_{h,p-1} & =&\displaystyle \left ({\mathbf{A}}_{h,p-1} \right )^{-1} {\mathbf{r}}_{h,p-1}, {} \end{array} \end{aligned} $$
(8)
$$\displaystyle \begin{aligned} \begin{array}{rcl} {\mathbf{u}}_{h,p}^{(0)} & =&\displaystyle {\mathbf{u}}_{h,p}^{(0)} + \mathcal{I}_{p-1}^p \left ({\mathbf{e}}_{h,p-1} \right ), \end{array} \end{aligned} $$
(9)
$$\displaystyle \begin{aligned} \begin{array}{rcl} {\mathbf{u}}_{h,p}^{(1)} & =&\displaystyle {\mathbf{u}}_{h,p}^{(0)} + \mathcal{S}_{h,p} \left ({\mathbf{f}}_{h,p} - {\mathbf{A}}_{h,p} {\mathbf{u}}_{h,p}^{(0)} \right ), \end{array} \end{aligned} $$
(10)

Here, \(\mathcal {S}_{h,p}\) denotes a single smoothing step applied to the high-order problem, while \(\mathcal {I}_{p}^{p-1}\) and \(\mathcal {I}_{p-1}^{p}\) denote the restriction and prolongation operator, respectively. The coarse grid operator A h,p−1 is obtained by rediscretizing equation (1).

Recursive application of this scheme on Eq. (8) until level p = 1 is reached, results in a V-cycle. As the coarsest problem in p-multigrid can become large for small values of h, a single V-cycle of a standard h-multigrid method (with canonical prolongation, weighted restriction and a single smoothing step) is adopted to approximately solve the coarse grid problem in our p-multigrid scheme.

In this paper, we also consider a direct projection from the high-order level to level p = 1. Both considered multigrid schemes, referred to as an indirect and direct projection scheme, are shown in Fig. 2.

Fig. 2
figure 2

Illustration of both an indirect (left) and direct (right) projection scheme within p-multigrid

Full size image

The operators to project between different p-levels are based on an L 2 projection and have been used extensively in the literature [14,15,16]. The prolongation and restriction operator are defined, respectively, as follows:

(11)

with the mass matrix M p and transfer matrix \({\mathbf {P}}_{p-1}^{p}\) given by:

(12)

The choice of the prolongation and restriction operator leads to a non-symmetric multigrid method. Choosing the prolongation and restriction operator as the transpose of eachother would restore symmetry. Numerical experiments, not presented in this paper, show, however, that this leads to a less robust p-multigrid method. To prevent the explicit solution of a linear system of equations for each projection step, the consistent mass matrix M p in both transfer operators is replaced by its lumped counterpart \({\mathbf {M}}_p^L\) by applying row-sum lumping, i.e. \(({\mathbf {M}}_p^L)_{(i,i)} = \sum _{j=1}^{N_{\mathrm {dof}}} ({\mathbf {M}}_p)_{(i,j)}\). Note that in IgA the mass matrix can easily be lumped due to the non-negativity of the B-spline basis functions. It was shown in [11] that the use of a lumped mass matrix in Eq. (13) hardly influences the convergence behaviour or accuracy of the resulting p-multigrid methods. Note that, alternatively, the mass matrix could be inverted efficiently by exploiting the tensor product structure, see [18].

Since the use of standard smoothers (i.e. Gauss–Seidel) within p-multigrid leads to convergence rates which detoriate for higher values of p [13], we adopt a smoother based on an ILUT factorization. This factorization is determined completely by a tolerance τ and fillfactor m, which are chosen such that the number of nonzeros is approximately the same as for the orignal operator A h,p. We applied this smoother successfully within p-multigrid methods to solve linear systems arising in IgA [11].

4 Numerical Results

To assess the quality of both projection schemes, two benchmarks are considered. For the first benchmark, the model problem (1) is considered with coefficients:

(13)

Here, Ω is chosen to be the unit square, i.e. Ω = [0, 1]2, described by a single patch. The second benchmark is Poisson’s equation (D is the identity matrix) on an L-shaped domain (Ω = {[−1, 1] × [−1, 1]}∖{[0, 1] × [0, 1]}), consisting of 4 patches. The resulting linear systems are then solved with the proposed p-multigrid methods. At level p = 1, coarsening in h is applied until h = 2−3, corresponding to 81 degrees of freedom.

To investigate the interplay between smoothing and the coarse grid correction, the error reduction factors when applying a single smoothing step (only on the finest level) or coarse grid correction (without smoothing) have been determined for both projection schemes. This analysis has been performed before in literature, in the context of h-multigrid methods [17]. Figure 3 (left) denotes the error reduction factors of the generalized eigenvectors v j (j = 1, …N dof) of the operator A h,p for p = 4 and h = 2−5. For both a direct and indirect projection, the smoother and coarse grid correction are complementary to eachother, where the smoother is effective for the high-frequency components and the coarse grid correction for the low frequency components. Remarkably, the coarse grid correction with a direct projection is not only more efficient in terms of less computational work, but also leads to lower reduction factors. Note that, no smoothing is applied here on the coarser levels.

Fig. 3
figure 3

Error reduction in v j (left) and the spectrum of the iteration matrix (right) for the first benchmark obtained with both projection schemes \( \left (p=4, h=2^{-5} \right )\)

Full size image

To further analyze the performance of both projection schemes, the asymptotic convergence rate of the resulting p-multigrid methods has been determined. For any multigrid method, the asymptotic convergence rate is given by the spectral radius ρ of the iteration matrix describing the effect of a single V-cycle. The spectra of the iteration matrices for both projection schemes are shown in Fig. 3 (right). For comparison, a circle with radius 0.025 has been added to the plot. Visually, both spectra are almost identical, which is also confirmed by the obtained spectral radia: ρ 1 = 0.02032 and ρ 2 = 0.02035 for a direct and indirect projection, respectively, implying an equally efficient p-multigrid method for both configurations.

Table 1 shows the number of iterations needed to achieve convergence for both benchmarks, respectively. For all numerical experiments, the initial guess \({\mathbf {u}}^{(0)}_{h,p}\) is chosen randomly, where each entry is sampled from a uniform distribution on the interval [−1, 1]. The p-multigrid iteration is considered converged when the initial residual has decreased with a factor of 108. Note that for both projection schemes and benchmarks, the number of iterations is robust in both the mesh width h and the approximation order p and similar for all configurations. For the first benchmark, with p = 4 and h = 2−5, the same number of iterations is needed, as expected from our spectral analysis. Note that for the multipatch geometry, more iterations are required to achieve convergence. This behaviour for p-multigrid methods has been observed and analyzed in literature by the authors, see [19].

Table 1 Number of iterations needed to achieve convergence for both benchmarks when applying a direct or indirect projection for different values of h and p
Full size table

To compare the computational costs of both approaches, CPU timings have been determined for the first benchmark. A serial implementation in the C++ library G+Smo is considered on an Intel(R) Core(TM) i7-8650 CPU (1.90GHz). Table 2 shows the measured set-up and solver times (in seconds). Although for both projection schemes, the set-up and solver time scales linearly with the number of degrees of freedom, the CPU times obtained with a direct projection scheme are significantly lower. Furthermore, the relative difference increases for higher values of p, as the number of levels in the p-multigrid hierarchy grows when adopting an indirect projection scheme: for p = 5 a reduction of the set-up and solving times of around 50% is achieved.

Table 2 CPU timings (secs) for the first benchmark for different values of h and p
Full size table

5 Conclusions

Recently, the use of p-multigrid methods has become more popular in solving linear systems of equations arising in Isogeometric Analysis. In this paper, various schemes to set up the p-multigrid hierarchy have been compared. In particular, a direct projection to level p = 1 has been compared with constructing a hierarchy for each order 1 ≤ k ≤ p. Numerical results, presented for the CDR-equation on the unit square and Poisson’s equation on an L-shaped multipatch domain, show that in terms of iteration numbers both projection schemes lead to (almost) identical results. This is also confirmed by the performed spectral analysis. However, CPU timings show that a direct projection scheme leads to the most efficient solution strategy, reducing the set-up and solving times up to a factor of 2 for higher values of p.