ON THE USE OF COMPRESSED POLYHEDRAL QUADRATURE

(1)

FORMULAS IN EMBEDDED INTERFACE METHODS

2

Y. SUDHAKAR^{† §}, ALVISE SOMMARIVA^‡, MARCO VIANELLO^‡, AND 3

WOLFGANG A. WALL^† 4

Abstract. The main idea of this paper is to apply a recent quadrature compression technique 5

to algebraic quadrature formulas on complex polyhedra. The quadrature compression substantially 6

reduces the number of integration points but preserves the accuracy of integration. The compression 7

is easy to achieve since it is entirely based on the fundamental methods of numerical linear algebra.

8

The resulting compressed formulas are applied in an embedded interface method to integrate the 9

weak form of the Navier-Stokes equations. Simulations of flow past stationary and moving interface 10

problems demonstrate that the compressed quadratures preserve accuracy, rate of convergence, and 11

improve the efficiency of performing the weak form integration.

12

AMS subject classifications. 65D32, 65M60.

13

Key words. quadrature compression, algebraic quadrature, complex polyhedra, embedded 14

interface methods.

15

1. Introduction. Accurate numerical integration over arbitrary complex poly-

16

hedra is an essential component in various classes of finite element methods (FEM):

17

embedded interface methods (EIM), polyhedral FEM, boundary element methods and

18

virtual element methods, to name a few. In EIMs, the interface which is embedded

19

within the non-body confirming finite element mesh cuts few elements of the back-

20

ground mesh and as a result splits these elements into two or more non-overlapping

21

polyhedra. The elements that are cut by the interface are called cut-elements, and the

22

polyhedra produced by the interface cut are referred to as volume-cells. These cut-

23

elements offer significant difficulties because in order to extract the stiffness matrix

24

for these elements, the weak form has to be integrated over the arbitrary polyhedral

25

shaped volume-cells. Moreover in many problem classes, one faces strict requirements

26

for such integrations.

27

Accuracy of the weak form integration over the volume-cells significantly influ-

28

ences the overall solution accuracy in EIMs. In certain simulations, a small error intro-

29

duced in the integration can even hinder the overall convergence behavior. The inap-

30

plicability of the standard Gauss quadrature rules for a general polyhedron, together

31

with the importance of accurate weak form integration have motivated researchers to

32

develop various methods for numerical integration over polyhedra [6,20–23,33, 34,39].

33

One of the major drawbacks of the methods developed to perform integration over

34

polyhedra is the large number of integration points they yield. Often we get thousands

35

of integration points to achieve an accurate integral value [33, 34], and this leads to

36

drastic computational overheads. Numerical integration on the cut-elements is a key

37

factor that tremendously slows down the execution speed of EIMs. As an attempt

38

to improve the computational efficiency of such methods, in this paper, we apply

39

∗Submitted to the Editors July 16, 2016

†Institute for Computational Mechanics, Technical University of Munich, Germany (wall@lnm.mw.tum.de,www.lnm.mw.tum.de).

‡Department of Pure and Applied Mathematics, University of Padova, Italy (alvise@math.unipd.it,marcov@math.unipd.it). Work partially supported by the “ex-60%” funds and by the biennial project CPDA143275 of the University of Padova, and by the GNCS-INdAM.

§Current address: Linn´e Flow Centre, Department of Mechanics, KTH Royal Institute of Tech- nology, Sweden (sudhakar.yogaraj@mech.kth.se)

1

This manuscript is for review purposes only.

(2)

2

Y. SUDHAKAR, A. SOMMARIVA, M. VIANELLO AND W. A. WALL

the recently developed multivariate quadrature compression techniques [3, 31, 32] to

40

reduce the number of integration points required for the polyhedral quadrature rules.

41

Quadrature compression techniques operate on an existing quadrature rule by

42

selecting a subset of nodes, and modify the corresponding weights in such a way

43

that the accuracy of the original quadrature rule is preserved. In the compressed

44

quadrature rule, the number of integration points is always equal to the dimension of

45

the considered polynomial space. For example, in 3D, the cardinality of fifth-order

46

basis functions is 56. This means that the compressed quadrature rule will have 56

47

integration points, irrespective of the shape of the polyhedra, to integrate any fifth-

48

order polynomial.

49

Multivariate quadrature compression is a fairly new area of research in applied

50

mathematics. The existing studies, performed until now, report quadrature compres-

51

sion only on 2D geometries [3, 31,32]. In this work, for the first time, we carry out the

52

quadrature compression over arbitrary complex polyhedra in 3D, and use the resulting

53

quadrature schemes to integrate the weak form of the EIMs.

54

This paper is organized as follows. Theory of multivariate quadrature compression

55

and a practical method to perform compression together with the results of applying

56

the method to arbitrary polyhedra are presented in §2. In section 3, the application of

57

compressed quadrature rules to perform weak form integration of EIMs is presented,

58

with emphasis on accuracy, rate of convergence and improved computational efficiency.

59

2. Compression of quadrature formulas. Multivariate algebraic quadrature

60

formulas on complicated geometries have often a huge number of nodes, much larger

61

than the dimension of the exactness polynomial space [33, 34]. The possibility of

62

compressing a multivariate quadrature formula by node selection and re-weighting

63

rests in principle on the well-known Tchakaloff’s theorem, a deep result of quadrature

64

theory, that ensures existence of positive algebraic formulas of low cardinality. Such a

65

theorem was originally stated and proved by Tchakaloff [36] for compactly supported

66

absolutely continuous measures with respect to the Lebesgue measure, and afterwards

67

generalized to arbitrary measures with finite moments. We report a version of the

68

theorem taken from [24, Theorem 1], sufficiently general for our purposes, since it

69

includes discrete measures.

70

Theorem 1. Let µ be a positive measure with compact support Ω in R

^d

and let

71

n be a fixed positive integer. Then there are m ≤ N = dim(P

^dn

) points {Q

^s

} in Ω and

72

positive real numbers λ = {λ

^s

} such that

73

(1)

Z

R^d

p(P ) dµ =

m

X

s=1

λ

s

p(Q

s

)

74

for all p ∈ P

^dn

.

75

