Finite Element Approximation with Hierarchical B-Splines

Abstract

We review the definition of hierarchical spline spaces and their application to finite element methods. Then we discuss how hierarchical techniques can be implemented using the FEMB program package. Subdivision algorithms play a crucial role and lead to a very simple program structure. A numerical example illustrates the substantial gains in accuracy for the adaptive strategy, in particular for higher degree B-splines.

1 Introduction

B-splines have become standard tools in approximation, computer aided design, and graphics. A systematic application to finite element analysis is fairly recent. Essentially two different strategies have been proposed: weighted [1] and isogeometric [2] methods. The text books [3, 4] give a comprehensive description of the relevant theory for these novel approaches. Which technique is best suited for a particular problem depends to some extent on the representation and topological form of the simulation domain D. Isogeometric methods use parametrizations of subsets of D over rectangles and cuboids which are often provided by NURBS models for CAD/CAM applications. Weighted methods can handle domains well which have a natural implicit description, e.g., domains constructed from elementary sets with Boolean operations. There are also problems for which a combination of both methods might be appropriate [5].

Using B-splines as finite elements bridges the gap between geometry description and numerical simulation. Compared to conventional finite element methods on unstructured grids, spline-based techniques have several advantages: arbitrary choice of degree and smoothness, exact representation of boundary conditions, and simple data structure (one parameter per grid point). As a consequence, B-splines often yield significantly better results than classical finite element schemes when highly accurate solutions are sought.

Tensor product B-splines span the simplest multivariate spline spaces and can utilize univariate algorithms very efficiently. However, unlike in one variable, knot insertion does not provide truly local flexibility; adding knots has a global effect. The natural remedy is hierarchical refinement. Using nested grids with uniform B-splines of different grid width combines well with adaptive approximation methods.

Given the crucial importance of hierarchical techniques for tensor product spline spaces, it is not surprising that such methods have been subject of intensive research. Building upon the classical articles [6, 7], hierarchical splines have been analyzed by a number of authors; the articles [8–11] serve as a few examples which are most relevant to our application. Moreover, several novel concepts, such as T-splines [12] and splines over box-partitions [13], have been introduced.

In this article we consider hierarchical finite element approximation with B-splines, a topic of key importance if B-splines are to compete successfully with classical mesh-based trial functions. For weighted methods, hierarchical B-spline elements were already described in [3], but first implemented in [14] for a special case. For isogeometric elements, adaptive B-spline approximations were recently studied in [15–17] and in the context of T-splines in [18–22]. Our objective is not to improve upon the by now well established theory. Instead, we describe how hierarchical methods can be easily implemented using the FEMB program package [23]. Clearly, incorporating existing software for uniform grids eliminates a great deal of redundant programming effort. As an illustration of our algorithms, we document the substantial gains in accuracy for a typical model problem with a singular solution.

After briefly reviewing some essential components of the FEMB routines in Sect. 2, we define hierarchical splines in Sect. 3. We follow the description in [24, 25] where a convenient notation has been suggested, covering many of the concepts introduced so far. Section 4 discusses grid transfer operations based on B-spline subdivision. Then we explain in Sect. 5 how to combine these tools with our programs for assembling and solving Ritz-Galerkin systems for uniform grids. Finally, Sect. 6 illustrates the error behavior of hierarchical B-spline elements at a reentrant corner.

2 FEMB Program Package

The FEMB programs implement finite element algorithms with uniform B-splines for two elliptic model problems: the scalar second order equation

$$\begin{aligned} -{\text {div}}(p\,{\text {grad}}~u) + qu = f, \end{aligned}$$

(1)

where $p>0$ and $q\ge 0$ are variable coefficients, and the Lamé-Navier system in linear elasticity

$$\begin{aligned} -{\text {div}}\,\sigma (u) = f, \end{aligned}$$

(2)

where $\sigma$ is the stress tensor. For each problem the main steps of a finite element simulation are

• determination of integration parameters,

