ECCM 2010
IV European Conference on Computational Mechanics Palais des Congrès, Paris, France, May 1621, 2010
Wavelet and Fast Multipole Data Sparse Approximations of Boundary Element Method matrices in a Fluid Flow Solver
J. Ravnik1 , L. Škerget2 , J. Lupše3
1 2 3
University of Maribor, Faculty of Mechanical Engineering, Smetanova ulica 17, SI2000 Maribor, Slovenia, jure.ravnik@unimb.si University of Maribor, Faculty of Mechanical Engineering, Smetanova ulica 17, SI2000 Maribor, Slovenia,
ECCM 2010
IV European Conference on Computational MechanicsPalais des Congrès, Paris, France, May 1621, 2010
Wavelet and Fast Multipole Data Sparse Approximationsof Boundary Element Method matrices in a Fluid Flow Solver
J. Ravnik
1
, L. Škerget
2
, J. Lupše
3
1
University of Maribor, Faculty of Mechanical Engineering, Smetanova ulica 17, SI2000 Maribor, Slovenia, jure.ravnik@unimb.si
2
University of Maribor, Faculty of Mechanical Engineering, Smetanova ulica 17, SI2000 Maribor, Slovenia, leo@unimb.si
3
University of Maribor, Faculty of Mechanical Engineering, Smetanova ulica 17, SI2000 Maribor, Slovenia, janez.lupse@unimb.si
In this paper we present a Boundary Element Method (BEM) based numerical algorithm for thesimulation of viscous ﬂuid ﬂow. The algorithm solves the velocityvorticity formulation of the NavierStokes equations. The governing equations are the Poisson type kinematics equation and the diffusionadvection type energy and vorticity transport equations. Single domain BEM is used to solve the kinematics equation for boundary values of vorticity. The transport equations and the solution of domainvelocities from the kinematics equation are solved using the domain decomposition approach, i.e. thesubdomain BEM. Validity and versatility of the algorithm was veriﬁed by solving benchmark ﬂowssuchas ﬂow in a 3D lid driven cavity and ﬂow and heat transfer during natural convection (Ravnik et al. [1]).After discretization the single domain BEM yields a fully populated system of linear equations.In this work we consider and compare two approaches aimed at decreasing computational and storagerequirements from
O
(
n
2
)
to
O
(
n
log
n
)
: The Fast Multipole Method (FMM) and the Wavelet Transform(WT). We examined the accuracy of ﬂuid ﬂow simulations when these approximation methods are used.FMM is used to provide a sparse approximation of the fully populated BEM domain matrices. Theintegral form of the kinematics equation without derivatives of the velocity and vorticity ﬁelds takes thefollowing form:
c
(
ξ
)
v
(
ξ
)+
Z
Γ
v
∇
u
⋆
·
nd
Γ
=
Z
Γ
v
×
(
n
×
∇
)
u
⋆
d
Γ
+
Z
Ω
(
ω
×
∇
u
⋆
)
d
Ω
,
(1)where
ξ
is the collocation point,
u
⋆
=
1
/
4
π

r
−
ξ