Now, if µ is a discrete measure with finite support Ω = X = {P

ⁱ

} and positive

76

masses w = {w

ⁱ

}, 1 ≤ i ≤ M, namely

77

(2)

Z

R^d

f (P ) dµ =

M

X

i=1

w

i

f (P

i

) ,

78

in particular if µ is an algebraic quadrature formula with positive weights (that we

79

shall term in the sequel the “base quadrature rule”)

80

(3) Q

^BQ

= (X, w) , card(X) = M > N = dim(P

^dn

) ,

81

(3)

for a continuous measure σ(P ) dP on a compact set K ⊂ R

^d

, σ ∈ L

¹+

(K), then by

82

Tchakaloff’s theorem

83

(4)

Z

K

p(P ) σ(P ) dP =

M

X

i=1

w

i

p(P

i

) =

m

X

s=1

λ

s

p(P

is

) , ∀p ∈ P

^dn

,

84

with m ≤ N, that is the base quadrature rule can be compressed preserving the degree

85

of polynomial exactness.

86

On the other hand, Tchakaloff’s theorem is a qualitative result, that does not

87

provide a constructive approach for the node subset selection and re-weighting. Nev-

88

ertheless, to this purpose we can use the following approach based on discrete mo-

89

ments. Given a polynomial basis τ (P ) = (τ

1

(P ), . . . , τ

N

(P )) of P

^dn

, we can consider

90

the underdetermined system

91

(5) T u = ν , T = (t

sk

) = (τ

s

(P

k

)) ∈ R

^N^×M

92

u = {u

^k

} ∈ R

^M

, ν = {ν

^s

} = T w ∈ R

^N

, w = (w

1

, . . . , w

M

)

^t

,

where ν is the vector of discrete moments of the basis, and seek a sparse solution, i.e.

93

a solution vector with (at least) M − N null components. In order to have a not too

94

ill-conditioned matrix T (an unavoidable fact with the standard monomial basis), we

95

can start from the total-degree product Chebyshev basis (with graded lexicographic

96

order, cf. [10]) of the minimal Cartesian rectangle containing the nodes, and possibly

97

perform a discrete orthonormalization of the basis by the QR algorithm applied to

98

the Vandermonde-like matrix T

^t

; see [32] for an implementation.

99

Looking for positive weights, sparsity can be achieved by reformulating equa-

100

tion (5) as the “NonNegative Least Squares” (NNLS) problem min

u≥0

kT u − νk

²

,

101

and solving it by some suitable quadratic programming method, such as the active

102

set method by Lawson and Henson [16]. The nonzero components of the NNLS solu-

103

tion, say u

^∗

, give a subset of indexes (i

1

, . . . , i

m

), that allow to compress the formula

104

by selecting a subset of nodes {P

ⁱs

}, with positive weights {w

^s

} = {u

^∗is

}. See [ 14]

105

for the univariate case, and [32] for the multivariate extension where the effect of

106

the moment reconstruction error ε = kT u

^∗

− νk

²

on the accuracy of the compressed

107

formula has also been studied.

108

On large problems, however, the NNLS approach has a high computational cost,

109

and as an alternative we can seek a classical solution to the underdetermined system,

110

with M − N zero components. A suitable way to obtain a classical solution consists

111

in selecting a subset of N colums of T , trying to maximize the (absolute value of) the

112

determinant of the resulting square submatrix. It is known that such a maximization

113

is an NP-hard problem [7], which requires heuristic algorithms. One is computing the

114

well-known QR factorization with column pivoting of T , cf. [4], which corresponds to a

115

greedy maximization of submatrix “volumes” (a concept that can be easily understood

116

thinking to the extraction of three vectors from a bunch of 3-dimensional vectors to

117

maximize the volume of the resulting parallelepiped). The computed subset of indexes

118

(i

1

, . . . , i

N

) selects from the original nodes the so-called “approximate Fekete points”;

119

cf. [31].

120

The approach adopted in this paper works instead on a greedy maximization

121

of the subdeterminants of the Vandermonde-like matrix T

^t

by its LU factorization

122

with row pivoting, obtained by the resulting subset of indexes (i

1

, . . . , i

N

) the so-

123

called “discrete Leja points” extracted from the original set of nodes; cf. [3] for a

124

full description of the algorithm and of the properties of discrete Leja points (for

125

This manuscript is for review purposes only.

(4)

4 example, the fact that they form a sequence). For the theoretical connections of

126

these Fekete-like and Leja-like extremal sets to multivariate polynomial interpolation

127

theory, we refer the reader to [3]. From the computational point of view, again at high

128

degree n a preliminary orthonormalization of the basis is needed, that works until the

129

conditioning of the Vandermonde-like matrix is not much higher than the reciprocal

130

of machine precision, cf. [3, 31].

131

Once the discrete Leja points L = {P

ⁱ1

, . . . , P

i_N

} have been extracted, the quadra-

132

ture weights λ = (λ

1

, . . . , λ

N

) are computed essentially by solving the square system

133

(6) T

^∗

λ = ν , T

^∗

= (t

^∗_sj

) = (t

sij

) = τ

s

(P

ij

) ∈ R

^N^×N

,

134

where T

^∗

is the square submatrix of T corresponding to the column indices

135

(i

1

, . . . , i

N

), which is already obtained by the LU factorization. Solution of the above

136

equation leads to a compressed quadrature formula

137

(7) Q

^CQ

= ( L, λ) , card(L) = N .

138

In this case (and also with the approximate Fekete points) the weights are not all

139

positive, in general. However, it turns out that with good distributions of starting

140

nodes, like those typical of quadrature on polygons or on polyhedra that are the object

141

of the present paper, the negative weights are few and of relatively small size, so that

142

the quadrature sensitivity parameter

143

(8) ρ =

P

N s=1

|λ

^s

|

P

N s=1

λ

s

144

remains close to 1 or grows very slowly with n, ensuring accuracy and stability to the

145

quadrature process; cf. [11, 32].

146

In summary, the method of constructing the compressed quadrature rule Q

^CQ

:=

147

( L, λ) involves 4 steps that are presented in algorithm 1. The first step is to construct

148

the base quadrature Q

^BQ

:= (X, w), with M number of points, over the considered

149