• assembly of the Ritz-Galerkin system,

• conjugate gradient iteration,

• visualization and computation of the residual.

We briefly discuss these steps for a simple special case of problem (1), a Helmholtz equation with homogeneous Neumann boundary conditions:

$$\begin{aligned} -\varDelta u + u = f \ \text {in} \ D,\quad \partial _\perp u = 0 \ \text {on} \ \partial D, \end{aligned}$$

(3)

where $D\subset \mathbb {R}^d$ is a bounded domain in two or three dimensions ($d=2,3$), and $\partial _\perp$ denotes the normal derivative. This example will be used for illustration purposes throughout the article.

The finite element discretizations of the FEMB programs are based on d-variate uniform tensor product B-splines $b_{k,\xi }$ of a fixed coordinate degree n; see Fig. 1. The index $k=(k_1,\ldots ,k_d)$ refers to the lower left grid position, i.e., $b_{k,\xi }$ has the knots $\xi _{\nu ,k_\nu },\ldots ,\xi _{\nu ,k_\nu +n+1}$ in the $\nu$-th coordinate direction and support

$$\begin{aligned} (\xi _{1,k_1},\ldots ,\xi _{d,k_d})+[0,n+1]^d\,h, \end{aligned}$$

where $h=\xi _{\nu ,\ell +1}-\xi _{\nu ,\ell }$ is the grid width.

Fig. 1.

Uniform tensor product B-spline of coordinate degree $n=3$ (Color figure online)

The domain is described in implicit form,

$$\begin{aligned} D:\ w(x)>0, \end{aligned}$$

with a weight function w supplied by the user (cf. [3] and [26] for some principal construction techniques). This description allows to incorporate the geometry information into a B-spline discretization in very simple form, combining the efficiency of regular grids with the flexibility of free-form boundary representations.

Definition 1

(Uniform Splines). A uniform spline on a domain D is a linear combination

$$\begin{aligned} p^\xi = \sum _{k\sim \xi } u^\xi _k\,b_{k,\xi }, \end{aligned}$$

where $\xi$ is a d-variate uniform knot sequence,

$$\begin{aligned} \xi _\nu :\, \xi _{\nu ,0},\ldots ,\xi _{\nu ,m_\nu +n},\quad \xi _{\nu ,\ell +1} = \xi _{\nu ,\ell }+h, \ 1\le \nu \le d \,, \end{aligned}$$

with parameter hyperrectangle

$$\begin{aligned} D^n_\xi = [\xi _{1,n},\xi _{1,m_1}] \times \cdots \times [\xi _{d,n},\xi _{d,m_d}] \supset D. \end{aligned}$$

The notation $(k_1,\ldots ,k_d)\sim \xi$ indicates that the sum is taken over all B-splines corresponding to $\xi$, i.e., $k_\nu = 0,\ldots ,m_\nu -1$, with the convention that the coefficients $u^\xi _k$ of B-splines with no support in D (irrelevant B-splines) are set to zero.

Fig. 2.

Relevant and irrelevant cubic B-splines for a bounded domain

In Fig. 2, the B-splines $b_{k,\xi }$ corresponding to the knot sequence $\xi$ are marked at the center of their support, using dots for relevant and circles for irrelevant B-splines. Keeping irrelevant B-splines, as described in the above definition, avoids index lists which are necessary for approximations on unstructured grids.

While splines are adequate finite elements for natural boundary conditions, essential or mixed boundary conditions must be incorporated into the finite element subspace. In the FEMB package this is done by using weighted B-splines $wb_{k,\xi }$. Since the hierarchical techniques in this more general case (standard splines correspond to the trivial choice $w=1$) are completely analogous, we have chosen to focus on the model problem (3), which allows us to explain the algorithms in the simplest setting without any modification of the spline space.

The coefficients $u^\xi$ of a finite element approximation $p^\xi$ satisfy the Ritz-Galerkin system

