// ------------------------------------------------------------------------ // // SPDX-License-Identifier: LGPL-2.1-or-later // Copyright (C) 2021 - 2024 by the deal.II authors // // This file is part of the deal.II library. // // Part of the source code is dual licensed under Apache-2.0 WITH // LLVM-exception OR LGPL-2.1-or-later. Detailed license information // governing the source code and code contributions can be found in // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II. // // ------------------------------------------------------------------------ #ifndef dealii_simplex_barycentric_polynomials_h #define dealii_simplex_barycentric_polynomials_h #include #include #include #include #include DEAL_II_NAMESPACE_OPEN /** * Polynomial implemented in barycentric coordinates. * * Barycentric coordinates are a coordinate system defined on simplices that * are particularly easy to work with since they express coordinates in the * simplex as convex combinations of the vertices. For example, any point in a * triangle can be written as * * @f[ * (x, y) = c_0 (x_0, y_0) + c_1 (x_1, y_1) + c_2 (x_2, y_2). * @f] * * where each value $c_i$ is the relative weight of each vertex (so the * centroid is, in 2d, where each $c_i = 1/3$). Since we only consider convex * combinations we can rewrite this equation as * * @f[ * (x, y) = (1 - c_1 - c_2) (x_0, y_0) + c_1 (x_1, y_1) + c_2 (x_2, y_2). * @f] * * This results in three polynomials that are equivalent to $P^1$ in 2d. More * exactly, this class implements a polynomial space defined with the basis, * in 2d, of * @f{align*}{ * t_0(x, y) &= 1 - x - y \\ * t_1(x, y) &= x \\ * t_2(x, y) &= y * @f} * and, in 3d, * @f{align*}{ * t_0(x, y) &= 1 - x - y - z \\ * t_1(x, y) &= x \\ * t_2(x, y) &= y \\ * t_2(x, y) &= z * @f} * * which is, in practice, a very convenient basis for defining simplex * polynomials: for example, the fourth basis function of a TRI6 element is * * @f[ * 4 * t_1(x, y) * t_2(x, y). * @f] * * Barycentric polynomials in dim-dimensional space have * dim + 1 variables in since t_0 can be written in * terms of the other monomials. * * Monomials can be conveniently constructed with * BarycentricPolynomial::monomial(). * * @ingroup Polynomials */ template class BarycentricPolynomial { public: /** * Constructor for the zero polynomial. */ BarycentricPolynomial(); /** * Constructor for a monomial. */ BarycentricPolynomial(const TableIndices &powers, const Number coefficient); /** * Return the specified monomial. */ static BarycentricPolynomial monomial(const unsigned int d); /** * Print the polynomial to the output stream with lowest-order terms first. * For example, the first P6 basis function is printed as * -1 * t0^1 + 2 * t0^2, where t0 is the first * barycentric variable, t1 is the second, etc. */ void print(std::ostream &out) const; /** * Degree of each barycentric polynomial. */ TableIndices degrees() const; /** * Unary minus. */ BarycentricPolynomial operator-() const; /** * Add a scalar. */ template BarycentricPolynomial operator+(const Number2 &a) const; /** * Subtract a scalar. */ template BarycentricPolynomial operator-(const Number2 &a) const; /** * Multiply by a scalar. */ template BarycentricPolynomial operator*(const Number2 &a) const; /** * Divide by a scalar. */ template BarycentricPolynomial operator/(const Number2 &a) const; /** * Add another barycentric polynomial. */ BarycentricPolynomial operator+(const BarycentricPolynomial &augend) const; /** * Subtract another barycentric polynomial. */ BarycentricPolynomial operator-(const BarycentricPolynomial &augend) const; /** * Multiply by another barycentric polynomial. */ BarycentricPolynomial operator*(const BarycentricPolynomial &multiplicand) const; /** * Differentiate in barycentric coordinates. */ BarycentricPolynomial barycentric_derivative(const unsigned int coordinate) const; /** * Differentiate in Cartesian coordinates. */ BarycentricPolynomial derivative(const unsigned int coordinate) const; /** * Evaluate the polynomial. */ Number value(const Point &point) const; /** * Return an estimate, in bytes, of the memory usage of the object. */ std::size_t memory_consumption() const; protected: /** * Coefficients of the polynomial. The exponents are the integer indexes. */ Table coefficients; /** * Utility function for barycentric polynomials: it is convenient to loop * over all the indices at once in a dimension-independent way, but we also * need to access the actual indices of the underlying Table object. This * utility function converts an integral index into the equivalent * TableIndices array (which are also the implicitly stored polynomial * exponents). */ static TableIndices index_to_indices(const std::size_t &index, const TableIndices &extents); }; /** * Scalar polynomial space based on barycentric polynomials. */ template class BarycentricPolynomials : public ScalarPolynomialsBase { public: /** * Alias for polynomial type. */ using PolyType = BarycentricPolynomial; /** * Alias for polynomial gradient type. */ using GradType = std::array; /** * Alias for polynomial hessian type. */ using HessianType = std::array; /** * Alias for polynomial third derivatives type. */ using ThirdDerivativesType = std::array; /** * Alias for polynomial fourth derivatives type. */ using FourthDerivativesType = std::array; /** * Make the dimension available to the outside. */ static constexpr unsigned int dimension = dim; /** * Get the standard Lagrange basis for a specified degree. */ static BarycentricPolynomials get_fe_p_basis(const unsigned int degree); /** * Constructor taking the polynomial @p degree as input. */ BarycentricPolynomials( const std::vector> &polynomials); /** * Access operator. */ const BarycentricPolynomial & operator[](const std::size_t i) const; /** * @copydoc ScalarPolynomialsBase::evaluate() */ void evaluate(const Point &unit_point, std::vector &values, std::vector> &grads, std::vector> &grad_grads, std::vector> &third_derivatives, std::vector> &fourth_derivatives) const override; /** * @copydoc ScalarPolynomialsBase::compute_value() */ double compute_value(const unsigned int i, const Point &p) const override; /** * @copydoc ScalarPolynomialsBase::compute_1st_derivative() */ Tensor<1, dim> compute_1st_derivative(const unsigned int i, const Point &p) const override; /** * @copydoc ScalarPolynomialsBase::compute_2nd_derivative() */ Tensor<2, dim> compute_2nd_derivative(const unsigned int i, const Point &p) const override; /** * @copydoc ScalarPolynomialsBase::compute_3rd_derivative() */ Tensor<3, dim> compute_3rd_derivative(const unsigned int i, const Point &p) const override; /** * @copydoc ScalarPolynomialsBase::compute_4th_derivative() */ Tensor<4, dim> compute_4th_derivative(const unsigned int i, const Point &p) const override; /** * @copydoc ScalarPolynomialsBase::compute_grad() */ Tensor<1, dim> compute_grad(const unsigned int i, const Point &p) const override; /** * @copydoc ScalarPolynomialsBase::compute_grad_grad() */ Tensor<2, dim> compute_grad_grad(const unsigned int i, const Point &p) const override; /** * @copydoc ScalarPolynomialsBase::memory_consumption() */ virtual std::size_t memory_consumption() const override; /** * @copydoc ScalarPolynomialsBase::name() */ std::string name() const override; /** * @copydoc ScalarPolynomialsBase::clone() */ virtual std::unique_ptr> clone() const override; protected: std::vector polys; std::vector poly_grads; std::vector poly_hessians; std::vector poly_third_derivatives; std::vector poly_fourth_derivatives; }; // non-member template functions for algebra /** * Multiply a BarycentricPolynomial by a constant. */ template BarycentricPolynomial operator*(const Number2 &a, const BarycentricPolynomial &bp) { return bp * Number1(a); } /** * Add a constant to a BarycentricPolynomial. */ template BarycentricPolynomial operator+(const Number2 &a, const BarycentricPolynomial &bp) { return bp + Number1(a); } /** * Subtract a BarycentricPolynomial from a constant. */ template BarycentricPolynomial operator-(const Number2 &a, const BarycentricPolynomial &bp) { return bp - Number1(a); } /** * Write a BarycentricPolynomial to the provided output stream. */ template std::ostream & operator<<(std::ostream &out, const BarycentricPolynomial &bp) { bp.print(out); return out; } // Template function definitions // BarycentricPolynomial: template BarycentricPolynomial::BarycentricPolynomial() { TableIndices extents; for (unsigned int d = 0; d < dim + 1; ++d) extents[d] = 1; coefficients.reinit(extents); coefficients(TableIndices{}) = Number(); } template BarycentricPolynomial::BarycentricPolynomial( const TableIndices &powers, const Number coefficient) { TableIndices extents; for (unsigned int d = 0; d < dim + 1; ++d) extents[d] = powers[d] + 1; coefficients.reinit(extents); coefficients(powers) = coefficient; } template BarycentricPolynomial BarycentricPolynomial::monomial(const unsigned int d) { AssertIndexRange(d, dim + 1); TableIndices indices; indices[d] = 1; return BarycentricPolynomial(indices, Number(1)); } template void BarycentricPolynomial::print(std::ostream &out) const { const auto &coeffs = this->coefficients; auto first = index_to_indices(0, coeffs.size()); bool print_plus = false; if (coeffs(first) != Number()) { out << coeffs(first); print_plus = true; } for (std::size_t i = 1; i < coeffs.n_elements(); ++i) { const auto indices = index_to_indices(i, coeffs.size()); if (coeffs(indices) == Number()) continue; if (print_plus) out << " + "; out << coeffs(indices); for (unsigned int d = 0; d < dim + 1; ++d) { if (indices[d] != 0) out << " * t" << d << '^' << indices[d]; } print_plus = true; } if (!print_plus) out << Number(); } template TableIndices BarycentricPolynomial::degrees() const { auto deg = coefficients.size(); for (unsigned int d = 0; d < dim + 1; ++d) deg[d] -= 1; return deg; } template BarycentricPolynomial BarycentricPolynomial::operator-() const { return *this * Number(-1); } template template BarycentricPolynomial BarycentricPolynomial::operator+(const Number2 &a) const { BarycentricPolynomial result(*this); result.coefficients(index_to_indices(0, result.coefficients.size())) += a; return result; } template template BarycentricPolynomial BarycentricPolynomial::operator-(const Number2 &a) const { return *this + (-a); } template template BarycentricPolynomial BarycentricPolynomial::operator*(const Number2 &a) const { if (a == Number2()) { return BarycentricPolynomial(); } BarycentricPolynomial result(*this); for (std::size_t i = 0; i < result.coefficients.n_elements(); ++i) { const auto index = index_to_indices(i, result.coefficients.size()); result.coefficients(index) *= a; } return result; } template template BarycentricPolynomial BarycentricPolynomial::operator/(const Number2 &a) const { Assert(a != Number2(), ExcDivideByZero()); return *this * (Number(1) / Number(a)); } template BarycentricPolynomial BarycentricPolynomial::operator+( const BarycentricPolynomial &augend) const { TableIndices deg; for (unsigned int d = 0; d < dim + 1; ++d) { deg[d] = std::max(degrees()[d], augend.degrees()[d]); } BarycentricPolynomial result(deg, Number()); auto add_coefficients = [&](const Table &in) { for (std::size_t i = 0; i < in.n_elements(); ++i) { const auto index = index_to_indices(i, in.size()); result.coefficients(index) += in(index); } }; add_coefficients(this->coefficients); add_coefficients(augend.coefficients); return result; } template BarycentricPolynomial BarycentricPolynomial::operator-( const BarycentricPolynomial &augend) const { return *this + (-augend); } template BarycentricPolynomial BarycentricPolynomial::operator*( const BarycentricPolynomial &multiplicand) const { TableIndices deg; for (unsigned int d = 0; d < dim + 1; ++d) { deg[d] = multiplicand.degrees()[d] + degrees()[d]; } BarycentricPolynomial result(deg, Number()); const auto &coef_1 = this->coefficients; const auto &coef_2 = multiplicand.coefficients; auto &coef_out = result.coefficients; for (std::size_t i1 = 0; i1 < coef_1.n_elements(); ++i1) { const auto index_1 = index_to_indices(i1, coef_1.size()); for (std::size_t i2 = 0; i2 < coef_2.n_elements(); ++i2) { const auto index_2 = index_to_indices(i2, coef_2.size()); TableIndices index_out; for (unsigned int d = 0; d < dim + 1; ++d) index_out[d] = index_1[d] + index_2[d]; coef_out(index_out) += coef_1(index_1) * coef_2(index_2); } } return result; } template BarycentricPolynomial BarycentricPolynomial::barycentric_derivative( const unsigned int coordinate) const { AssertIndexRange(coordinate, dim + 1); if (degrees()[coordinate] == 0) return BarycentricPolynomial(); auto deg = degrees(); deg[coordinate] -= 1; BarycentricPolynomial result(deg, std::numeric_limits::max()); const auto &coeffs_in = coefficients; auto &coeffs_out = result.coefficients; for (std::size_t i = 0; i < coeffs_out.n_elements(); ++i) { const auto out_index = index_to_indices(i, coeffs_out.size()); auto input_index = out_index; input_index[coordinate] += 1; coeffs_out(out_index) = coeffs_in(input_index) * input_index[coordinate]; } return result; } template BarycentricPolynomial BarycentricPolynomial::derivative( const unsigned int coordinate) const { AssertIndexRange(coordinate, dim); return -barycentric_derivative(0) + barycentric_derivative(coordinate + 1); } template Number BarycentricPolynomial::value(const Point &point) const { // TODO: this is probably not numerically stable for higher order. // We really need some version of Horner's method. Number result = {}; // Begin by converting point (which is in Cartesian coordinates) to // barycentric coordinates: std::array b_point; b_point[0] = 1.0; for (unsigned int d = 0; d < dim; ++d) { b_point[0] -= point[d]; b_point[d + 1] = point[d]; } // Now evaluate the polynomial at the computed barycentric point: for (std::size_t i = 0; i < coefficients.n_elements(); ++i) { const auto indices = index_to_indices(i, coefficients.size()); const auto coef = coefficients(indices); if (coef == Number()) continue; auto temp = Number(1); for (unsigned int d = 0; d < dim + 1; ++d) temp *= Utilities::pow(b_point[d], indices[d]); result += coef * temp; } return result; } template std::size_t BarycentricPolynomial::memory_consumption() const { return coefficients.memory_consumption(); } template TableIndices BarycentricPolynomial::index_to_indices( const std::size_t &index, const TableIndices &extents) { TableIndices result; auto temp = index; for (unsigned int n = 0; n < dim + 1; ++n) { std::size_t slice_size = 1; for (unsigned int n2 = n + 1; n2 < dim + 1; ++n2) slice_size *= extents[n2]; result[n] = temp / slice_size; temp %= slice_size; } return result; } template const BarycentricPolynomial & BarycentricPolynomials::operator[](const std::size_t i) const { AssertIndexRange(i, polys.size()); return polys[i]; } DEAL_II_NAMESPACE_CLOSE #endif