polyhedron. The present work uses the direct divergence method [33] to construct

150

Q

^BQ

but any other available technique can be used for this purpose. It should be

151

noted that M can be on the order of thousands [33, 34] for a complex polyhedron.

152

The next step is to construct the Vandermonde-like matrix T (of dimension N × M)

153

on X using the considered total-degree product Chebyshev basis functions τ (P ) (see

154

equation (5)). The cardinality of the considered base functions is N , and usually

155

N < M . Then, we extract L ⊂ X by performing LU decomposition with row-

156

pivoting of T

^t

; the set L contains N number of points. As a next step, we form

157

the Vandermonde-like matrix T

^∗

(of dimension N × N) on L using τ (P ). Finally,

158

we compute the modified weights λ on L by solving T

^∗

λ = ν (see equation (6) for

159

more information on ν). Thus the compressed quadrature rule Q

^CQ

:= ( L, λ) is

160

constructed.

161

2.1. Polyhedral quadrature formulas. The quadrature compression algo-

162

rithm, if it is to be applied in an EIM framework, must be highly robust to handle

163

complex polyhedra. In order to test the robustness, we perform quadrature compres-

164

sion over some selected polyhedra, and study the accuracy of integrations performed

165

using the compressed quadrature. Purposefully, we chose very complex shapes so that

166

the accuracy comparison is meaningful.

167

The polyhedra considered are shown in figures 1 and 2, which illustrate the dis-

168

tribution of discrete Leja points and the M − N points that are eliminated during

169

(5)

Algorithm 1 Construction of compressed quadrature Q

^CQ

:= ( L, λ) over a polyhe- dron

1:

Construct base quadrature Q

^BQ

:= (X, w) over the polyhedron

2:

Form Vandermonde-like matrix T on X using the base functions (equation (5))

3:

Extract discrete Leja points L ⊂ X by performing LU-decomposition of T

^t

4:

Form square submatrix T

^∗

from T on L using the base functions

5:

Get modified weights λ on L by solving T

^∗

λ = ν

(c)-Pol-3

(b)-Pol-2

(d)-Pol-4 (a)-Pol-1

(e)-Pol-5 (f)-Pol-6

(g)-Pol-7 (h)-Pol-8

Eliminated points Leja points

Leja points Eliminated points

Fig. 1. Quadrature compression over arbitrary polyhedra. Discrete Leja points represent the compressed quadrature and the collection of both Leja points and the eliminated points define the base quadrature.

the LU-decomposition process. The combination of these two sets of points define the

170

integration points of the base quadrature rule.

171

Note:. It can be seen from figures 1 and 2 that some of the integration points are

172

outside the polyhedra for concave shapes. This is not the result of the quadrature

173

compression. The only reason for this is because Q

^BQ

contains points that are outside

174

the polyhedra [33]. As mentioned earlier, the quadrature compression always selects

175

a subset of points form Q

^BQ

.

176

In all the examples presented in this work, we consider fifth-order quadrature

177

rules. The number of points in the base quadrature (N

BQ

) is dictated by the com-

178

plexity of the polyhedra (Table 1). However, by construction of the method, the

179

number of compressed quadrature points (N

CQ

) is equal to the cardinality of the

180

basis functions considered. In three-dimensions, the cardinality of fifth-order basis

181

This manuscript is for review purposes only.

(6)

6

Y. SUDHAKAR, A. SOMMARIVA, M. VIANELLO AND W. A. WALL (c)-Pol-3

(b)-Pol-2

(d)-Pol-4 (a)-Pol-1

(e)-Pol-5 (f)-Pol-6

(g)-Pol-7 (h)-Pol-8

Eliminated points Leja points

Leja points Eliminated points

Fig. 2. Additional polyhedra over which quadrature compression is performed.

functions is 56. This means that irrespective of the shape of the polyhedra, each

182

volume will have 56 integration points in Q

^CQ

.

183

Table 1

Number of integration points in base quadrature as well as compressed quadrature, quadrature compression time (tCQ), and the error in integration of basis functions (eCQ) while using QCQ.

N

BQ

N

CQ

t

CQ

(in seconds) e

CQ

Pol-1 96 56 0.001498 1 × 10

⁻¹⁵

Pol-2 144 56 0.004528 3 × 10

⁻¹⁵

Pol-3 156 56 0.004558 4 × 10

⁻¹⁹

Pol-4 504 56 0.004822 2 × 10

⁻¹⁶

Pol-5 1044 56 0.010110 2 × 10

⁻¹⁵

Pol-6 1044 56 0.010212 3 × 10

⁻¹⁵

Pol-7 1152 56 0.010511 2 × 10

⁻¹⁵

Pol-8 2520 56 0.022173 4 × 10

⁻¹⁶

Accuracy of the compressed quadrature rule is quantified by the quadrature error,

184

(7)

which is defined as,

185

(9) e

CQ

=

I

BQ

− I

^CQ

I

BQ

186

where I

BQ

and I

CQ

are the integral values obtained using the base quadrature and

187

the compressed quadrature rule, respectively.

188

First, the error incurred in the integration of basis functions, which are used to

189

perform the quadrature compression are quantified. In order to do so, e

CQ

of all the

190

56 basis functions are computed, and the maximum value among them for each of

191

the considered polyhedra is reported in table 1. It can be seen that the maximum

192

quadrature error for all the polyhedra is as low as 10

⁻¹⁵

. In the next step, it is

193

checked whether Q

^CQ

is accurate to integrate a general polynomial. In order to check

194

this, the following polynomials are integrated over the considered polyhedra, and the

195

corresponding error is reported in table 2.

196

p

0

(x) = 1

197

p

1

(x) = x + 2y + 3z

198

p

2

(x) = x

²

− 2y

²

+ z

²

199

p

3

(x) = −x

³

+ xyz + y

³

+ z

³

200

p

4

(x) = x

⁴

− 4y

⁴

+ 7xz

³

+ z

⁴

201

p

5

(x) = x

⁵

+ 5xyz

³

− 10xy

³

z + 5x

³

yz + y

⁵

+ z

⁵

202 203204

It is clearly evident from table 2 that the compressed quadrature is accurate

205