$$\begin{aligned} \sum _{j\sim \xi } a(b_{k,\xi },b_{j,\xi })\,u^\xi _j = f^\xi _k,\quad k\sim \xi , \end{aligned}$$

where

$$\begin{aligned} a(\varphi ,\psi ) = \int _D ( {\text {grad}}~\varphi \, {\text {grad}}~\psi \,+\,\varphi \psi ),\quad f^\xi _k = \int _D f b_{k,\xi } \end{aligned}$$

for Helmholtz equation (3). We abbreviate this system by

$$\begin{aligned} G_\xi u^\xi = f^\xi . \end{aligned}$$

The matrix $G_\xi$ and the vector $f^\xi$ are assembled by adding the contributions to the integrals from each grid cell using predetermined Gauß parameters (cf. [3, 25] for details). Then the coefficients $u^\xi$ are computed with a preconditioned conjugate gradient iteration. An important feature of the final FEMB evaluation and visualization routine is the return of the residual. Unlike for conventional finite element solvers, the spline approximation is continuously differentiable for degree $n>1$ and can be substituted into the partial differential equation. This provides a very reliable error measure.

In the FEMB package it is assumed that $D\subseteq (0,1)^d$ and, accordingly, $\xi _{\nu ,n}=0$, $\xi _{\nu ,m_\nu }=1$, $h=1/(m_\nu -n)$. Changing the relevant program codes slightly, we can relax this requirement. We can provide a Matlab ¹ function which assembles $G_\xi$ and $f^\xi$ for arbitrary uniform knot sequences $\xi$. In particular, the parameter hyperrectangle $D^n_\xi$ need not contain the simulation region D. This subroutine will be the essential tool for implementing a hierarchical finite element solver.

3 Hierarchical Splines

Roughly speaking, a hierarchical spline is a sum of uniform splines $p^\xi$ with different knot sequences $\xi$. Typically, such approximations are constructed with an adaptive process. In regions with large error, B-splines $b_{k,\xi }$ are subdivided by halving the grid width and replaced by the resulting B-splines on the finer grid. These refinement steps are repeated until a prescribed tolerance for the error is met. Figure 3 shows an example for bilinear B-splines ($n=1$).

Fig. 3.

Grid refinement for bilinear hierarchical B-splines

A knot sequence $\xi$ with grid width $h=1/4$ and parameter rectangle $D^1_\xi =[0,1]^2$ (thick grid lines), covering a heart-shaped domain, is refined near the two corners of the domain boundaries. The knot sequence $\eta$ near the reentrant corner is further refined leading to a knot sequence $\zeta$ with grid width $h=1/16$. The bilinear B-splines belonging to the hierarchical basis are marked with circles at the center of their support. As mentioned before, B-splines which can be represented on finer grids do not belong to the hierarchical basis as well as B-splines with no support in the domain D. Nevertheless, such B-splines are included with zero coefficients in linear combinations to facilitate programming.

The adaptive construction, leading to a hierarchical approximation, corresponds to a tree structure of knot sequences. To make this more precise, some notation is helpful. We define the extent of a d-variate knot sequence as the smallest rectangle containing all break points:

$$\begin{aligned}{}[\xi ] = [\xi _{1,0},\xi _{1,m_1+n}] \times \cdots \times [\xi _{d,0},\xi _{d,m_d+n}] \,. \end{aligned}$$

Moreover, we say that $\eta$ is the refinement of $\xi$ if $\eta _\nu$, $\nu =1,\ldots ,d$, is obtained from $\xi _\nu$ by adding midpoints in all knot intervals. Finally, we speak of a local refinement, if the knot sequences $\eta _\nu$ are refinements of subsequences of consecutive knots of $\xi _\nu$.

Definition 2

(Hierarchical Spline). A hierarchical spline $p^\varXi$ is a sum of uniform splines $p^\xi$ corresponding to knot sequences $\xi$ which are nodes of a tree $\varXi$:

$$\begin{aligned} p^\varXi = \sum _{\xi \sim \varXi } p^\xi ,\quad p^\xi = \sum _{k\sim \xi } u^\xi _k\,b_{k,\xi } \,. \end{aligned}$$

It is required that the children of each node $\xi$ are local refinements of $\xi$ with disjoint extents. Moreover, coefficients $u^\xi _k$ of irrelevant B-splines $b_{k,\xi }$ or B-splines which can be represented on refined grids are set to zero.

In Matlab, the relevant data for a hierarchical spline $p^\varXi$ can be stored in a cell vector HS of structures, corresponding to the nodes $\xi$ of the tree $\varXi$, with fields

$$\begin{aligned} .\mathtt {parent},\ .\mathtt {children},\ .\mathtt {h},\ .\mathtt {knots},\ .\mathtt {u} \,. \end{aligned}$$

The first two fields refer to the cell vector indices of the parent and children nodes $\xi$, .h is the grid width, the field .knots specifies the knot sequence using the lower left and upper right coordinates of $[\xi ]$ divided by the grid width,

$$\begin{aligned}{}[\xi _{1,0} \ \xi _{1,m_1+n}\,; \ \ldots \ ;\, \xi _{d,0} \ \xi _{d,m_d+n}]/h, \end{aligned}$$

and .u is the d-dimensional array of coefficients with size

$$\begin{aligned} m_1\times \cdots \times m_d \,. \end{aligned}$$

This natural storage model is illustrated for the example in Fig. 3 above:

We note the forced zeros in the coefficient arrays due to irrelevant or refined B-splines. For example, the B-spline $b_{(4,0),\xi }$ with center at $x=(1,0)$ has support outside of D and hence HS {1} .u(5,1) = 0. The B-spline $b_{(4,0),\eta }$ with center at $x=(3/8,7/8)$ is a linear combination of the B-splines $b_{k,\zeta }$, $0\le k_1,k_2\le 2$. Consequently, HS{2}.u(5,1) = 0. Note that Matlab indexing starts at 1 while 0 is more convenient for the theory. Moreover, columns in the matrices HS{i}.u correspond to horizontal directions in the figure (analogously as for the commands ndgrid and meshgrid in Matlab).

In addition to the assumptions on the tree $\varXi$ made in Definition 2, the following property, already proposed in [14], simplifies programming considerably and also has theoretical relevance for stability and the construction of quasi-interpolants.

Definition 3

(Nested Tree). A tree $\varXi$ is nested if the grid widths of any two B-splines in the hierarchical basis, which are both nonzero at some common point x, are equal or differ by a factor two.

Requiring a tree to be nested is not a severe restriction. The knot sequences of a tree generated via an adaptive procedure can always be refined to meet the additional requirement. We illustrate this for the example in Fig. 3. Clearly, the tree formed by the knot sequences $\xi$, $\eta$, $\tilde{\eta }$, $\zeta$ is not nested since the B-splines $b_{(1,3),\xi }$ (grid width 1 / 4, centered at (1 / 4, 3 / 4)) and $b_{(0,0),\zeta }$ (grid width 1 / 16, centered at (5 / 16, 13 / 16)) are both nonzero for all x in $(2/8,3/8)\times (6/8,7/8)$. To conform to the requirement of Definition 3, we add a layer of B-splines with grid width 1 / 8 to separate the coarse- and fine-grid B-splines. We replace the knot sequence $\eta$ by $\eta ^*$ with knots

$$\begin{aligned} \eta ^*_{1,0}=-2/8,\ldots ,6/8=\eta ^*_{1,8},\quad \eta ^*_{2,0}=4/8,\ldots ,10/8=\eta ^*_{2,6} \,. \end{aligned}$$

All B-splines $b_{k,\xi }$ which overlap B-splines $b_{k,\zeta }$ from the finest grid are now replaced by linear combinations of B-splines from $\eta ^*$ with grid width 1 / 8. This leads to the following changes in the Matlab structure listed above.