is the fundamental solution of the Laplace equation,
v
is the velocity ﬁeld,
ω
is the vorticity ﬁeld and
n
is the unit normal. The FMM is based on the fact that itis possible to separate the variables (i.e. the collocation point
ξ
and the domain integration point
r
) of theintegral kernels in equation (1) by series expansion. The gradient of the Laplace fundamental solution isexpanded into a spherical harmonics series thus separating the variables. The collocation points on theboundary and the domain cells in the domain are grouped into clusters using a hierarchical algorithmsforming boundary and boundarydomain cluster trees (Ravnik et al. [2]).We studied the inﬂuence of the admissibility criterion and the inﬂuence of the number of termson the ﬁnal solution of ﬂuid ﬂow. We found, that the error, introduced by the usage of FMM into ournonlinear ﬂuid ﬂow solver, is ampliﬁed in cases of higher nonlinearity. The conclusion being that given acomputational grid the admissibility criterion depends on the nonlinearity of the problem we are solving.Figure 1 presents velocity proﬁles of a benchmark 3D driven cavity test case solved by Yang et al. [3] andby present code without the use of FMM and with the use of FMM with different number of expansionterms. We observe that as the Reynolds number (nonlinearity) increases, the solutions with lower numberof expansion terms become less accurate.Secondly, we used the wavelet transform to obtain a data sparse approximation of BEM matrices.1
xvx
v z z
0 0.2 0.4 0.6 0.8 11 0.5 0 0.5 1
10.500.5100.20.40.60.81
Yang 98full251694
xvx
v z z
0 0.2 0.4 0.6 0.8 11 0.5 0 0.5 1
10.500.5100.20.40.60.81
Yang 98full251694
xvx
v z z
0 0.2 0.4 0.6 0.8 11 0.5 0 0.5 1
10.500.5100.20.40.60.81
Yang 98full251694
Figure 1: Velocity proﬁles through the center of a 3D lid driven cavity. Left
Re
=
100, middle
Re
=
400 and right
Re
=
1000. Benchmark solution [3] and soluitons with and without FMM are presented.Decrease of solution accuracy with increasing Reynolds number can be observed.The wavelet transform is a mathematical tool, developed specially for saving computational time andcomputer storage. Let
W
be a wavelet matrix, which if multiplied by a vector, transforms the vector intoa vector of wavelet coefﬁcients. The matrix
W
is never stored in memory. Its structure and layout of nonzero elements are known, so the matrix is set up on the ﬂy, during matrix vector multiplication.The transpose of the wavelet matrix is equal to its inverse,
W
T
=
W
−
1
. If
{
b
}
is a vector and
[
B
]
aBEM matrix, we may write matrix times a vector product as
[
B
]
{
b
}
=
W
T
W
[
B
]
W
T
W
{
b
}
.
(2)The product
W
[
B
]
is the wavelet transform of all columns in
[
B
]
, while
(
W
[
B
])
W
T
transforms all rows inthe product
W
[
B
]
. Thus the majority of information is written in large elements of
[
B
w
] =
W
[
B
]
W
T
, whilethe redundant information of
[
B
]
is represented in small elements in
[
B
w
]
. Small elements of
[
B
w
]
may beset to zero without greatly diminishing the accuracy of the matrix  vector product (2). This operation iscalled
thresholding
. We used wavelet level dependent threshold. Elements in the matrix, whose absolutevalue is less than the thresholding limit, are set to zero. The zeros in the wavelet approximation of thedomain matrix
[
B
w
]
are not stored, thus saving storage space. Compressed row storage matrix format isused.We compared FMM and WT methods in terms of ﬂuid ﬂow and heat transfer solution accuracy.Several ﬂow and heat transfer benchmark problems were investigated. We observed that using a densermesh yields more accurate results and it enables better data ratio for the same error. Higher nonlinearityof the problem caused higher error in the ﬁnal ﬂow ﬁeld, compared to a less nonlinear problem simulatedon the same computational mesh at the same compression level. We found that both methods cause anerror in the ﬁnal ﬂow ﬁeld of the same order of magnitude and behave in the same manner towards meshreﬁnement and increase of nonlinearity.
References
[1] J. Ravnik, L. Škerget, and Z. Žuniˇc. Velocityvorticity formulation for 3D natural convection in an inclinedenclosure by BEM.
Int. J. Heat Mass Transfer
, 51:4517–4527,2008.[2] J. Ravnik, L. Škerget, and Z. Žuniˇc. Fast single domain–subdomain BEM algorithm for 3D incompressibleﬂuid ﬂow and heat transfer.
Int. J. Numer. Meth. Engng.
, 77:1627–1645,2009.[3] J.Y. Yang, Y.N. Chen S.C. Yang, and C.A. Hsu. Implicit Weighted ENO Schemes for the ThreeDimensionalIncompressible Navier–Stokes Equations.
J. Comput. Phys.
, 146(1):464–487,1998.[4] J. Ravnik, L. Škerget, and Z. Žuniˇc. Comparison between wavelet and fast multipole data sparse approximations for Poisson and kinematics boundary – domain integral equations.
Comput. Meth. Appl. Mech. Engrg.
,198:1473–1485,2009.
2