enough to integrate all the considered polynomials over all the polyhedra; the max-

206

imum error is of the order of 10

⁻¹⁴

. This is despite the fact that the considered

207

polyhedra include highly complex and concave shapes. Another remarkable observa-

208

tion is that for Pol-8, more than 2500 points in Q

^BQ

is reduced to 56 points in Q

^CQ

.

209

Even after such a drastic reduction, e

CQ

stays as low as 10

⁻¹⁵

for all the polynomials.

210

Therefore, it can be concluded that the quadrature compression procedure is robust

211

enough to be used in EIMs.

212

Table 2

Error incurred in integrating the polynomial functions using the compressed quadrature.

p

0

(x) p

1

(x) p

2

(x) p

3

(x) p

4

(x) p

5

(x) Pol-1 4 ×10

⁻¹⁶

0 1 ×10

⁻¹⁵

2 ×10

⁻¹⁵

2 ×10

⁻¹⁵

3 ×10

⁻¹⁵

Pol-2 0 3 ×10

⁻¹⁵

9 ×10

⁻¹⁶

9 ×10

⁻¹⁶

2 ×10

⁻¹⁴

4 ×10

⁻¹⁵

Pol-3 0 2 ×10

⁻¹⁸

1 ×10

⁻¹⁸

3 ×10

⁻¹⁹

7 ×10

⁻¹⁹

1 ×10

⁻¹⁹

Pol-4 1 ×10

⁻¹⁶

1 ×10

⁻¹⁵

2 ×10

⁻¹⁶

8 ×10

⁻¹⁷

2 ×10

⁻¹⁶

6 ×10

⁻¹⁶

Pol-5 9 ×10

⁻¹⁶

1 ×10

⁻¹⁴

2 ×10

⁻¹⁵

7 ×10

⁻¹⁶

1 ×10

⁻¹⁴

2 ×10

⁻¹⁵

Pol-6 2 ×10

⁻¹⁵

3 ×10

⁻¹⁵

5 ×10

⁻¹⁵

8 ×10

⁻¹⁶

2 ×10

⁻¹⁴

5 ×10

⁻¹⁵

Pol-7 9 ×10

⁻¹⁶

8 ×10

⁻¹⁵

1 ×10

⁻¹⁶

3 ×10

⁻¹⁵

1 ×10

⁻¹⁴

5 ×10

⁻¹⁵

Pol-8 2 ×10

⁻¹⁶

8 ×10

⁻¹⁵

2 ×10

⁻¹⁵

2 ×10

⁻¹⁵

3 ×10

⁻¹⁵

2 ×10

⁻¹⁵

The quadrature compression algorithm requires performing the LU-decomposition

213

of the underdetermined system presented in equation (5), and the solution of the

214

matrix system given in equation (6). The time required to execute the proposed

215

This manuscript is for review purposes only.

(8)

8 method (t

CQ

) is presented in table 1. It can be seen that when N

BQ

is higher, t

CQ 216

increases. This is due to the fact that the dimension of the Vandermonde-like matrix

217

T

^t

(N

BQ

×56) increases when N

^BQ

is higher. As a result, the time required to perform

218

LU factorization of the matrix goes up, and hence t

CQ

. However, we can expect that

219

owing to the reduced number of integration points, the compressed quadrature can

220

lead to efficient integration of the weak forms associated with EIMs. This feature is

221

explored in the next section.

222

3. Application to embedded interface methods. In the previous section,

223

the quadrature compression is performed over various complex shaped polyhedra,

224

and the results of integrating predefined polynomials are reported. This method is

225

implemented to integrate weak forms of the Navier-Stokes equations discretized by

226

using an embedded interface method [27–29]. The performance of the quadrature

227

compression algorithm in EIM framework is studied here. We consider two classes of

228

problems for which EIMs are ideally suited: flow over multiple immersed objects and

229

flow past arbitrary moving structures.

230

In all the test cases, two simulations are performed: one simulation involving base

231

quadrature obtained from the direct divergence method [33] and another utilizing the

232

compressed version of the base quadrature to perform weak form integration over the

233

cut-elements. The comparison of these two simulations enables us to quantify the

234

influence of using the compressed quadratures on the accuracy, rate of convergence,

235

and the computational efficiency of EIM simulations.

236

3.1. Kim-Moin flow. In the last section, it is shown that the compression of

237

quadrature rules introduced errors as low as 10

⁻¹⁴

even for very complex polyhedra.

238

However, in order to prove the usefulness of the compressed quadratures, it is essen-

239

tial to show that these errors do not affect the rate of convergence of finite element

240

simulations. In order to do so, we consider the Kim-Moin flow [15] for which the

241

analytical solutions are readily available.

242

The velocity and pressure solution are given as,

243

u

x

(x, y) = −cos(2πx)sin(2πy) (10)

244

u

y

(x, y) = sin(2πx)cos(2πy) (11)

245

p(x, y) = − 1

4 (cos(4πx) + cos(4πy)) (12)

246

which satisfy the continuity equation ∇ · u = 0. The numerical solution is computed

247

on a circular domain of radius 0.45 units, whose centre is located at (0.5,0.5). This

248

circular domain is immersed into the background fluid mesh defined on [0, 1]

²

, rotated

249

by 45

^o

(see figure 3a). The fluid mesh contains one element in the depth direction, so

250

that the interface cut produces 3D polyhedra.

251

It is to be mentioned that on the boundary of the circular domain, the boundary

252

conditions for velocity (given by the analytical solution) are enforced weakly by the

253

recently derived variant of Nitche’s method [27–29]. Since this is a pure Dirichlet

254

problem the pressure value, given by equation (12), is fixed at the centre node (0.5,0.5).

255

The background fluid mesh is discretized with uniform wedge elements. The

256

pressure distribution within the circular domain is presented in figure 3a, and the

257

vortex distribution qualitatively resemble the expected flow behavior. In order to

258

quantify the errors and to predict the rate of convergence, the L

2

−norm of pressure

259

and velocity errors for various mesh densities are computed. The plot of L

2

−norm

260

with increasing mesh density is given in figure 3b. Owing to the smoothness of

261

(9)

Z Y X Pressure

-0.5 -0.00402-0.00402 0.4920.492 Z

