VTK  9.7.20261119
PyrCnBasis.h
Go to the documentation of this file.
1// Arbitrary-order Lagrange interpolants on the reference pyramid.
2//
3// A pyramid's reference cell (see vtkDGPyr::Parameters) has its quadrilateral
4// base at t = 0, r,s in [-w, w], and its apex at t = 1, where w = 1 - t is the
5// base's own half-width at that height. Writing a = (r + w)/(2w),
6// b = (s + w)/(2w), c = t undoes that collapse, and in those coordinates the
7// order-n pyramid space is
8//
9// V_n = span{ a^p b^q (1-c)^max(p,q) g(c) : deg g <= n - max(p,q) },
10//
11// that is: the coefficient of a^p b^q is a polynomial in c of degree at most
12// n that is divisible by (1-c)^max(p,q). (At n = 1 this is the classical
13// rational space span{1, r, s, t, rs/(1-t)}; see PyrC1Basis.h.)
14//
15// That is the rational pyramid space of M. Bergot, G. Cohen and M. Durufle,
16// "Higher-order Finite Elements for Hybrid Meshes Using New Nodal Pyramidal
17// Elements", J. Sci. Comput. 42:345-381 (2010), doi:10.1007/s10915-009-9334-9;
18// its dimension is (n+1)(n+2)(2n+3)/6, which is what
19// vtkDGOperatorEntry::PyramidFunctionCount returns, and PyrGnBasis.h and
20// Basis/Bezier/PyrCnBasis.h span the same space at the same order. The space is
21// rational because a conforming pyramid element cannot be polynomial: its
22// quadrilateral face must carry the same traces as a hexahedron's and its
23// triangular faces the same as a tetrahedron's, which no single polynomial
24// space does (N. Nigam and J. Phillips, "High-order conforming finite elements
25// on pyramids", IMA J. Numer. Anal. 32:448-483, 2012, prove it). So every
26// pyramid basis in this directory divides by 1 - t, PyrC1Basis.h and
27// PyrC2Basis.h included; this one is no more rational than they are. The paper
28// is the reference for the space; the particular nodal construction below - the
29// spanning set psi_{i,j,d}, the layered lattice and the block back substitution
30// over it - was worked out for this file rather than transcribed from it, and
31// is one of several ways to interpolate on that space.
32//
33// The degrees of freedom sit on a layered lattice: layer d (0 <= d <= n) lies
34// at c = d/n and carries the uniform (m+1)^2 grid a_i = i/m, b_j = j/m with
35// m = n - d - the cross-section's own node count shrinking with it, to one node
36// at the apex. This is the lattice vtkDGLagrangePoints reports.
37//
38// Unlike the wedge (see WdgCnBasis.h), no product mu(a) nu(b) phi(c) can be
39// one of these interpolants once m >= 2: mu and nu would be the layer's
40// degree-m Lagrange functions, whose a^m b^m term forces (1-c)^m | phi, while
41// phi must also vanish at the other n-1 layers - 2n-d-1 > n roots in a
42// polynomial of degree at most n. So the interpolants genuinely mix the (a, b)
43// and c directions, and are built here instead by solving for them.
44//
45// Take the spanning set of V_n
46//
47// psi_{i,j,d}(a, b, c) = l_i(a) l_j(b) (1-c)^m omega_d(c),
48// omega_d(c) = prod_{k<d} (c - k/n), 0 <= i,j <= m = n-d, 0 <= d <= n,
49//
50// where l_i is the degree-m Lagrange polynomial on layer d's own grid. Each
51// psi lies in V_n because its a^p b^q coefficient carries the full (1-c)^m,
52// and m >= max(p,q); its degree in c is m + d = n. The d-th group vanishes on
53// every layer below d, so ordering the nodes by layer and the functions by d
54// makes the collocation matrix V (V[node][function]) block lower-triangular,
55// and - this being the point of using Lagrange factors rather than monomials -
56// its d-th diagonal block is the *diagonal* matrix (1-c_d)^m omega_d(c_d) I,
57// since l_i is 1 at layer d's i-th node and 0 at the others. The interpolants
58// are then the solution of V^T L(x) = psi(x) by block back substitution from
59// d = n down to 0, with nothing to invert but that scalar.
60//
61// Using monomials a^p b^q in place of l_i l_j spans the same space and gives
62// the same interpolants in exact arithmetic, but makes each diagonal block a
63// tensor-product Vandermonde matrix, and inverting one of those through the
64// Lagrange polynomials' monomial coefficients loses roughly a digit per order:
65// that costs 1e-3 by order 8 and 0.2 by order 9, with partition of unity
66// holding throughout, so the basis would stop interpolating without looking
67// wrong. Nothing here forms a monomial coefficient at all - l_i is evaluated as
68// the product prod_{k!=i} (x - x_k)/(x_i - x_k), whose relative error stays at
69// rounding - and the worst |L_i(x_j) - delta_ij| over the lattice measures
70// 2e-15 at order 4, 3e-15 at 6, 1e-14 at 9, 1e-13 at 12 and 1e-9 at 20. What
71// growth is left is the Lebesgue constant of equispaced nodes, which the
72// hexahedron's and wedge's bases have too (HexCnBasis.h measures 7e-15 at
73// order 12 and 9e-13 at 20 on the same test), so this basis needs no order
74// bound of its own either.
75//
76// Everything the substitution needs is closed form: omega_d(c_K) = K!/((K-d)! n^d)
77// and (1-c_K)^M = ((n-K)/n)^M.
78//
79// The degrees of freedom are enumerated with i (the a-axis) varying fastest,
80// then j (the b-axis), then d (the layer) slowest, matching every other
81// arbitrary-order basis in this module. order[0], order[1] and order[2] are
82// always equal (see vtkDGOperatorEntry::PyramidFunctionCount) - a single
83// degree n, not one per axis - and every workspace is sized off order[2]
84// alone so its size stays a literal constant once compiled to GLSL.
85if (abs(tt - 1.) < eps)
86{
87 tt = tt <= 1. ? 1. - eps : 1. + eps;
88}
89RealT ww = 1. - tt;
90RealT aa = (rr + ww) / (2. * ww);
91RealT bb = (ss + ww) / (2. * ww);
92
93// Where each group of order[2] - d + 1 squared functions (and each layer's
94// equally many nodes) begins.
95WORKSPACE(int, offset, order[2] + 2);
96offset[0] = 0;
97for (int dd = 0; dd <= order[2]; ++dd)
98{
99 int mm = order[2] - dd;
100 offset[dd + 1] = offset[dd] + (mm + 1) * (mm + 1);
101}
102
103// (1-c)^M for M = 0 .. n, at the point being evaluated.
104WORKSPACE(RealT, wpow, order[2] + 1);
105wpow[0] = 1.;
106for (int pp = 1; pp <= order[2]; ++pp)
107{
108 wpow[pp] = wpow[pp - 1] * ww;
109}
110
111// omega_d(c), the Newton basis on the layer heights c_k = k/n.
112WORKSPACE(RealT, omega, order[2] + 1);
113omega[0] = 1.;
114for (int dd = 1; dd <= order[2]; ++dd)
115{
116 omega[dd] = omega[dd - 1] * (tt - RealT(dd - 1) / RealT(order[2]));
117}
118
119WORKSPACE(RealT, la, order[2] + 1);
120WORKSPACE(RealT, lb, order[2] + 1);
121WORKSPACE(RealT, resamp, (order[2] + 1) * (order[2] + 1));
122WORKSPACE(RealT, rhs, (order[2] + 1) * (order[2] + 1));
123WORKSPACE(RealT, tmp, (order[2] + 1) * (order[2] + 1));
124
125// Back substitution. Layers are solved from the apex down; by the time layer d
126// is reached every layer above it is known, so its own right-hand side is psi
127// minus what those already account for.
128for (int dd = order[2]; dd >= 0; --dd)
129{
130 int mm = order[2] - dd;
131
132 // Layer d's Lagrange polynomials at the point being evaluated, each as the
133 // product prod_{k!=i} (x - x_k)/(x_i - x_k) over its own grid x_k = k/m.
134 for (int ii = 0; ii <= mm; ++ii)
135 {
136 la[ii] = 1.;
137 lb[ii] = 1.;
138 for (int kk = 0; kk <= mm; ++kk)
139 {
140 if (kk == ii)
141 {
142 continue;
143 }
144 RealT xk = RealT(kk) / RealT(mm);
145 RealT scale = RealT(mm) / RealT(ii - kk);
146 la[ii] *= (aa - xk) * scale;
147 lb[ii] *= (bb - xk) * scale;
148 }
149 }
150 for (int jj = 0; jj <= mm; ++jj)
151 {
152 for (int ii = 0; ii <= mm; ++ii)
153 {
154 rhs[jj * (mm + 1) + ii] = la[ii] * lb[jj] * wpow[mm] * omega[dd];
155 }
156 }
157
158 for (int KK = dd + 1; KK <= order[2]; ++KK)
159 {
160 int mK = order[2] - KK;
161
162 // Layer d's Lagrange polynomials resampled onto layer K's coarser grid:
163 // resamp[i * (mK + 1) + i2] = l_i(i2 / mK). Every entry is again a plain
164 // product, so a node the two grids share lands on an exact 0 or 1.
165 for (int ii = 0; ii <= mm; ++ii)
166 {
167 for (int i2 = 0; i2 <= mK; ++i2)
168 {
169 RealT yy = mK > 0 ? RealT(i2) / RealT(mK) : 0.;
170 RealT value = 1.;
171 for (int kk = 0; kk <= mm; ++kk)
172 {
173 if (kk == ii)
174 {
175 continue;
176 }
177 value *= (yy - RealT(kk) / RealT(mm)) * RealT(mm) / RealT(ii - kk);
178 }
179 resamp[ii * (mK + 1) + i2] = value;
180 }
181 }
182
183 // psi_{i,j,d} at layer K's nodes shares the factor omega_d(c_K) (1-c_K)^m.
184 RealT om = 1.;
185 for (int kk = 0; kk < dd; ++kk)
186 {
187 om *= RealT(KK - kk) / RealT(order[2]);
188 }
189 RealT wK = order[2] > 0 ? RealT(mK) / RealT(order[2]) : 1.;
190 RealT wKpow = 1.;
191 for (int pp = 1; pp <= mm; ++pp)
192 {
193 wKpow *= wK;
194 }
195 RealT weight = om * wKpow;
196
197 // Contract layer K's known interpolants against that resampling, one axis
198 // at a time, rather than forming the block itself.
199 for (int ii = 0; ii <= mm; ++ii)
200 {
201 for (int j2 = 0; j2 <= mK; ++j2)
202 {
203 RealT sum = 0.;
204 for (int i2 = 0; i2 <= mK; ++i2)
205 {
206 sum += resamp[ii * (mK + 1) + i2] * basis[offset[KK] + j2 * (mK + 1) + i2];
207 }
208 tmp[ii * (order[2] + 1) + j2] = sum;
209 }
210 }
211 for (int jj = 0; jj <= mm; ++jj)
212 {
213 for (int ii = 0; ii <= mm; ++ii)
214 {
215 RealT sum = 0.;
216 for (int j2 = 0; j2 <= mK; ++j2)
217 {
218 sum += resamp[jj * (mK + 1) + j2] * tmp[ii * (order[2] + 1) + j2];
219 }
220 rhs[jj * (mm + 1) + ii] -= weight * sum;
221 }
222 }
223 }
224
225 // The diagonal block is (1-c_d)^m omega_d(c_d) times the identity, so the
226 // whole of this layer's solve is one division.
227 RealT wd = order[2] > 0 ? RealT(mm) / RealT(order[2]) : 1.;
228 RealT denom = 1.;
229 for (int pp = 1; pp <= mm; ++pp)
230 {
231 denom *= wd;
232 }
233 for (int kk = 0; kk < dd; ++kk)
234 {
235 denom *= RealT(dd - kk) / RealT(order[2]);
236 }
237 for (int jj = 0; jj <= mm; ++jj)
238 {
239 for (int ii = 0; ii <= mm; ++ii)
240 {
241 basis[offset[dd] + jj * (mm + 1) + ii] = rhs[jj * (mm + 1) + ii] / denom;
242 }
243 }
244}
RealT yy
Definition EdgeCnBasis.h:17
WORKSPACE(RealT, ctmp, order[2]+1)
RealT ww
Definition PyrCnBasis.h:44
basis[0]
Definition CellC0Basis.h:1
wpow[0]
Definition PyrCnBasis.h:105
RealT bb
Definition PyrCnBasis.h:91
omega[0]
Definition PyrCnBasis.h:113
offset[0]
Definition PyrCnBasis.h:96
RealT aa
Definition PyrCnBasis.h:90
@ order
Definition vtkX3D.h:441
@ value
Definition vtkX3D.h:221
@ scale
Definition vtkX3D.h:230
@ weight
Definition vtkX3D.h:533