The other structure variables remain unchanged.

4 Grid Transfer Operations

For approximation with hierarchical splines grid transfer operations are essential. Subdivision strategies, systematically introduced by Boehm [27] and Cohen, Lyche, and Riesenfeld [28], provide the canonical mechanism.

Theorem 1

(Subdivision of B-Splines). A d-variate B-spline $b_{k,\xi }$ with grid width h can be represented as linear combination of B-splines $b_{k,\eta }$ with grid width h / 2 ($\xi _k = \eta _{2k}$):

$$\begin{aligned} b_{k,\xi } = \sum _{\nu _1=0}^{n+1}\cdots \sum _{\nu _d=0}^{n+1} s_\nu \,b_{2k+\nu ,\eta },\quad s_\nu = 2^{-nd}\,\left( {\begin{array}{c}n+1\\ \nu _1\end{array}}\right) \cdots \left( {\begin{array}{c}n+1\\ \nu _d\end{array}}\right) \,; \end{aligned}$$

(4)

see Fig. 4. When manipulating sums it is often convenient to extend the range of summation to all integer vectors $\nu =(\nu _1,\ldots ,\nu _d)$. This is possible in view of the convention that the binomial coefficient $\left( {\begin{array}{c}n+1\\ \alpha \end{array}}\right)$ vanishes if $\alpha \notin \{0,\ldots ,n+1\}$.

Fig. 4.

Subdivision coefficients of a bilinear and biquadratic B-spline

By linearity, the subdivision rule extends to splines as well. It can be used for grid transfer in both directions. We consider each case in turn.

Corollary 1

(Coarse-to-Fine Extension). If the knot sequence $\eta$ is the refinement of $\xi$ and $\sum _{k\sim \xi } u^\xi _k\,b_{k,\xi } = \sum _{j\sim \eta } v^\eta _j\,b_{j,\eta }$, then the transformation of the coefficient vectors has the form

$$\begin{aligned} v^\eta = S^\eta _\xi \,u^\xi :\quad v^\eta _j = \sum _k s_{j-2k}\,u_k^\xi \,. \end{aligned}$$

In pseudo Matlab code, this extension operation can be implemented as

where K denotes the relevant range of indices for the B-splines corresponding to the knot sequence $\xi$.

The assertions follow from the definitions. Substituting the subdivision formula (4) for B-splines and changing the summation index yields

$$\begin{aligned} \sum _k u^\xi _k\,b_{k,\xi } = \sum _\nu \sum _k s_\nu \,u^\xi _k\,b_{2k+\nu ,\eta } = \sum _j \sum _k s_{j-2k}\,u^\xi _k\,b_{j,\eta } \,. \end{aligned}$$

The middle expression corresponds to the Matlab pseudo code and the right expression to the extension operator $S^\eta _\xi$.

We now consider the reverse operation.

Corollary 2

(Fine-to-Coarse Restriction). Let the knot sequence $\eta$ be the refinement of $\xi$. If, for a bilinear form $a(\cdot ,\cdot )$ and a function $\varphi$, $v^\eta _j = a(b_{j,\eta },\varphi )$, $j\sim \eta$, then $u^\xi _k = a(b_{k,\xi },\varphi )$, $k\sim \xi$, can be computed with the transformation

$$\begin{aligned} u^\xi = S^\xi _\eta v^\eta :\quad u^\xi _k = \sum _j s_{j-2k}\,v^\eta _{j} \,. \end{aligned}$$

In pseudo Matlab code, this restriction operation can be implemented as

where K denotes the relevant range of indices for the B-splines corresponding to the knot sequence $\xi$.

Again, the assertions follow by substituting the subdivision formula (4) for B-splines and changing the summation index:

$$\begin{aligned} u^\xi _k = a(b_{k,\xi },\varphi ) = \sum _\nu s_\nu \,a(b_{2k+\nu ,\eta },\varphi ) = \sum _\nu s_\nu \,v^\eta _{2k+\nu } = \sum _j s_{j-2k}\,v^\eta _j \,, \end{aligned}$$