-0.5 X

Pressure Y

(a) Pressure distribution

10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰

10 100

L2−norm

Number of elements in each direction

||u − u_h||2

||p − p_h||2

2nd

order Base quad Compressed quad

(b) Convergence plot

Fig. 3. Kim-Moin flow

the solution field, as expected, we obtain optimal order of convergence rate for both

262

pressure and velocity. It can be seen that the simulations with quadrature compression

263

also maintain the optimal convergence rate. Moreover, the magnitude of L

2

−norm is

264

also exactly the same for both the base quadrature and the compressed quadrature.

265

From the results presented in this section, it can be concluded that the compressed

266

quadrature does not introduce additional errors into the computation. In addition, it

267

also enables us to achieve the same rate of convergence as that of the base quadrature.

268

3.2. Flow past 3D multiple stationary interfaces. This example considers

269

flow past three-dimensional multiple stationary interfaces. Three spheres of diameter

270

D

s

= 1m are placed inside a pipe of dimensions 18m ×1.5m×1.5m. The configuration

271

of the simulation is depicted in figure 4. A parabolic velocity profile with maximum

272

velocity u

max

= 1m/s is specified in the inflow (left boundary). On all the surfaces,

273

except the outflow (right boundary), no-slip condition is enforced. The kinematic

274

viscosity of the fluid, ν = 0.01m

²

/s, results in Reynolds number Re = 100 by taking

275

D

s

as the length scale. Unsteady simulations with time step ∆t = 0.1 are performed

276

for 1250 steps.

277

Fig. 4. Geometric details of the multiple stationary interfaces problem.

Since the present simulation involves flow over stationary interfaces, the base

278

quadrature construction using the direct divergence method and its compression need

279

to be carried out only once in the beginning of the simulation.

280

The pressure distribution within the domain at the end of the simulation are

281

illustrated in figure 5. It is directly evident from this figure that both the simula-

282

tions yield the same qualitative results (which also still holds when studied in more

283

This manuscript is for review purposes only.

(10)

10

(a) Without quadrature compression

(b) With quadrature compression

Fig. 5. Pressure distribution over stationary spheres

detail). Thorough quantitative accuracy comparison is presented for the forthcoming

284

examples.

285

3.3. Flow over a rapidly accelerating airfoil. Results of the previous sec-

286

tion demonstrated the accuracy of quadrature compression for stationary interface

287

simulations. Since the interface is held stationary in that example, the quadrature

288

compression is performed only once in the beginning of the simulation. However,

289

EIMs are mainly used and are most challenging in practical applications in which the

290

interface changes its shape and position with time. This leads to different polyhedral

291

shapes at each time step over which the numerical integration has to be carried out.

292

Owing to this fact, the geometrical cutting operations and the compression of the

293

quadrature schemes need to be performed at each time step; also, all kinds of critical

294

and challenging polyhedral shapes will appear naturally. The present and the next

295

examples test the accuracy of the simulations using quadrature compression in such

296

situations.

297

The present example resolves the flow field around a rapidly accelerated airfoil in

298

a still fluid, as described in [13]. The NACA0012 airfoil is used in our simulations.

299

It accelerates from rest to a velocity U = 1, and then it traverses with this constant

300

velocity. Throughout the simulation, the airfoil maintains a constant angle of attack

301

of 35

^o

. This test case is a pseudo-3D simulation in which only one finite element

302

is used in the depth direction. The comparison of time-dependent forces acting on

303

the airfoil enables us to perform quantitative analysis of the accuracy of compressed

304

quadrature rules.

305

(11)

The unsteady displacement of the airfoil is given as follows,

306

x(τ ) = − 1 2

τ − τ

a

π sin πτ τ

a

for 0 ≤ τ ≤ τ

^a

(13a)

307

x(τ ) = τ

a

2 − τ for τ > τ

a

(13b)

308309

where τ =

^tU_c

is the non-dimensional time, τ

a

= 0.8 is the acceleration duration and

310

c is the chord length of the airfoil. Reynolds number, the non-dimensional number

311

that characterizes the flow field, Re =

^{U c}_ν

is set to be 100, where ν is the kinematic

312

viscosity of fluid. The computational domain is taken to be 24c × 20c, where c is the

313

chord length of the airfoil. The complete subdomain within which the airfoil traverses

314

is discretized with a very fine mesh, and a coarse mesh is used away from this region.

315

The time step used in the simulation is ∆τ = 0.02.

316

As in the previous example, two simulations are performed: one with the base

317

quadrature and another with the compressed quadrature rule. The evolution of vor-

318

ticity field around the airfoil at different instances of time is illustrated in figure 6.

319

Since both simulations produced same vorticity distribution, only the results obtained

320

from the simulation that uses compressed quadrature rule are presented. It can be

321

seen that negative vorticity is generated around leading-edge and the upper surface,

322

whereas positive vorticity is generated over the bottom surface and the trailing-edge

323

region. As the airfoil starts moving, over the period of time, the positive vorticity is

324

shed from the trailing edge to the wake region. These qualitative features agree very

325

well with the observations reported in [13].

326

t=0.5 t=1.0 t=1.5

t=2.0 t=2.5 t=3.0

4

2

0

-2 -4 vorti-z

Fig. 6. Evolution of vorticity field around airfoil

The main objective of this simulation is to investigate whether the use of com-

327

pressed quadrature rule for the weak form integration leads to accurate quantitative

328

results in fluid flow modeling. The drag (C

D

) and lift (C

L

) coefficients computed

329

from the above two simulations are compared for this purpose.

330

The time evolution of C

D

and C

L

are shown in figure 7. Lift and drag start raising

331

during the acceleration phase, and reach their peak values. After this, they fall down,

332

and settle almost to a constant value during the constant velocity translation phase.

333

It is directly apparent from the figure that the drag- and lift-curves produced from

334

both the simulations fall exactly one over the another. This demonstrates that the

335

compressed quadrature rules are accurate enough to compute the time-dependent

336

forces acting on the airfoil.

337

This manuscript is for review purposes only.

(12)

12

0 0.5 1 1.5 2 2.5

0 0.5 1 1.5 2 2.5 3

CD

τ

Base quad.

