Debian Codegraph @

include/deal.II/base/polynomials_barycentric.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2021 - 2024 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15
16 #ifndef dealii_simplex_barycentric_polynomials_h
17 #define dealii_simplex_barycentric_polynomials_h
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/exceptions.h>
22 #include <deal.II/base/scalar_polynomials_base.h>
23 #include <deal.II/base/table.h>
24
25 #include <limits>
26
27 DEAL_II_NAMESPACE_OPEN
28
29 /**
30 * Polynomial implemented in barycentric coordinates.
31 *
32 * Barycentric coordinates are a coordinate system defined on simplices that
33 * are particularly easy to work with since they express coordinates in the
34 * simplex as convex combinations of the vertices. For example, any point in a
35 * triangle can be written as
36 *
37 * @f[
38 * (x, y) = c_0 (x_0, y_0) + c_1 (x_1, y_1) + c_2 (x_2, y_2).
39 * @f]
40 *
41 * where each value $c_i$ is the relative weight of each vertex (so the
42 * centroid is, in 2d, where each $c_i = 1/3$). Since we only consider convex
43 * combinations we can rewrite this equation as
44 *
45 * @f[
46 * (x, y) = (1 - c_1 - c_2) (x_0, y_0) + c_1 (x_1, y_1) + c_2 (x_2, y_2).
47 * @f]
48 *
49 * This results in three polynomials that are equivalent to $P^1$ in 2d. More
50 * exactly, this class implements a polynomial space defined with the basis,
51 * in 2d, of
52 * @f{align*}{
53 * t_0(x, y) &= 1 - x - y \\
54 * t_1(x, y) &= x \\
55 * t_2(x, y) &= y
56 * @f}
57 * and, in 3d,
58 * @f{align*}{
59 * t_0(x, y) &= 1 - x - y - z \\
60 * t_1(x, y) &= x \\
61 * t_2(x, y) &= y \\
62 * t_2(x, y) &= z
63 * @f}
64 *
65 * which is, in practice, a very convenient basis for defining simplex
66 * polynomials: for example, the fourth basis function of a TRI6 element is
67 *
68 * @f[
69 * 4 * t_1(x, y) * t_2(x, y).
70 * @f]
71 *
72 * Barycentric polynomials in <code>dim</code>-dimensional space have
73 * <code>dim + 1</code> variables in since <code>t_0</code> can be written in
74 * terms of the other monomials.
75 *
76 * Monomials can be conveniently constructed with
77 * BarycentricPolynomial::monomial().
78 *
79 * @ingroup Polynomials
80 */
81 template <int dim, typename Number = double>
82 class BarycentricPolynomial
83 {
84 public:
85 /**
86 * Constructor for the zero polynomial.
87 */
88 BarycentricPolynomial();
89
90 /**
91 * Constructor for a monomial.
92 */
93 BarycentricPolynomial(const TableIndices<dim + 1> &powers,
94 const Number coefficient);
95
96 /**
97 * Return the specified monomial.
98 */
99 static BarycentricPolynomial<dim, Number>
100 monomial(const unsigned int d);
101
102 /**
103 * Print the polynomial to the output stream with lowest-order terms first.
104 * For example, the first P6 basis function is printed as
105 * <code>-1 * t0^1 + 2 * t0^2</code>, where <code>t0</code> is the first
106 * barycentric variable, <code>t1</code> is the second, etc.
107 */
108 void
109 print(std::ostream &out) const;
110
111 /**
112 * Degree of each barycentric polynomial.
113 */
114 TableIndices<dim + 1>
115 degrees() const;
116
117 /**
118 * Unary minus.
119 */
120 BarycentricPolynomial<dim, Number>
121 operator-() const;
122
123 /**
124 * Add a scalar.
125 */
126 template <typename Number2>
127 BarycentricPolynomial<dim, Number>
128 operator+(const Number2 &a) const;
129
130 /**
131 * Subtract a scalar.
132 */
133 template <typename Number2>
134 BarycentricPolynomial<dim, Number>
135 operator-(const Number2 &a) const;
136
137 /**
138 * Multiply by a scalar.
139 */
140 template <typename Number2>
141 BarycentricPolynomial<dim, Number>
142 operator*(const Number2 &a) const;
143
144 /**
145 * Divide by a scalar.
146 */
147 template <typename Number2>
148 BarycentricPolynomial<dim, Number>
149 operator/(const Number2 &a) const;
150
151 /**
152 * Add another barycentric polynomial.
153 */
154 BarycentricPolynomial<dim, Number>
155 operator+(const BarycentricPolynomial<dim, Number> &augend) const;
156
157 /**
158 * Subtract another barycentric polynomial.
159 */
160 BarycentricPolynomial<dim, Number>
161 operator-(const BarycentricPolynomial<dim, Number> &augend) const;
162
163 /**
164 * Multiply by another barycentric polynomial.
165 */
166 BarycentricPolynomial<dim, Number>
167 operator*(const BarycentricPolynomial<dim, Number> &multiplicand) const;
168
169 /**
170 * Differentiate in barycentric coordinates.
171 */
172 BarycentricPolynomial<dim, Number>
173 barycentric_derivative(const unsigned int coordinate) const;
174
175 /**
176 * Differentiate in Cartesian coordinates.
177 */
178 BarycentricPolynomial<dim, Number>
179 derivative(const unsigned int coordinate) const;
180
181 /**
182 * Evaluate the polynomial.
183 */
184 Number
185 value(const Point<dim> &point) const;
186
187 /**
188 * Return an estimate, in bytes, of the memory usage of the object.
189 */
190 std::size_t
191 memory_consumption() const;
192
193 protected:
194 /**
195 * Coefficients of the polynomial. The exponents are the integer indexes.
196 */
197 Table<dim + 1, Number> coefficients;
198
199 /**
200 * Utility function for barycentric polynomials: it is convenient to loop
201 * over all the indices at once in a dimension-independent way, but we also
202 * need to access the actual indices of the underlying Table object. This
203 * utility function converts an integral index into the equivalent
204 * TableIndices array (which are also the implicitly stored polynomial
205 * exponents).
206 */
207 static TableIndices<dim + 1>
208 index_to_indices(const std::size_t &index,
209 const TableIndices<dim + 1> &extents);
210 };
211
212 /**
213 * Scalar polynomial space based on barycentric polynomials.
214 */
215 template <int dim>
216 class BarycentricPolynomials : public ScalarPolynomialsBase<dim>
217 {
218 public:
219 /**
220 * Alias for polynomial type.
221 */
222 using PolyType = BarycentricPolynomial<dim>;
223
224 /**
225 * Alias for polynomial gradient type.
226 */
227 using GradType = std::array<PolyType, dim>;
228
229 /**
230 * Alias for polynomial hessian type.
231 */
232 using HessianType = std::array<GradType, dim>;
233
234 /**
235 * Alias for polynomial third derivatives type.
236 */
237 using ThirdDerivativesType = std::array<HessianType, dim>;
238
239 /**
240 * Alias for polynomial fourth derivatives type.
241 */
242 using FourthDerivativesType = std::array<ThirdDerivativesType, dim>;
243
244 /**
245 * Make the dimension available to the outside.
246 */
247 static constexpr unsigned int dimension = dim;
248
249 /**
250 * Get the standard Lagrange basis for a specified degree.
251 */
252 static BarycentricPolynomials<dim>
253 get_fe_p_basis(const unsigned int degree);
254
255 /**
256 * Constructor taking the polynomial @p degree as input.
257 */
258 BarycentricPolynomials(
259 const std::vector<BarycentricPolynomial<dim>> &polynomials);
260
261 /**
262 * Access operator.
263 */
264 const BarycentricPolynomial<dim> &
265 operator[](const std::size_t i) const;
266
267 /**
268 * @copydoc ScalarPolynomialsBase::evaluate()
269 */
270 void
271 evaluate(const Point<dim> &unit_point,
272 std::vector<double> &values,
273 std::vector<Tensor<1, dim>> &grads,
274 std::vector<Tensor<2, dim>> &grad_grads,
275 std::vector<Tensor<3, dim>> &third_derivatives,
276 std::vector<Tensor<4, dim>> &fourth_derivatives) const override;
277
278 /**
279 * @copydoc ScalarPolynomialsBase::compute_value()
280 */
281 double
282 compute_value(const unsigned int i, const Point<dim> &p) const override;
283
284 /**
285 * @copydoc ScalarPolynomialsBase::compute_1st_derivative()
286 */
287 Tensor<1, dim>
288 compute_1st_derivative(const unsigned int i,
289 const Point<dim> &p) const override;
290
291 /**
292 * @copydoc ScalarPolynomialsBase::compute_2nd_derivative()
293 */
294 Tensor<2, dim>
295 compute_2nd_derivative(const unsigned int i,
296 const Point<dim> &p) const override;
297
298 /**
299 * @copydoc ScalarPolynomialsBase::compute_3rd_derivative()
300 */
301 Tensor<3, dim>
302 compute_3rd_derivative(const unsigned int i,
303 const Point<dim> &p) const override;
304
305 /**
306 * @copydoc ScalarPolynomialsBase::compute_4th_derivative()
307 */
308 Tensor<4, dim>
309 compute_4th_derivative(const unsigned int i,
310 const Point<dim> &p) const override;
311
312 /**
313 * @copydoc ScalarPolynomialsBase::compute_grad()
314 */
315 Tensor<1, dim>
316 compute_grad(const unsigned int i, const Point<dim> &p) const override;
317
318 /**
319 * @copydoc ScalarPolynomialsBase::compute_grad_grad()
320 */
321 Tensor<2, dim>
322 compute_grad_grad(const unsigned int i, const Point<dim> &p) const override;
323
324 /**
325 * @copydoc ScalarPolynomialsBase::memory_consumption()
326 */
327 virtual std::size_t
328 memory_consumption() const override;
329
330 /**
331 * @copydoc ScalarPolynomialsBase::name()
332 */
333 std::string
334 name() const override;
335
336 /**
337 * @copydoc ScalarPolynomialsBase::clone()
338 */
339 virtual std::unique_ptr<ScalarPolynomialsBase<dim>>
340 clone() const override;
341
342 protected:
343 std::vector<PolyType> polys;
344 std::vector<GradType> poly_grads;
345 std::vector<HessianType> poly_hessians;
346 std::vector<ThirdDerivativesType> poly_third_derivatives;
347 std::vector<FourthDerivativesType> poly_fourth_derivatives;
348 };
349
350 // non-member template functions for algebra
351
352 /**
353 * Multiply a BarycentricPolynomial by a constant.
354 */
355 template <int dim, typename Number1, typename Number2>
356 BarycentricPolynomial<dim, Number1>
357 operator*(const Number2 &a, const BarycentricPolynomial<dim, Number1> &bp)
358 {
359 return bp * Number1(a);
360 }
361
362 /**
363 * Add a constant to a BarycentricPolynomial.
364 */
365 template <int dim, typename Number1, typename Number2>
366 BarycentricPolynomial<dim, Number1>
367 operator+(const Number2 &a, const BarycentricPolynomial<dim, Number1> &bp)
368 {
369 return bp + Number1(a);
370 }
371
372 /**
373 * Subtract a BarycentricPolynomial from a constant.
374 */
375 template <int dim, typename Number1, typename Number2>
376 BarycentricPolynomial<dim, Number1>
377 operator-(const Number2 &a, const BarycentricPolynomial<dim, Number1> &bp)
378 {
379 return bp - Number1(a);
380 }
381
382 /**
383 * Write a BarycentricPolynomial to the provided output stream.
384 */
385 template <int dim, typename Number>
386 std::ostream &
387 operator<<(std::ostream &out, const BarycentricPolynomial<dim, Number> &bp)
388 {
389 bp.print(out);
390 return out;
391 }
392
393 // Template function definitions
394
395 // BarycentricPolynomial:
396 template <int dim, typename Number>
397 BarycentricPolynomial<dim, Number>::BarycentricPolynomial()
398 {
399 TableIndices<dim + 1> extents;
400 for (unsigned int d = 0; d < dim + 1; ++d)
401 extents[d] = 1;
402 coefficients.reinit(extents);
403
404 coefficients(TableIndices<dim + 1>{}) = Number();
405 }
406
407
408
409 template <int dim, typename Number>
410 BarycentricPolynomial<dim, Number>::BarycentricPolynomial(
411 const TableIndices<dim + 1> &powers,
412 const Number coefficient)
413 {
414 TableIndices<dim + 1> extents;
415 for (unsigned int d = 0; d < dim + 1; ++d)
416 extents[d] = powers[d] + 1;
417 coefficients.reinit(extents);
418
419 coefficients(powers) = coefficient;
420 }
421
422
423
424 template <int dim, typename Number>
425 BarycentricPolynomial<dim, Number>
426 BarycentricPolynomial<dim, Number>::monomial(const unsigned int d)
427 {
428 AssertIndexRange(d, dim + 1);
429 TableIndices<dim + 1> indices;
430 indices[d] = 1;
431 return BarycentricPolynomial<dim, Number>(indices, Number(1));
432 }
433
434
435
436 template <int dim, typename Number>
437 void
438 BarycentricPolynomial<dim, Number>::print(std::ostream &out) const
439 {
440 const auto &coeffs = this->coefficients;
441 auto first = index_to_indices(0, coeffs.size());
442 bool print_plus = false;
443 if (coeffs(first) != Number())
444 {
445 out << coeffs(first);
446 print_plus = true;
447 }
448 for (std::size_t i = 1; i < coeffs.n_elements(); ++i)
449 {
450 const auto indices = index_to_indices(i, coeffs.size());
451 if (coeffs(indices) == Number())
452 continue;
453 if (print_plus)
454 out << " + ";
455 out << coeffs(indices);
456 for (unsigned int d = 0; d < dim + 1; ++d)
457 {
458 if (indices[d] != 0)
459 out << " * t" << d << '^' << indices[d];
460 }
461 print_plus = true;
462 }
463
464 if (!print_plus)
465 out << Number();
466 }
467
468
469
470 template <int dim, typename Number>
471 TableIndices<dim + 1>
472 BarycentricPolynomial<dim, Number>::degrees() const
473 {
474 auto deg = coefficients.size();
475 for (unsigned int d = 0; d < dim + 1; ++d)
476 deg[d] -= 1;
477 return deg;
478 }
479
480
481
482 template <int dim, typename Number>
483 BarycentricPolynomial<dim, Number>
484 BarycentricPolynomial<dim, Number>::operator-() const
485 {
486 return *this * Number(-1);
487 }
488
489
490
491 template <int dim, typename Number>
492 template <typename Number2>
493 BarycentricPolynomial<dim, Number>
494 BarycentricPolynomial<dim, Number>::operator+(const Number2 &a) const
495 {
496 BarycentricPolynomial<dim, Number> result(*this);
497 result.coefficients(index_to_indices(0, result.coefficients.size())) += a;
498
499 return result;
500 }
501
502
503
504 template <int dim, typename Number>
505 template <typename Number2>
506 BarycentricPolynomial<dim, Number>
507 BarycentricPolynomial<dim, Number>::operator-(const Number2 &a) const
508 {
509 return *this + (-a);
510 }
511
512
513
514 template <int dim, typename Number>
515 template <typename Number2>
516 BarycentricPolynomial<dim, Number>
517 BarycentricPolynomial<dim, Number>::operator*(const Number2 &a) const
518 {
519 if (a == Number2())
520 {
521 return BarycentricPolynomial<dim, Number>();
522 }
523
524 BarycentricPolynomial<dim, Number> result(*this);
525 for (std::size_t i = 0; i < result.coefficients.n_elements(); ++i)
526 {
527 const auto index = index_to_indices(i, result.coefficients.size());
528 result.coefficients(index) *= a;
529 }
530
531 return result;
532 }
533
534
535
536 template <int dim, typename Number>
537 template <typename Number2>
538 BarycentricPolynomial<dim, Number>
539 BarycentricPolynomial<dim, Number>::operator/(const Number2 &a) const
540 {
541 Assert(a != Number2(), ExcDivideByZero());
542 return *this * (Number(1) / Number(a));
543 }
544
545
546
547 template <int dim, typename Number>
548 BarycentricPolynomial<dim, Number>
549 BarycentricPolynomial<dim, Number>::operator+(
550 const BarycentricPolynomial<dim, Number> &augend) const
551 {
552 TableIndices<dim + 1> deg;
553 for (unsigned int d = 0; d < dim + 1; ++d)
554 {
555 deg[d] = std::max(degrees()[d], augend.degrees()[d]);
556 }
557
558 BarycentricPolynomial<dim, Number> result(deg, Number());
559
560 auto add_coefficients = [&](const Table<dim + 1, Number> &in) {
561 for (std::size_t i = 0; i < in.n_elements(); ++i)
562 {
563 const auto index = index_to_indices(i, in.size());
564 result.coefficients(index) += in(index);
565 }
566 };
567
568 add_coefficients(this->coefficients);
569 add_coefficients(augend.coefficients);
570 return result;
571 }
572
573
574
575 template <int dim, typename Number>
576 BarycentricPolynomial<dim, Number>
577 BarycentricPolynomial<dim, Number>::operator-(
578 const BarycentricPolynomial<dim, Number> &augend) const
579 {
580 return *this + (-augend);
581 }
582
583
584
585 template <int dim, typename Number>
586 BarycentricPolynomial<dim, Number>
587 BarycentricPolynomial<dim, Number>::operator*(
588 const BarycentricPolynomial<dim, Number> &multiplicand) const
589 {
590 TableIndices<dim + 1> deg;
591 for (unsigned int d = 0; d < dim + 1; ++d)
592 {
593 deg[d] = multiplicand.degrees()[d] + degrees()[d];
594 }
595
596 BarycentricPolynomial<dim, Number> result(deg, Number());
597
598 const auto &coef_1 = this->coefficients;
599 const auto &coef_2 = multiplicand.coefficients;
600 auto &coef_out = result.coefficients;
601
602 for (std::size_t i1 = 0; i1 < coef_1.n_elements(); ++i1)
603 {
604 const auto index_1 = index_to_indices(i1, coef_1.size());
605 for (std::size_t i2 = 0; i2 < coef_2.n_elements(); ++i2)
606 {
607 const auto index_2 = index_to_indices(i2, coef_2.size());
608
609 TableIndices<dim + 1> index_out;
610 for (unsigned int d = 0; d < dim + 1; ++d)
611 index_out[d] = index_1[d] + index_2[d];
612 coef_out(index_out) += coef_1(index_1) * coef_2(index_2);
613 }
614 }
615
616 return result;
617 }
618
619
620
621 template <int dim, typename Number>
622 BarycentricPolynomial<dim, Number>
623 BarycentricPolynomial<dim, Number>::barycentric_derivative(
624 const unsigned int coordinate) const
625 {
626 AssertIndexRange(coordinate, dim + 1);
627
628 if (degrees()[coordinate] == 0)
629 return BarycentricPolynomial<dim, Number>();
630
631 auto deg = degrees();
632 deg[coordinate] -= 1;
633 BarycentricPolynomial<dim, Number> result(deg,
634 std::numeric_limits<Number>::max());
635 const auto &coeffs_in = coefficients;
636 auto &coeffs_out = result.coefficients;
637 for (std::size_t i = 0; i < coeffs_out.n_elements(); ++i)
638 {
639 const auto out_index = index_to_indices(i, coeffs_out.size());
640 auto input_index = out_index;
641 input_index[coordinate] += 1;
642
643 coeffs_out(out_index) = coeffs_in(input_index) * input_index[coordinate];
644 }
645
646 return result;
647 }
648
649
650
651 template <int dim, typename Number>
652 BarycentricPolynomial<dim, Number>
653 BarycentricPolynomial<dim, Number>::derivative(
654 const unsigned int coordinate) const
655 {
656 AssertIndexRange(coordinate, dim);
657 return -barycentric_derivative(0) + barycentric_derivative(coordinate + 1);
658 }
659
660
661
662 template <int dim, typename Number>
663 Number
664 BarycentricPolynomial<dim, Number>::value(const Point<dim> &point) const
665 {
666 // TODO: this is probably not numerically stable for higher order.
667 // We really need some version of Horner's method.
668 Number result = {};
669
670 // Begin by converting point (which is in Cartesian coordinates) to
671 // barycentric coordinates:
672 std::array<Number, dim + 1> b_point;
673 b_point[0] = 1.0;
674 for (unsigned int d = 0; d < dim; ++d)
675 {
676 b_point[0] -= point[d];
677 b_point[d + 1] = point[d];
678 }
679
680 // Now evaluate the polynomial at the computed barycentric point:
681 for (std::size_t i = 0; i < coefficients.n_elements(); ++i)
682 {
683 const auto indices = index_to_indices(i, coefficients.size());
684 const auto coef = coefficients(indices);
685 if (coef == Number())
686 continue;
687
688 auto temp = Number(1);
689 for (unsigned int d = 0; d < dim + 1; ++d)
690 temp *= Utilities::pow(b_point[d], indices[d]);
691 result += coef * temp;
692 }
693
694 return result;
695 }
696
697
698
699 template <int dim, typename Number>
700 std::size_t
701 BarycentricPolynomial<dim, Number>::memory_consumption() const
702 {
703 return coefficients.memory_consumption();
704 }
705
706
707
708 template <int dim, typename Number>
709 TableIndices<dim + 1>
710 BarycentricPolynomial<dim, Number>::index_to_indices(
711 const std::size_t &index,
712 const TableIndices<dim + 1> &extents)
713 {
714 TableIndices<dim + 1> result;
715 auto temp = index;
716
717 for (unsigned int n = 0; n < dim + 1; ++n)
718 {
719 std::size_t slice_size = 1;
720 for (unsigned int n2 = n + 1; n2 < dim + 1; ++n2)
721 slice_size *= extents[n2];
722 result[n] = temp / slice_size;
723 temp %= slice_size;
724 }
725 return result;
726 }
727
728
729
730 template <int dim>
731 const BarycentricPolynomial<dim> &
732 BarycentricPolynomials<dim>::operator[](const std::size_t i) const
733 {
734 AssertIndexRange(i, polys.size());
735 return polys[i];
736 }
737
738 DEAL_II_NAMESPACE_CLOSE
739
740 #endif