with the second to last expression corresponding to the Matlab code.

The grid transfer operations simplify the assembly and solution of the Ritz-Galerkin system considerably. As will be described in the next section, it suffices to compute integrals involving only B-splines on the same grid level.

5 Solving Hierarchical Systems

We recall from Sect. 3 that a hierarchical spline has the form

$$\begin{aligned} u^\varXi = \sum _{\xi \sim \varXi }\sum _{k\sim \xi } u^\xi _k\,b_{k,\xi } \,. \end{aligned}$$

Accordingly, the Ritz-Galerkin matrix G has block structure with entries

$$\begin{aligned} G^\xi _\eta :\quad a(b_{k,\xi },b_{j,\eta }),\,k\sim \xi ,\,j\sim \eta \,. \end{aligned}$$

We could proceed in a standard fashion, i.e., assemble G using an appropriate storage scheme, and solve the Ritz-Galerkin system

$$\begin{aligned} GU = F \quad \Leftrightarrow \quad \sum _{\eta \sim \varXi } G^\xi _\eta \,u^\eta = f^\xi ,\quad \xi \sim \varXi , \end{aligned}$$

by some iterative method. However, since the standard solvers just require the implementation of multiplication by the system matrix, we can avoid the explicit assembly of G and use the routines of the FEMB package for the uniform case in an elegant fashion. To this end we examine the matrix/vector multiplication

$$\begin{aligned} U\mapsto F = GU,\quad f^\xi = \sum _{\eta \sim \varXi } G^\xi _\eta \,u^\eta \,, \end{aligned}$$

in more detail.

The equation, relating the blocks of the hierarchical vectors U and F, simplifies if we require that $\varXi$ is nested, i.e., if for B-splines in the hierarchical basis only supports of adjacent levels overlap. Since we are also assuming that the extents of knot sequences with the same grid width are disjoint, the matrices $G^\xi _\eta$ are zero unless $\xi =\eta$, or $\eta$ is the parent or a child of $\xi$. Hence, for implementing the multiplication by $G_\eta ^\xi$, i.e., for computing

$$\begin{aligned} v^\xi = G^\xi _\eta u^\eta \quad \Leftrightarrow \quad v^\xi _k = \sum _{j\sim \eta } a(b_{k,\xi },b_{j,\eta })\,u^\eta _j \,, \end{aligned}$$

(5)

there are three cases to consider.

(i) $\eta =\xi$:    Since $G_\xi = G^\xi _\xi$ is a Ritz-Galerkin matrix of B-splines of the same grid level, the FEMB routines are applicable with minor modifications ($\xi$ corresponds in general to a grid covering only a subset of the simulation domain D).

(ii) $\eta$ is the parent of $\xi$:    In Eq. (5) we refine the coarse grid B-splines $b_{j,\eta }$ and obtain by Corollary 1

$$\begin{aligned} \sum _{j\sim \eta } u^\eta _j\,b_{j,\eta } = \sum _{\ell \sim \zeta } w^\zeta _\ell \,b_{\ell ,\zeta },\quad w^\zeta = S^\zeta _\eta \,u^\eta \,, \end{aligned}$$

with the knot sequence $\zeta$ being the refinement of $\eta$. This yields the desired conversion to multiplication with a Ritz-Galerkin matrix for B-splines on the same grid level:

$$\begin{aligned} v^\xi _k = \sum _{\ell \sim \zeta } a(b_{k,\xi },b_{\ell ,\zeta })\,w^\zeta _\ell \quad \Leftrightarrow \quad v_k^\xi = \left( G_\zeta \,w^\zeta \right) _{\tilde{k}} \,, \end{aligned}$$