Compressed quad.

(a) Drag coefficient

0 0.5 1 1.5 2 2.5

0 0.5 1 1.5 2 2.5 3

CL

τ

Base quad.

Compressed quad.

(b) Lift coefficient

Fig. 7. Comparison of drag and lift coefficients for a rapidly accelerated airfoil

3.4. Fluid-structure interaction of a bending beam. The last section inves-

338

tigated the accuracy of the compressed quadrature for moving boundary simulations.

339

However, the problem considered was pseudo-3D, and hence the resulting polyhedral

340

shapes are of limited complexity. In order to study the influence of the proposed algo-

341

rithm, a real 3D problem involving a coupled fluid-structure interaction of a flexible

342

bending beam is simulated.

343

The complete configuration of the simulation is shown in figure 8. A flexible beam,

344

whose bottom part is fixed, is immersed in the fluid flow. The material properties

345

of the beam are: Young’s modulus, E = 100P a, Poisson’s ratio ν = 0.1, and density

346

ρ

s

= 10kg/m

³

. On the fluid domain, a parabolic inflow velocity profile with u

max

=

347

1m/s is specified at the inlet. The top, bottom and side walls are no-slip boundaries.

348

The kinematic viscosity of the fluid ν

f

= 0.05m

²

/s. This corresponds to Reynolds

349

number of Re = 20, where the length scale is the height of the beam. The FSI method

350

proposed in [12] is used to simulate this test case.

351

The flexible beam starts bending due to the fluid loads acting on the beam. In

352

order to quantify the accuracy of the compressed quadrature, the x −component of

353

(13)

Fig. 8. Configuration of fluid-structure interaction of a bending beam.

displacement of the beam at point A (figure 8) is given in figure 9. This plot shows

354

that the simulation with compressed quadrature produces exactly the same result as

355

the base quadrature.

356

0 0.05 0.1 0.15 0.2 0.25

0 2 4 6 8 10 12

dx

t Base quad Compressed quad

Fig. 9. Comparison of displacement component in x−direction at point A in figure 8with time.

This result is encouraging due to the following reason. In FSI examples, the

357

interface movement at each step leads to different orientation and relative position of

358

the interface with respect to the cut-elements. This means that at each new time step,

359

the cut configuration is different and we get different polyhedral shaped volume-cells

360

over which the quadrature compression is carried out. Fluid dynamic simulations are

361

very sensitive to the accuracy of quadrature rules: especially in coupled problems, the

362

sensitivity is much more pronounced because even a small error in the integrals will

363

change the pressure distribution (a very sensitive quantity in incompressible flows),

364

and this will affect the structural movement, which in-turn changes the fluid flow.

365

The fact that we get accurate matching of the time-dependent quantities imply that

366

for every polyhedral shapes generated throughout our simulation, the quadrature

367

compression is accurate.

368

3.5. Discussion on computational efficiency. The use of quadrature com-

369

pression leads to reduction in the number of integration points, which can help to

370

reduce the simulation time. However, some amount of computational time is spent in

371

performing the compression over each polyhedron (Table 1). This section studies the

372

This manuscript is for review purposes only.

(14)

14 overall influence of using the compressed quadrature rules on the simulation time for

373

the above simulations.

374

In EIMs, only cut-elements require a special quadrature rule with a large num-

375

ber of points, and in the remaining non-cut elements the efficient traditional Gauss

376

quadrature rules can be directly employed. The base quadrature for volume-cells may

377

contain more than 1000 points but the compressed quadrature, by construction, needs

378

only 56 points for the same accuracy. Due to this reduction in number of points, the

379

evaluation time is greatly reduced when using the compressed quadrature, and this

380

is quantified in table 3. The evaluation time here implies the time required to per-

381

form the weak form integration throughout the computational domain and assemble

382

the relevant entries into the stiffness matrix. The efficiency gain is quantified by η

E

,

383

which is defined as follows

384

(14) η

E

= E

BQ

− E

^CQ

E

BQ 385

where E

BQ

and E

CQ

are the evaluation time over the whole computational domain

386

when using base quadrature and compressed quadrature, respectively. It is to be

387

mentioned that the evaluation time includes neither the time required to construct

388

base quadrature nor performing compression operations on them.

389

Table 3

Ratio of number of cut-elements (Ncut) to the total number of elements (N_total) in the mesh, evaluation times and efficiency gain (η_E). For moving interface simulations,Ncut/N_totalchanges with time, and the ratio at the initial configuration is reported.

N

cut

/N

total

(%) Evaluation time (s) η

E

(%)

E

BQ

E

CQ

Stationary spheres 11.05 3.853 × 10

⁴

2.895 × 10

⁴

24.86 Accelerating airfoil 0.265 1.138 × 10

⁴

0.987 × 10

⁴

13.20 Bending beam 0.809 2.735 × 10

⁴

2.086 × 10

⁴

23.73 η

E

depends on two factors: ratio of the number of cut-elements (N

cut

) to the

390

total number of elements in the mesh (N

total

), and the complexity of polyhedra. By

391

comparing the numbers given in table 3 for the moving boundary simulations, it can

392

be seen that when N

cut

/N

total

is increased from 0.265% to 0.809%, η

E

is increased

393

from 13.20% to 23.73%. However, this can not define a general behavior because the

394

number of integration points in Q

^BQ

depends on the complexity of polyhedra [33].

395

When the interface cut produces polyhedra of limited complexity, the number of

396

integration points in Q

^BQ

is not very high and hence the η

E

is marginal even though

397

N

cut

/N

total

is high. This is the reason why η

E

is only 24.86% for stationary interface

398

simulation, although N

cut

/N

total

is as high as 11.05%.

399

Table 4

Time required for quadrature compression (tCQ), geometrical cutting operations (tcut), comparison of total simulation times and computational efficiency gain due to the use of QCQ (ηT).

t

CQ

(s) t

cut

(s) Total simulation time (s) η

T

(%)

T

BQ

T

CQ

Stationary spheres 1.4004 19.43 4.188 × 10

⁴

3.191 × 10

⁴

23.80 Accelerating airfoil 20.996 210 4.350 × 10

⁴

3.882 × 10

⁴

10.76 Bending beam 427.78 2791 7.893 × 10

⁴

7.296 × 10

⁴

7.566

(15)

The most important quantity is the total simulation time, which is given in ta-

400

ble 4. By observing η

T

(defined exactly like η

E

but with total simulation times T

BQ 401

and T

CQ

), it is directly evident that for the stationary interface problem, the compu-

402

tational efficiency gain in η

E

directly translates to η

T

. However, for moving boundary

403

simulations, this is not the case. One of the reasons is that since the interface is

404

non-stationary, the geometrical cutting operations required to form the volume-cells

405

and the quadrature compression need to be performed at each time step, and this

406

contributes to reduction in η

T

. For bending beam simulation, η

T

is reduced when

407

compared to η

E

. Since this example is an FSI simulation, it involves solving the

408

structural dynamics equations and moreover, the time required to perform the ge-

409

ometrical cutting operations (t

cut

) as well as the quadrature compression are also

410

larger. The time invested in solving the structural dynamics equations and t

cut

are

411

the same irrespective of using Q

^BQ

or Q

^CQ

. Owing to these operations, η

T

is smaller

412

when compared to η

E

, which is defined only based on the time required to compute

413

the stiffness matrix associated with the governing equations of fluid flow. However,

414

despite all these points, by simply applying certain standard linear algebraic methods,

415

we obtain as much as 7.56% gain in efficiency. This is quite impressive considering

416

the other expensive parts of such a coupled simulation. From this observation, It can

417

be concluded that the use of quadrature compression always lead to improvements in

418

total simulation time.

419

An interesting extension of the present work is to apply the quadrature compres-

420

sion to polygonal and polyhedral finite element methods [8, 17, 25, 35, 40] in which

421

all the elements in the mesh are of polyhedral shape. Therefore special quadrature

422

schemes need to be used for all the elements in the computational domain. As a

423

result, the application of the quadrature compression in such methods might lead

424

to significant gain in computational efficiency when compared to EIMs in which the

425

quadrature compression is applied only to a few elements in the mesh. In order to

426

have a preliminary impression of the advantage of using quadrature compression in

427

polyhedral FEM, we define an efficiency parameter (η

cutE

), similar to η

E

in equa-

428

tion (14). While η

E

is based on the evaluation time over the whole computational

429

domain, η

cutE

is defined by considering the evaluation time only on the cut-elements

430

which requires integration over arbitrary polyhedra. The estimated η

cutE

for the con-

431

sidered simulations are shown in table 5, and it can be seen that it is significantly

432

larger than η

E

. η

cutE

can be considered as the parameter characterising the effi-

433

ciency gain in evaluation time for polyhedral FEM. This significant efficiency gain in

434

evaluation time will directly reflect as tremendous gain in total simulation time.

435

Table 5

Efficiency gain in evaluation time on cut-elements

η

cutE

(%) Stationary spheres 58.27 Accelerating airfoil 95.86

Bending beam 93.96

In addition, the quadrature compression techniques can be of help in variety of

436

other fields: level set based methods [18, 26], electronic structure calculations [1, 2],

437

aerospace applications [9, 30, 38], and computational geometry [5, 19, 37], to name a

438

few.

439

This manuscript is for review purposes only.

(16)

16 4. Conclusion. We apply the multivariate quadrature compression to the al-

440

gebraic quadrature formulas on complex polyhedra. The quadrature compression is

441

very simple to implement since it is completely based on standard numerical alge-

442

braic methods. It operates on an existing quadrature rule by selecting a subset of

443

nodes, and modify the corresponding weights in such a way that the accuracy of the

444

original quadrature rule is preserved. In the compressed quadrature rule, the number

445

of integration points is always equal to the dimension of the considered polynomial

446

space. The compressed quadratures are applied in an embedded interface method

447

to integrate the weak form of the Navier-Stokes equations. Simulations of flow past

448

stationary and moving interface problems demonstrate that compressed quadratures

449

preserve accuracy, order of convergence, and improve the computational efficiency of

450

embedded interface methods.

451

REFERENCES 452

[1] A. Alam, S. N. Khan, B. G. Wilson, and D. D. Johnson, Efficient isoparametric integration 453

over arbitrary space-filling Voronoi polyhedra for electronic structure calculations, Phys.

454

Rev. B, 84 (2011), p. 045105.

455

[2] P. M. Boerrigter, G. Te Velde, and E. J. Baerends, Three-dimensional numerical in- 456

tegration for electronic structure calculations, Int. J. Quantum Chem., XXXIII (1988), 457

pp. 87–113.

458

[3] L. Bos, S. D. Marchi, A. Sommariva, and M. Vianello, Computing multivariate Fekete and 459

Leja points by numerical linear algebra, SIAM J. Numer. Anal., 48 (2010), pp. 1984–1999.

460

[4] P. Businger and G. Golub, Linear least-squares solutions by householder transformations, 461

Numer. Math., 7 (1965), pp. 269–276.

462

[5] C. Cattani and A. Paoluzzi, Boundary integration over linear polyhedra, Comput.-Aided 463

Des., 22 (1990), pp. 130–135.

464

[6] E. B. Chin, J. B. Lasserre, and N. Sukumar, Numerical integration of homogeneous 465

functions on convex and nonconvex polygons and polyhedra, Comput. Mech., 56 (2015), 466

pp. 967–981.

467

[7] A. Civril and M. Magdon-Ismail, On selecting a maximum volume submatrix of a matrix 468

and related problems, Theor. Comput. Sci., 410 (2009), pp. 4801–4811.

469

[8] G. Dasgupta, Integration within Polygonal Finite Elements, J. Aerosp. Eng., 16 (2003), pp. 9–

470

18.

471

[9] A. R. Dobrovolskis, Inertia of any polyhedron, Icarus, 124 (1996), pp. 698–704.

472

[10] C. F. Dunkl and Y. Xu, Orthogonal Polynomials of Several Variables, Cambridge University 473

Press, 2001.

474

[11] M. Gentile, A. Sommariva, and M. Vianello, Polynomial interpolation and cubature over 475

polygons, J. Comput. Appl. Math., 235 (2011), pp. 5232 –5239.

476