where $\tilde{k}$ is the index of the B-spline $b_{k,\xi }$ with respect to $\zeta$ ($b_{k,\xi }=b_{\tilde{k},\zeta }$). While $\xi _\nu$ are subsequences of $\zeta _\nu$, the indices do, in general, not match since the labeling starts from 0 for all knot sequences (cf. Fig. 3).

A final adjustment is necessary. Multiplying $w^\zeta$ by $G_\zeta$ results in a larger vector than needed. Since $\xi$ is a local refinement of $\eta$, $[\xi ]\subseteq [\eta ]=[\zeta ]$. As a consequence, some B-splines of the knot sequence $\zeta$ are, in general, irrelevant for $\xi$. Hence, we have to extract the entries relevant for $\xi$:

$$\begin{aligned} v^\zeta _k,\,k\sim \zeta \quad \mapsto \quad v^\xi _k,\,k\sim \xi \,. \end{aligned}$$

We denote this truncation operation, which also incorporates the index adjustment, by $v^\xi = I^\xi _\zeta \,v^\zeta$. Summarizing, we obtain the following procedure.

Theorem 2

(Coarse-to-Fine Multiplication). If the knot sequence $\eta$ is the parent of $\xi$, then

$$\begin{aligned} v^\xi = G^\xi _\eta \,u^\eta \quad \Leftrightarrow \quad v^\xi = I^\xi _\zeta \,G_\zeta \,S^\zeta _\eta \,u^\eta \end{aligned}$$

with $\zeta$ the refinement of $\eta$.

(iii) $\eta$ is a child of $\xi$: As in the previous case, we rewrite Eq. (5) in terms of the Ritz-Galerkin matrix $G_\zeta$, where $\zeta$ is the refinement of the coarse knot sequence $\xi$. To this end let $u^\zeta = I^\zeta _\eta \,u^\eta$ denote the extension of the coefficient vector $u^\eta$ with coefficients of the B-splines $b_{j,\zeta }$, $j\sim \zeta$, which do not correspond to the smaller knot sequence $\eta$ ($[\eta ]\subseteq [\xi ]=[\zeta ]$) set to zero, and define

$$\begin{aligned} \varphi = \sum _{j\sim \eta } u^\eta _j\,b_{j,\eta } = \sum _{j\sim \zeta } u^\zeta _j\,b_{j,\zeta } \,. \end{aligned}$$

Then, according to Corollary 2, $v^\xi _k = a(b_{k,\xi },\varphi )$ can be computed from $w^\zeta _\ell = a(b_{\ell ,\zeta },\varphi )$ with the restriction operator:

$$\begin{aligned} v^\xi = S^\xi _\zeta \,w^\zeta ,\quad w^\zeta = G_\zeta u^\zeta \,. \end{aligned}$$

We summarize this procedure as follows.

Theorem 3

(Fine-to-Coarse Multiplication). If the knot sequence $\eta$ is a child of $\xi$, then

$$\begin{aligned} v^\xi = G^\xi _\eta \,u^\eta \quad \Leftrightarrow \quad v^\xi = S^\xi _\zeta \,G_\zeta \,I^\zeta _\eta \,u^\eta \end{aligned}$$

with $\zeta$ the refinement of $\xi$.

Summarizing, we have reduced the multiplication with the hierarchical matrix G to multiplications with Ritz-Galerkin matrices $G_\xi$, involving only B-splines with the same grid width. These matrices can be precomputed using the FEMB package before an iterative solver is started. If we employ, e.g., the conjugate gradient method, we have to provide in addition routines for adding hierarchical vectors, multiplication with scalars, and forming of scalar products. This is straightforward.

As a final comment on the programming details, we note that the hierarchical matrix G contains zero rows and columns since we keep irrelevant B-splines for ease of programming. This does not cause any problem though, since the corresponding sections in the coefficient vectors are set to zero. In effect, the iteration “sees” only the invertible part of G.

6 Accuracy of Adaptive Approximations