[12] A. Gerstenberger and W. A. Wall, An extended finite element method / Lagrange multiplier 477

based approach for fluid-structure interaction, Comput. Methods Appl. Mech. Engrg, 197 478

(2008), pp. 1699–1714.

479

[13] H. Hamdani and M. Sun, Aerodynamic forces and flow structures of an airfoil in some un- 480

steady motions at small reynolds number, Acta Mech., 145 (2000), pp. 173–187.

481

[14] D. Huybrechs, Stable high-order quadrature rules with equidistant points, J. Comput. Appl.

482

Math., 231 (2009), pp. 933 –947.

483

[15] J. Kim and P. Moin, Application of a fractional-step method to incompressible navier-stokes 484

equations, J. Comput. Phys, 59 (1985), pp. 308 – 323.

485

[16] C. Lawson and R. Hanson, Solving Least Squares Problems, Society for Industrial and Applied 486

Mathematics, 1995.

487

[17] P. Milbradt and T. Pick, Polytope finite elements, Internat. J. Numer. Methods Engrg., 73 488

(2008), pp. 1811–1835.

489

[18] C. Min and F. Gibou, Geometric integration over irregular domains with application to level- 490

set methods, J. Comput. Phys, 226 (2007), pp. 1432–1443.

491

[19] B. Mirtich, Fast and accurate computation of polyhedral mass properties, J. Graph. GPU 492

Game tools, 1 (1996), pp. 31–50.

493

[20] S. E. Mousavi and N. Sukumar, Numerical integration of polynomials and discontinuous func- 494

tions on irregular convex polygons and polyhedrons, Comput. Mech., 47 (2011), pp. 535–

495

(17)

554.

496

[21] B. Mueller, F. Kummer, M. Oberlack, and Y. Wang, Simple multidimensional integra- 497

tion of discontinuous functions with application to level set methods, Internat. J. Numer.

498

Methods Engrg., 92 (2012), pp. 637–651.

499

[22] S. Natarajan, S. Bordas, and D. R. Mahapatra, Numerical integration over arbitrary polyg- 500

onal domains based on Schwarz-Christoffel conformal mapping, Internat. J. Numer. Meth- 501

ods Engrg., 80 (2009), pp. 103–134.

502

[23] J. P. Pereira, C. A. Duarte, D. Guoy, and X. Jiao, hp-Generalized FEM and crack surface 503

representation for non-planar 3-D cracks, Internat. J. Numer. Methods Engrg., 77 (2009), 504

pp. 601–633.

505

[24] M. Putinar, A note on Tchakaloff’s theorem, Proc. Amer. Math. Soc., 125 (1997), pp. 2409–

506

2414.

507

[25] M. M. Rashid and M. Selimotic, A three-dimensional finite element method with arbitrary 508

polyhedral elements, Internat. J. Numer. Methods Engrg., 67 (2006), pp. 226–252.

509

[26] U. Rasthofer, F. Henke, W. A. Wall, and V. Gravemeier, An extended residual-based vari- 510

ational multiscale method for two-phase flow including surface tension, Comput. Methods 511

Appl. Mech. Engrg, 200 (2011), pp. 1866–1876.

512

[27] B. Schott, U. Rasthofer, V. Gravemeier, and W. A. Wall, A face-oriented stabilized 513

Nitsche-type extended variational multiscale method for incompressible two-phase flow, 514

Internat. J. Numer. Methods Engrg., 104 (2015), pp. 721–748.

515

[28] B. Schott, S. Shahmiri, R. Kruse, and W. Wall, A stabilized nitsche-type extended em- 516

bedding mesh approach for 3d low- and high-reynolds-number flows, Internat. J. Numer.

517

Methods Fluids, (2016),doi:10.1002/fld.4218.

518

[29] B. Schott and W. A. Wall, A new face-oriented stabilized XFEM approach for 2D and 3D 519

incompressible Navier-Stokes equations, Comput. Methods Appl. Mech. Engrg, 276 (2014), 520

pp. 233–265.

521

[30] B. Singh and D. Guptasarma, New method for fast computation of gravity and magnetic 522

anomalies from arbitrary polyhedra, Geophysics, 66 (2001), pp. 521–526.

523

[31] A. Sommariva and M. Vianello, Computing approximate fekete points by QR factorizations 524

of vandermonde matrices, Comput. Math. Appl., 57 (2009), pp. 1324 – 1336.

525

[32] A. Sommariva and M. Vianello, Compression of multivariate discrete measures and appli- 526

cations, Numer. Funct. Anal. Optim, 36 (2015), pp. 1198–1223.

527

[33] Y. Sudhakar, J. P. M. de Almeida, and W. A. Wall, An accurate, robust, and easy- 528

to-implement method for integration over arbitrary polyhedra: Application to embedded 529

interface methods, J. Comput. Phys, 273 (2014), pp. 393–415.

530

[34] Y. Sudhakar and W. A. Wall, Quadrature schemes for arbitrary convex/concave volumes 531

and integration of weak form in enriched partition of unity methods, Comput. Methods 532

Appl. Mech. Engrg, 258 (2013), pp. 39–54.

533

[35] N. Sukumar and A. Tabarraei, Confirming polygonal finite elements, Internat. J. Numer.

534

Methods Engrg., 61 (2004), pp. 2045–2066.

535

[36] Tchakaloff, Formules de cubature mécaniques à coefficients nonnégatifs, Bull. Sci. Math., 81 536

(1957), pp. 123–134.

537

[37] H. G. Trimmer and J. M. Stern, Computation of global geometric properties of solid objects, 538

Comput.-Aided Des., 12 (1980), pp. 301–304.

539

[38] D. Tsoulis, Analytical computation of the full gravity tensor of a homogeneous arbitrarily 540

shaped polyhedra source using line integrals, Geophysics, 77 (2012), pp. F1–F11.

541

[39] G. Ventura, On the elimination of quadrature subcells for discontinuous functions in the 542

eXtended Finite-Element Method, Internat. J. Numer. Methods Engrg., 66 (2006), pp. 761–

543

795.

544

[40] M. Wicke, M. Botsch, and M. Gross, A finite element method on convex polyhedra, Comput.

545

Graph. Forum, 26 (2007), pp. 355–364.

546