As a sample problem for testing the proposed method, we chose Helmholtz equation (3) with right–hand side $f(x) = \sin (\pi x_1x_2)$ on the B–shaped domain shown in Fig. 5. D is the intersection of the square $(0,1)^2$ with the union of the two ellipses

$$\begin{aligned} E_1: \ x_1^2\, +\, \frac{(x_2-a)^2}{a^2}\, <\, 1 \qquad {\text{ and }} \qquad E_2: \ \frac{9x_1^2}{4}\, +\, \frac{(x_2-b)^2}{(1-b)^2}\, <\, 1, \end{aligned}$$

where $a=\frac{11}{10}\,(2-\sqrt{3}\,)$ and $b=\frac{1}{5}\,(1+\sqrt{7}\,)$. The boundary of D has a reentrant corner at $x^\star = (0.5, 0.55)$ with an interior angle of width $\alpha \approx 1.8089\,\pi$, causing the solution u of (3) to form a singularity at this point. More precisely, u is of asymptotic order $O(r^{\pi /\alpha }) \approx O(r^{0.5528})$ in the region near the corner, where r denotes the distance to $x^\star$, cf. [29]. No other singularities occur at the corners (0, 0) and (0, 1) since, due to symmetry, u can be regarded as restriction to D of the solution on the entire domain $E_1\,\cup \,E_2$, which has a smooth boundary near these two points.

The shading in Fig. 5 illustrates the growth of $|{\text {grad}}\,u|$ in the vicinity of the reentrant corner, indicating that the gradient of u  —  yet still being square integrable on D  —  becomes infinite when approaching $x^\star$.

Fig. 5.

Singular solution with hierarchical grid (Color figure online)

Corner singularities strongly affect the performance of both conventional finite element schemes and methods based on uniform tensor product B–splines, as they require the solution to belong to some higher order Sobolev space in order to yield optimal rates of convergence. If, as in our example, u has no square integrable second derivatives, the uniform bases cannot release their full approximation power, which results in a slow convergence of numerical solutions. Not even the use of higher spline degrees pays off, as can be seen from Fig. 6 where, regardless of the degree, all uniform spline approximations exhibit about the same poor convergence rate of $O(h^{3/2})$, or $O(N^{-3/4})$ if expressed in terms of the dimension N of the respective spline spaces.

For comparison, we computed approximate solutions to (3) in sequences of hierarchical spline spaces, defined by nested trees with different numbers of levels. Local grid refinement was employed (manually) in regions where the pointwise error of a corresponding uniform approximation was large with respect to the average error. A typical choice of the grid structure for a quadratic spline space is depicted in Fig. 5.

Fig. 6.

Relative $L^2$ error for uniform (dashed) and hierarchical approximations (solid) as a function of the dimension for degrees $n=1$

(Color figure online)

The significant improvement in efficiency achieved through hierarchical refinement near the critical corner is apparent from Fig. 6. The number of parameters necessary to attain similar accuracy is, on an average, smaller by a factor of more than 20, compared with approximations on uniform grids. For example, quadratic elements meet a tolerance of $7.8\cdot 10^{-5}$ with 1593 B–splines on five hierarchical levels, whereas the error for a finite element space spanned by 18900 quadratic B–splines on a uniform grid of $160\times 160$ cells is still greater than $1.5\cdot 10^{-4}$.

7 Conclusion

We have described the implementation of hierarchical finite element methods with B-splines using the FEMB package. B-spline subdivision plays a crucial role and leads to a very simple program structure. The numerical results for Helmholtz’s equation as a model problem document the substantial gains in accuracy due to adaptive refinement.

For classical mesh-based finite element methods, adaptive techniques have been studied intensively. Hence, for the relatively novel application to B-splines, a number of topics remain to be investigated. An interesting question is, whether the possibility of computing pointwise residuals of the partial differential equations (B-splines are sufficiently smooth) can be exploited. Moreover, deriving optimal error estimates for typical singularities is a major project. These are just two examples of a longer list of open problems to which we hope to contribute in the future.