| 1 |
// ------------------------------------------------------------------------ |
| 2 |
// |
| 3 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 4 |
// Copyright (C) 2000 - 2025 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 |
#ifndef dealii_polynomial_h |
| 16 |
#define dealii_polynomial_h |
| 17 |
|
| 18 |
|
| 19 |
|
| 20 |
#include <deal.II/base/config.h> |
| 21 |
|
| 22 |
#include <deal.II/base/enable_observer_pointer.h> |
| 23 |
#include <deal.II/base/exceptions.h> |
| 24 |
#include <deal.II/base/numbers.h> |
| 25 |
#include <deal.II/base/point.h> |
| 26 |
#include <deal.II/base/types.h> |
| 27 |
|
| 28 |
#include <array> |
| 29 |
#include <limits> |
| 30 |
#include <memory> |
| 31 |
#include <shared_mutex> |
| 32 |
#include <vector> |
| 33 |
|
| 34 |
DEAL_II_NAMESPACE_OPEN |
| 35 |
|
| 36 |
/** |
| 37 |
* @addtogroup Polynomials |
| 38 |
* @{ |
| 39 |
*/ |
| 40 |
|
| 41 |
/** |
| 42 |
* A namespace in which classes relating to the description of 1d polynomial |
| 43 |
* spaces are declared. |
| 44 |
*/ |
| 45 |
namespace Polynomials |
| 46 |
{ |
| 47 |
/** |
| 48 |
* Base class for all 1d polynomials. A polynomial is represented in this |
| 49 |
* class by its coefficients, which are set through the constructor or by |
| 50 |
* derived classes. |
| 51 |
* |
| 52 |
* There are two paths for evaluation of polynomials. One is based on the |
| 53 |
* coefficients which are evaluated through the Horner scheme which is a |
| 54 |
* robust general-purpose scheme. An alternative and more stable evaluation |
| 55 |
* of high-degree polynomials with roots in the unit interval is provided by |
| 56 |
* a product in terms of the roots. This form is available for special |
| 57 |
* polynomials such as Lagrange polynomials or Legendre polynomials and used |
| 58 |
* with the respective constructor. To obtain this more stable evaluation |
| 59 |
* form, the constructor with the roots in form of a Lagrange polynomial |
| 60 |
* must be used. In case a manipulation is done that changes the roots, the |
| 61 |
* representation is switched to the coefficient form. |
| 62 |
* |
| 63 |
* This class is a typical example of a possible template argument for the |
| 64 |
* TensorProductPolynomials class. |
| 65 |
*/ |
| 66 |
template <typename number> |
| 67 |
class Polynomial : public EnableObserverPointer |
| 68 |
{ |
| 69 |
public: |
| 70 |
/** |
| 71 |
* Constructor. The coefficients of the polynomial are passed as |
| 72 |
* arguments, and denote the polynomial $\sum_i a[i] x^i$, i.e. the first |
| 73 |
* element of the array denotes the constant term, the second the linear |
| 74 |
* one, and so on. The degree of the polynomial represented by this object |
| 75 |
* is thus the number of elements in the <tt>coefficient</tt> array minus |
| 76 |
* one. |
| 77 |
*/ |
| 78 |
Polynomial(const std::vector<number> &coefficients); |
| 79 |
|
| 80 |
/** |
| 81 |
* Constructor creating a zero polynomial of degree @p n. |
| 82 |
*/ |
| 83 |
Polynomial(const unsigned int n); |
| 84 |
|
| 85 |
/** |
| 86 |
* Constructor for a Lagrange polynomial and its point of evaluation. The |
| 87 |
* idea is to construct $\prod_{i\neq j} \frac{x-x_i}{x_j-x_i}$, where j |
| 88 |
* is the evaluation point specified as argument and the support points |
| 89 |
* contain all points (including x_j, which will internally not be |
| 90 |
* stored). |
| 91 |
*/ |
| 92 |
Polynomial(const std::vector<Point<1>> &lagrange_support_points, |
| 93 |
const unsigned int evaluation_point); |
| 94 |
|
| 95 |
/** |
| 96 |
* Default constructor creating an illegal object. |
| 97 |
*/ |
| 98 |
Polynomial(); |
| 99 |
|
| 100 |
/** |
| 101 |
* Return the value of this polynomial at the given point. |
| 102 |
* |
| 103 |
* This function uses the most numerically stable evaluation |
| 104 |
* algorithm for the provided form of the polynomial. If the |
| 105 |
* polynomial is in the product form of roots, the evaluation is |
| 106 |
* based on products of the form (x - x_i), whereas the Horner |
| 107 |
* scheme is used for polynomials in the coefficient form. |
| 108 |
*/ |
| 109 |
number |
| 110 |
value(const number x) const; |
| 111 |
|
| 112 |
/** |
| 113 |
* Return the values and the derivatives of the Polynomial at point |
| 114 |
* <tt>x</tt>. <tt>values[i], i=0,...,values.size()-1</tt> includes the |
| 115 |
* <tt>i</tt>th derivative. The number of derivatives to be computed is |
| 116 |
* thus determined by the size of the array passed. |
| 117 |
* |
| 118 |
* This function uses the Horner scheme for numerical stability of the |
| 119 |
* evaluation for polynomials in the coefficient form or the product of |
| 120 |
* terms involving the roots if that representation is used. |
| 121 |
*/ |
| 122 |
void |
| 123 |
value(const number x, std::vector<number> &values) const; |
| 124 |
|
| 125 |
/** |
| 126 |
* Return the values and the derivatives of the Polynomial at point |
| 127 |
* <tt>x</tt>. <tt>values[i], i=0,...,n_derivatives</tt> includes the |
| 128 |
* <tt>i</tt>th derivative. The number of derivatives to be computed is |
| 129 |
* determined by @p n_derivatives and @p values has to provide sufficient |
| 130 |
* space for @p n_derivatives + 1 values. |
| 131 |
* |
| 132 |
* This function uses the most numerically stable evaluation |
| 133 |
* algorithm for the provided form of the polynomial. If the |
| 134 |
* polynomial is in the product form of roots, the evaluation is |
| 135 |
* based on products of the form (x - x_i), whereas the Horner |
| 136 |
* scheme is used for polynomials in the coefficient form. |
| 137 |
* |
| 138 |
* The template type `Number2` must implement arithmetic |
| 139 |
* operations such as additions or multiplication with the type |
| 140 |
* `number` of the polynomial, and must be convertible from |
| 141 |
* `number` by `operator=`. |
| 142 |
*/ |
| 143 |
template <typename Number2> |
| 144 |
void |
| 145 |
value(const Number2 x, |
| 146 |
const unsigned int n_derivatives, |
| 147 |
Number2 *values) const; |
| 148 |
|
| 149 |
/** |
| 150 |
* Similar to the function above, but evaluate the polynomials on several |
| 151 |
* positions at once, as described by the array argument @p points. This |
| 152 |
* function is can be faster than the other function when the same |
| 153 |
* polynomial should be evaluated on several positions at once, e.g., the |
| 154 |
* x,y,z coordinates of a point for tensor-product polynomials. |
| 155 |
* |
| 156 |
* The template type `Number2` must implement arithmetic |
| 157 |
* operations such as additions or multiplication with the type |
| 158 |
* `number` of the polynomial, and must be convertible from |
| 159 |
* `number` by `operator=`. |
| 160 |
*/ |
| 161 |
template <std::size_t n_entries, typename Number2> |
| 162 |
#ifndef DEBUG |
| 163 |
DEAL_II_ALWAYS_INLINE |
| 164 |
#endif |
| 165 |
void |
| 166 |
values_of_array(const std::array<Number2, n_entries> &points, |
| 167 |
const unsigned int n_derivatives, |
| 168 |
std::array<Number2, n_entries> *values) const; |
| 169 |
|
| 170 |
/** |
| 171 |
* Degree of the polynomial. This is the degree reflected by the number of |
| 172 |
* coefficients provided by the constructor. Leading non-zero coefficients |
| 173 |
* are not treated separately. |
| 174 |
*/ |
| 175 |
unsigned int |
| 176 |
degree() const; |
| 177 |
|
| 178 |
/** |
| 179 |
* Scale the abscissa of the polynomial. Given the polynomial <i>p(t)</i> |
| 180 |
* and the scaling <i>t = ax</i>, then the result of this operation is the |
| 181 |
* polynomial <i>q</i>, such that <i>q(x) = p(t)</i>. |
| 182 |
* |
| 183 |
* The operation is performed in place. |
| 184 |
*/ |
| 185 |
void |
| 186 |
scale(const number factor); |
| 187 |
|
| 188 |
/** |
| 189 |
* Shift the abscissa oft the polynomial. Given the polynomial |
| 190 |
* <i>p(t)</i> and the shift <i>t = x + a</i>, then the result of this |
| 191 |
* operation is the polynomial <i>q</i>, such that <i>q(x) = p(t)</i>. |
| 192 |
* |
| 193 |
* The template parameter allows to compute the new coefficients with |
| 194 |
* higher accuracy, since all computations are performed with type |
| 195 |
* <tt>number2</tt>. This may be necessary, since this operation involves |
| 196 |
* a big number of additions. On a Sun Sparc Ultra with Solaris 2.8, the |
| 197 |
* difference between <tt>double</tt> and <tt>long double</tt> was not |
| 198 |
* significant, though. |
| 199 |
* |
| 200 |
* The operation is performed in place, i.e. the coefficients of the |
| 201 |
* present object are changed. |
| 202 |
*/ |
| 203 |
template <typename number2> |
| 204 |
void |
| 205 |
shift(const number2 offset); |
| 206 |
|
| 207 |
/** |
| 208 |
* Compute the derivative of a polynomial. |
| 209 |
*/ |
| 210 |
Polynomial<number> |
| 211 |
derivative() const; |
| 212 |
|
| 213 |
/** |
| 214 |
* Compute the primitive of a polynomial. the coefficient of the zero |
| 215 |
* order term of the polynomial is zero. |
| 216 |
*/ |
| 217 |
Polynomial<number> |
| 218 |
primitive() const; |
| 219 |
|
| 220 |
/** |
| 221 |
* Multiply with a scalar. |
| 222 |
*/ |
| 223 |
Polynomial<number> & |
| 224 |
operator*=(const double s); |
| 225 |
|
| 226 |
/** |
| 227 |
* Multiply with another polynomial. |
| 228 |
*/ |
| 229 |
Polynomial<number> & |
| 230 |
operator*=(const Polynomial<number> &p); |
| 231 |
|
| 232 |
/** |
| 233 |
* Add a second polynomial. |
| 234 |
*/ |
| 235 |
Polynomial<number> & |
| 236 |
operator+=(const Polynomial<number> &p); |
| 237 |
|
| 238 |
/** |
| 239 |
* Subtract a second polynomial. |
| 240 |
*/ |
| 241 |
Polynomial<number> & |
| 242 |
operator-=(const Polynomial<number> &p); |
| 243 |
|
| 244 |
/** |
| 245 |
* Test for equality of two polynomials. |
| 246 |
*/ |
| 247 |
bool |
| 248 |
operator==(const Polynomial<number> &p) const; |
| 249 |
|
| 250 |
/** |
| 251 |
* Print coefficients. |
| 252 |
*/ |
| 253 |
void |
| 254 |
print(std::ostream &out) const; |
| 255 |
|
| 256 |
/** |
| 257 |
* Write or read the data of this object to or from a stream for the |
| 258 |
* purpose of serialization using the [BOOST serialization |
| 259 |
* library](https://www.boost.org/doc/libs/1_74_0/libs/serialization/doc/index.html). |
| 260 |
*/ |
| 261 |
template <class Archive> |
| 262 |
void |
| 263 |
serialize(Archive &ar, const unsigned int version); |
| 264 |
|
| 265 |
/** |
| 266 |
* Return an estimate (in bytes) for the memory consumption of this object. |
| 267 |
*/ |
| 268 |
virtual std::size_t |
| 269 |
memory_consumption() const; |
| 270 |
|
| 271 |
protected: |
| 272 |
/** |
| 273 |
* This function performs the actual scaling. |
| 274 |
*/ |
| 275 |
static void |
| 276 |
scale(std::vector<number> &coefficients, const number factor); |
| 277 |
|
| 278 |
/** |
| 279 |
* This function performs the actual shift |
| 280 |
*/ |
| 281 |
template <typename number2> |
| 282 |
static void |
| 283 |
shift(std::vector<number> &coefficients, const number2 shift); |
| 284 |
|
| 285 |
/** |
| 286 |
* Multiply polynomial by a factor. |
| 287 |
*/ |
| 288 |
static void |
| 289 |
multiply(std::vector<number> &coefficients, const number factor); |
| 290 |
|
| 291 |
/** |
| 292 |
* Transform polynomial form of product of linear factors into standard |
| 293 |
* form, $\sum_i a_i x^i$. Deletes all data structures related to the |
| 294 |
* product form. |
| 295 |
*/ |
| 296 |
void |
| 297 |
transform_into_standard_form(); |
| 298 |
|
| 299 |
/** |
| 300 |
* Coefficients of the polynomial $\sum_i a_i x^i$. This vector is filled |
| 301 |
* by the constructor of this class and may be passed down by derived |
| 302 |
* classes. |
| 303 |
* |
| 304 |
* This vector cannot be constant since we want to allow copying of |
| 305 |
* polynomials. |
| 306 |
*/ |
| 307 |
std::vector<number> coefficients; |
| 308 |
|
| 309 |
/** |
| 310 |
* Stores whether the polynomial is in Lagrange product form, i.e., |
| 311 |
* constructed as a product $(x-x_0) (x-x_1) \ldots (x-x_n)/c$, or not. |
| 312 |
*/ |
| 313 |
bool in_lagrange_product_form; |
| 314 |
|
| 315 |
/** |
| 316 |
* If the polynomial is in Lagrange product form, i.e., constructed as a |
| 317 |
* product $(x-x_0) (x-x_1) \ldots (x-x_n)/c$, store the shifts $x_i$. |
| 318 |
*/ |
| 319 |
std::vector<number> lagrange_support_points; |
| 320 |
|
| 321 |
/** |
| 322 |
* If the polynomial is in Lagrange product form, i.e., constructed as a |
| 323 |
* product $(x-x_0) (x-x_1) \ldots (x-x_n)/c$, store the weight c. |
| 324 |
*/ |
| 325 |
number lagrange_weight; |
| 326 |
}; |
| 327 |
|
| 328 |
|
| 329 |
/** |
| 330 |
* Class generates Polynomial objects representing a monomial of degree n, |
| 331 |
* that is, the function $x^n$. |
| 332 |
*/ |
| 333 |
template <typename number> |
| 334 |
class Monomial : public Polynomial<number> |
| 335 |
{ |
| 336 |
public: |
| 337 |
/** |
| 338 |
* Constructor, taking the degree of the monomial and an optional |
| 339 |
* coefficient as arguments. |
| 340 |
*/ |
| 341 |
Monomial(const unsigned int n, const double coefficient = 1.); |
| 342 |
|
| 343 |
/** |
| 344 |
* Return a vector of Monomial objects of degree zero through |
| 345 |
* <tt>degree</tt>, which then spans the full space of polynomials up to |
| 346 |
* the given degree. This function may be used to initialize the |
| 347 |
* TensorProductPolynomials and PolynomialSpace classes. |
| 348 |
*/ |
| 349 |
static std::vector<Polynomial<number>> |
| 350 |
generate_complete_basis(const unsigned int degree); |
| 351 |
|
| 352 |
private: |
| 353 |
/** |
| 354 |
* Needed by constructor. |
| 355 |
*/ |
| 356 |
static std::vector<number> |
| 357 |
make_vector(unsigned int n, const double coefficient); |
| 358 |
}; |
| 359 |
|
| 360 |
|
| 361 |
/** |
| 362 |
* Lagrange polynomials with equidistant interpolation points in [0,1]. The |
| 363 |
* polynomial of degree <tt>n</tt> has got <tt>n+1</tt> interpolation |
| 364 |
* points. The interpolation points are sorted in ascending order. This |
| 365 |
* order gives an index to each interpolation point. A Lagrangian |
| 366 |
* polynomial equals to 1 at its `support point', and 0 at all other |
| 367 |
* interpolation points. For example, if the degree is 3, and the support |
| 368 |
* point is 1, then the polynomial represented by this object is cubic and |
| 369 |
* its value is 1 at the point <tt>x=1/3</tt>, and zero at the point |
| 370 |
* <tt>x=0</tt>, <tt>x=2/3</tt>, and <tt>x=1</tt>. All the polynomials have |
| 371 |
* polynomial degree equal to <tt>degree</tt>, but together they span the |
| 372 |
* entire space of polynomials of degree less than or equal <tt>degree</tt>. |
| 373 |
* |
| 374 |
* The Lagrange polynomials are implemented up to degree 10. |
| 375 |
*/ |
| 376 |
class LagrangeEquidistant : public Polynomial<double> |
| 377 |
{ |
| 378 |
public: |
| 379 |
/** |
| 380 |
* Constructor. Takes the degree <tt>n</tt> of the Lagrangian polynomial |
| 381 |
* and the index <tt>support_point</tt> of the support point. Fills the |
| 382 |
* <tt>coefficients</tt> of the base class Polynomial. |
| 383 |
*/ |
| 384 |
LagrangeEquidistant(const unsigned int n, const unsigned int support_point); |
| 385 |
|
| 386 |
/** |
| 387 |
* Return a vector of polynomial objects of degree <tt>degree</tt>, which |
| 388 |
* then spans the full space of polynomials up to the given degree. The |
| 389 |
* polynomials are generated by calling the constructor of this class with |
| 390 |
* the same degree but support point running from zero to <tt>degree</tt>. |
| 391 |
* This function may be used to initialize the TensorProductPolynomials |
| 392 |
* and PolynomialSpace classes. |
| 393 |
*/ |
| 394 |
static std::vector<Polynomial<double>> |
| 395 |
generate_complete_basis(const unsigned int degree); |
| 396 |
|
| 397 |
private: |
| 398 |
/** |
| 399 |
* Compute the <tt>coefficients</tt> of the base class Polynomial. This |
| 400 |
* function is <tt>static</tt> to allow to be called in the constructor. |
| 401 |
*/ |
| 402 |
static void |
| 403 |
compute_coefficients(const unsigned int n, |
| 404 |
const unsigned int support_point, |
| 405 |
std::vector<double> &a); |
| 406 |
}; |
| 407 |
|
| 408 |
|
| 409 |
|
| 410 |
/** |
| 411 |
* Given a set of points along the real axis, this function returns all |
| 412 |
* Lagrange polynomials for interpolation of these points. The number of |
| 413 |
* polynomials is equal to the number of points and the maximum degree is |
| 414 |
* one less. |
| 415 |
*/ |
| 416 |
std::vector<Polynomial<double>> |
| 417 |
generate_complete_Lagrange_basis(const std::vector<Point<1>> &points); |
| 418 |
|
| 419 |
|
| 420 |
|
| 421 |
/** |
| 422 |
* Legendre polynomials of arbitrary degree. Constructing a Legendre |
| 423 |
* polynomial of degree <tt>p</tt>, the roots will be computed by the Gauss |
| 424 |
* formula of the respective number of points and a representation of the |
| 425 |
* polynomial by its roots. |
| 426 |
* |
| 427 |
* @note The polynomials defined by this class differ in two aspects by what |
| 428 |
* is usually referred to as Legendre polynomials: (i) This classes defines |
| 429 |
* them on the reference interval $[0,1]$, rather than the commonly used |
| 430 |
* interval $[-1,1]$. (ii) The polynomials have been scaled in such a way |
| 431 |
* that they are orthonormal, not just orthogonal; consequently, the |
| 432 |
* polynomials do not necessarily have boundary values equal to one. |
| 433 |
*/ |
| 434 |
class Legendre : public Polynomial<double> |
| 435 |
{ |
| 436 |
public: |
| 437 |
/** |
| 438 |
* Constructor for polynomial of degree <tt>p</tt>. |
| 439 |
*/ |
| 440 |
Legendre(const unsigned int p); |
| 441 |
|
| 442 |
/** |
| 443 |
* Return a vector of Legendre polynomial objects of degrees zero through |
| 444 |
* <tt>degree</tt>, which then spans the full space of polynomials up to |
| 445 |
* the given degree. This function may be used to initialize the |
| 446 |
* TensorProductPolynomials and PolynomialSpace classes. |
| 447 |
*/ |
| 448 |
static std::vector<Polynomial<double>> |
| 449 |
generate_complete_basis(const unsigned int degree); |
| 450 |
}; |
| 451 |
|
| 452 |
/** |
| 453 |
* Lobatto polynomials of arbitrary degree on <tt>[0,1]</tt>. |
| 454 |
* |
| 455 |
* These polynomials are the integrated Legendre polynomials on [0,1]. The |
| 456 |
* first two polynomials are the standard linear shape functions given by |
| 457 |
* $l_0(x) = 1-x$ and $l_1(x) = x$. For $i\geq2$ we use the definition |
| 458 |
* $l_i(x) = \frac{1}{\Vert L_{i-1}\Vert_2}\int_0^x L_{i-1}(t)\,dt$, where |
| 459 |
* $L_i$ denotes the $i$-th Legendre polynomial on $[0,1]$. The Lobatto |
| 460 |
* polynomials $l_0,\ldots,l_k$ form a complete basis of the polynomials |
| 461 |
* space of degree $k$. |
| 462 |
* |
| 463 |
* Calling the constructor with a given index <tt>k</tt> will generate the |
| 464 |
* polynomial with index <tt>k</tt>. But only for $k\geq 1$ the index equals |
| 465 |
* the degree of the polynomial. For <tt>k==0</tt> also a polynomial of |
| 466 |
* degree 1 is generated. |
| 467 |
* |
| 468 |
* These polynomials are used for the construction of the shape functions of |
| 469 |
* Nédélec elements of arbitrary order. |
| 470 |
*/ |
| 471 |
class Lobatto : public Polynomial<double> |
| 472 |
{ |
| 473 |
public: |
| 474 |
/** |
| 475 |
* Constructor for polynomial of degree <tt>p</tt>. There is an exception |
| 476 |
* for <tt>p==0</tt>, see the general documentation. |
| 477 |
*/ |
| 478 |
Lobatto(const unsigned int p = 0); |
| 479 |
|
| 480 |
/** |
| 481 |
* Return the polynomials with index <tt>0</tt> up to <tt>degree</tt>. |
| 482 |
* There is an exception for <tt>p==0</tt>, see the general documentation. |
| 483 |
*/ |
| 484 |
static std::vector<Polynomial<double>> |
| 485 |
generate_complete_basis(const unsigned int p); |
| 486 |
|
| 487 |
private: |
| 488 |
/** |
| 489 |
* Compute coefficients recursively. |
| 490 |
*/ |
| 491 |
std::vector<double> |
| 492 |
compute_coefficients(const unsigned int p); |
| 493 |
}; |
| 494 |
|
| 495 |
|
| 496 |
|
| 497 |
/** |
| 498 |
* Hierarchical polynomials of arbitrary degree on <tt>[0,1]</tt>. |
| 499 |
* |
| 500 |
* When Constructing a Hierarchical polynomial of degree <tt>p</tt>, the |
| 501 |
* coefficients will be computed by a recursion formula. The coefficients |
| 502 |
* are stored in a static data vector to be available when needed next time. |
| 503 |
* |
| 504 |
* These hierarchical polynomials are based on those of Demkowicz, Oden, |
| 505 |
* Rachowicz, and Hardy (CMAME 77 (1989) 79-112, Sec. 4). The first two |
| 506 |
* polynomials are the standard linear shape functions given by $\phi_{0}(x) |
| 507 |
* = 1 - x$ and $\phi_{1}(x) = x$. For $l \geq 2$ we use the definitions |
| 508 |
* $\phi_{l}(x) = (2x-1)^l - 1, l = 2,4,6,...$ and $\phi_{l}(x) = (2x-1)^l - |
| 509 |
* (2x-1), l = 3,5,7,...$. These satisfy the recursion relations |
| 510 |
* $\phi_{l}(x) = (2x-1)\phi_{l-1}, l=3,5,7,...$ and $\phi_{l}(x) = |
| 511 |
* (2x-1)\phi_{l-1} + \phi_{2}, l=4,6,8,...$. |
| 512 |
* |
| 513 |
* The degrees of freedom are the values at the vertices and the derivatives |
| 514 |
* at the midpoint. Currently, we do not scale the polynomials in any way, |
| 515 |
* although better conditioning of the element @ref GlossStiffnessMatrix "stiffness matrix" could |
| 516 |
* possibly be achieved with scaling. |
| 517 |
* |
| 518 |
* Calling the constructor with a given index <tt>p</tt> will generate the |
| 519 |
* following: if <tt>p==0</tt>, then the resulting polynomial is the linear |
| 520 |
* function associated with the left vertex, if <tt>p==1</tt> the one |
| 521 |
* associated with the right vertex. For higher values of <tt>p</tt>, you |
| 522 |
* get the polynomial of degree <tt>p</tt> that is orthogonal to all |
| 523 |
* previous ones. Note that for <tt>p==0</tt> you therefore do <b>not</b> |
| 524 |
* get a polynomial of degree zero, but one of degree one. This is to allow |
| 525 |
* generating a complete basis for polynomial spaces, by just iterating over |
| 526 |
* the indices given to the constructor. |
| 527 |
* |
| 528 |
* On the other hand, the function generate_complete_basis() creates a |
| 529 |
* complete basis of given degree. In order to be consistent with the |
| 530 |
* concept of a polynomial degree, if the given argument is zero, it does |
| 531 |
* <b>not</b> return the linear polynomial described above, but rather a |
| 532 |
* constant polynomial. |
| 533 |
*/ |
| 534 |
class Hierarchical : public Polynomial<double> |
| 535 |
{ |
| 536 |
public: |
| 537 |
/** |
| 538 |
* Constructor for polynomial of degree <tt>p</tt>. There is an exception |
| 539 |
* for <tt>p==0</tt>, see the general documentation. |
| 540 |
*/ |
| 541 |
Hierarchical(const unsigned int p); |
| 542 |
|
| 543 |
/** |
| 544 |
* Return a vector of Hierarchical polynomial objects of degrees zero |
| 545 |
* through <tt>degree</tt>, which then spans the full space of polynomials |
| 546 |
* up to the given degree. Note that there is an exception if the given |
| 547 |
* <tt>degree</tt> equals zero, see the general documentation of this |
| 548 |
* class. |
| 549 |
* |
| 550 |
* This function may be used to initialize the TensorProductPolynomials, |
| 551 |
* AnisotropicPolynomials, and PolynomialSpace classes. |
| 552 |
*/ |
| 553 |
static std::vector<Polynomial<double>> |
| 554 |
generate_complete_basis(const unsigned int degree); |
| 555 |
|
| 556 |
private: |
| 557 |
/** |
| 558 |
* Compute coefficients recursively. |
| 559 |
*/ |
| 560 |
static void |
| 561 |
compute_coefficients(const unsigned int p); |
| 562 |
|
| 563 |
/** |
| 564 |
* Get coefficients for constructor. This way, it can use the |
| 565 |
* non-standard constructor of Polynomial. |
| 566 |
*/ |
| 567 |
static const std::vector<double> & |
| 568 |
get_coefficients(const unsigned int p); |
| 569 |
|
| 570 |
/** |
| 571 |
* Vector with already computed coefficients. For each degree of the |
| 572 |
* polynomial, we keep one pointer to the list of coefficients; we do so |
| 573 |
* rather than keeping a vector of vectors in order to simplify |
| 574 |
* programming multithread-safe. In order to avoid memory leak, we use a |
| 575 |
* unique_ptr in order to correctly free the memory of the vectors when |
| 576 |
* the global destructor is called. |
| 577 |
*/ |
| 578 |
static std::vector<std::unique_ptr<const std::vector<double>>> |
| 579 |
recursive_coefficients; |
| 580 |
|
| 581 |
/** |
| 582 |
* The mutex that guards read and write access to the |
| 583 |
* `recursive_coefficients` array. |
| 584 |
*/ |
| 585 |
static std::shared_mutex coefficients_lock; |
| 586 |
}; |
| 587 |
|
| 588 |
|
| 589 |
|
| 590 |
/** |
| 591 |
* Polynomials for Hermite interpolation condition. |
| 592 |
* |
| 593 |
* This is the set of polynomials of degree at least three, such that the |
| 594 |
* following interpolation conditions are met: the polynomials and their |
| 595 |
* first derivatives vanish at the values <i>x</i>=0 and <i>x</i>=1, with |
| 596 |
* the exceptions <i>p</i><sub>0</sub>(0)=1, |
| 597 |
* <i>p</i><sub><i>1</i></sub>(1)=1, <i>p</i>'<sub>2</sub>(0)=1, |
| 598 |
* <i>p'</i><sub>3</sub>(1)=1. |
| 599 |
* |
| 600 |
* For degree three, we obtain the standard four Hermitian interpolation |
| 601 |
* polynomials, see for instance <a |
| 602 |
* href="http://en.wikipedia.org/wiki/Cubic_Hermite_spline">Wikipedia</a>. |
| 603 |
* For higher degrees, these are augmented first, by the polynomial of |
| 604 |
* degree four with vanishing values and derivatives at <i>x</i>=0 and |
| 605 |
* <i>x</i>=1, then by the product of this fourth order polynomial with |
| 606 |
* Legendre polynomials of increasing order. The implementation is |
| 607 |
* @f{align*}{ |
| 608 |
* p_0(x) &= 2x^3-3x^2+1 \\ |
| 609 |
* p_1(x) &= -2x^3+3x^2 \\ |
| 610 |
* p_2(x) &= x^3-2x^2+x \\ |
| 611 |
* p_3(x) &= x^3-x^2 \\ |
| 612 |
* p_4(x) &= 16x^2(x-1)^2 \\ |
| 613 |
* \ldots & \ldots \\ |
| 614 |
* p_k(x) &= x^2(x-1)^2 L_{k-4}(x) |
| 615 |
* @f} |
| 616 |
*/ |
| 617 |
class HermiteInterpolation : public Polynomial<double> |
| 618 |
{ |
| 619 |
public: |
| 620 |
/** |
| 621 |
* Constructor for polynomial with index <tt>p</tt>. See the class |
| 622 |
* documentation on the definition of the sequence of polynomials. |
| 623 |
*/ |
| 624 |
HermiteInterpolation(const unsigned int p); |
| 625 |
|
| 626 |
/** |
| 627 |
* Return the polynomials with index <tt>0</tt> up to <tt>p+1</tt> in a |
| 628 |
* space of degree up to <tt>p</tt>. Here, <tt>p</tt> has to be at least |
| 629 |
* 3. |
| 630 |
*/ |
| 631 |
static std::vector<Polynomial<double>> |
| 632 |
generate_complete_basis(const unsigned int p); |
| 633 |
}; |
| 634 |
|
| 635 |
|
| 636 |
|
| 637 |
/** |
| 638 |
* Polynomials for a variant of Hermite polynomials with better condition |
| 639 |
* number in the interpolation than the basis from HermiteInterpolation. |
| 640 |
* |
| 641 |
* In analogy to the proper Hermite polynomials, this basis evaluates the |
| 642 |
* first polynomial $p_0$ to 1 at $x=0$ and has both a zero value and zero |
| 643 |
* derivative at $x=1$. Likewise, the last polynomial $p_n$ evaluates to 1 |
| 644 |
* at $x=1$ with a zero value and zero derivative at $x=0$. The second |
| 645 |
* polynomial $p_1$ and the second to last polynomial $p_{n-1}$ represent |
| 646 |
* the derivative degree of freedom at $x=0$ and $x=1$, respectively. |
| 647 |
* They are zero at both the end points $x=0, x=1$ and have zero |
| 648 |
* derivative at the opposite end, $p_1'(1)=0$ and $p_{n-1}'(0)=0$. As |
| 649 |
* opposed to the original Hermite polynomials, $p_0$ does not have zero |
| 650 |
* derivative at $x=0$. The additional degree of freedom is used to make |
| 651 |
* $p_0$ and $p_1$ orthogonal, which for $n=3$ results in a root at |
| 652 |
* $x=\frac{2}{7}$ for $p_0$ and at $x=\frac{5}{7}$ for $p_n$, |
| 653 |
* respectively. Furthermore, the extension of these polynomials to higher |
| 654 |
* degrees $n>3$ is constructed by adding additional nodes inside the unit |
| 655 |
* interval, again ensuring better conditioning. The nodes are computed as |
| 656 |
* the roots of the Jacobi polynomials for $\alpha=\beta=4$, which are |
| 657 |
* orthogonal against the square of the generating function $x^2(1-x)^2$ |
| 658 |
* with the Hermite |
| 659 |
* property. Then, these polynomials are constructed in the usual way as |
| 660 |
* Lagrange polynomials with double roots at $x=0$ and $x=1$. For example |
| 661 |
* with $n=4$, all of $p_0, p_1, p_3, p_4$ get an additional root at $x=0.5$ |
| 662 |
* through the factor $(x-0.5)$. In summary, this basis is dominated by |
| 663 |
* nodal contributions, but it is not a nodal one because the second and |
| 664 |
* second to last polynomials that are non-nodal, and due to the presence of |
| 665 |
* double nodes in $x=0$ and $x=1$. The weights of the basis functions are |
| 666 |
* set such that the sum of all polynomials with unit weight represents the |
| 667 |
* constant function 1, similarly to Lagrange polynomials. |
| 668 |
* |
| 669 |
* The basis only contains Hermite information for <code>degree>=3</code>, |
| 670 |
* but it is also implemented for degrees between 0 and two. For the linear |
| 671 |
* case, the usual hat functions are implemented, whereas the polynomials |
| 672 |
* for <code>degree=2</code> are $p_0(x)=(1-x)^2$, $p_1(x)=2x(x-1)$, and |
| 673 |
* $p_2(x)=x^2$, in accordance with the construction principle for degree 3. |
| 674 |
* |
| 675 |
* These two relaxations improve the condition number of the @ref GlossMassMatrix "mass matrix" |
| 676 |
* (i.e., interpolation) significantly, as can be seen from the following |
| 677 |
* table: |
| 678 |
* |
| 679 |
* <table align="center" border="1"> |
| 680 |
* <tr> |
| 681 |
* <th> </th> |
| 682 |
* <th colspan="2">Condition number mass matrix</th> |
| 683 |
* </tr> |
| 684 |
* <tr> |
| 685 |
* <th>degree</th> |
| 686 |
* <th>HermiteInterpolation</th> |
| 687 |
* <th>HermiteLikeInterpolation</th> |
| 688 |
* </tr> |
| 689 |
* <tr> |
| 690 |
* <th>n=3</th> |
| 691 |
* <th>1057</th> |
| 692 |
* <th>17.18</th> |
| 693 |
* </tr> |
| 694 |
* <tr> |
| 695 |
* <th>n=4</th> |
| 696 |
* <th>6580</th> |
| 697 |
* <th>16.83</th> |
| 698 |
* </tr> |
| 699 |
* <tr> |
| 700 |
* <th>n=5</th> |
| 701 |
* <th>1.875e+04</th> |
| 702 |
* <th>15.99</th> |
| 703 |
* </tr> |
| 704 |
* <tr> |
| 705 |
* <th>n=6</th> |
| 706 |
* <th>6.033e+04</th> |
| 707 |
* <th>16.34</th> |
| 708 |
* </tr> |
| 709 |
* <tr> |
| 710 |
* <th>n=10</th> |
| 711 |
* <th>9.756e+05</th> |
| 712 |
* <th>20.70</th> |
| 713 |
* </tr> |
| 714 |
* <tr> |
| 715 |
* <th>n=15</th> |
| 716 |
* <th>9.431e+06</th> |
| 717 |
* <th>27.91</th> |
| 718 |
* </tr> |
| 719 |
* <tr> |
| 720 |
* <th>n=25</th> |
| 721 |
* <th>2.220e+08</th> |
| 722 |
* <th>43.54</th> |
| 723 |
* </tr> |
| 724 |
* <tr> |
| 725 |
* <th>n=35</th> |
| 726 |
* <th>2.109e+09</th> |
| 727 |
* <th>59.51</th> |
| 728 |
* </tr> |
| 729 |
* </table> |
| 730 |
* |
| 731 |
* This polynomial inherits the advantageous property of Hermite polynomials |
| 732 |
* where only two functions have value and/or derivative nonzero on a face |
| 733 |
* advantageous for discontinuous Galerkin methods |
| 734 |
* but gives better condition numbers of interpolation, which improves the |
| 735 |
* performance of some iterative schemes like conjugate gradients with |
| 736 |
* point-Jacobi. This polynomial is used in FE_DGQHermite. |
| 737 |
*/ |
| 738 |
class HermiteLikeInterpolation : public Polynomial<double> |
| 739 |
{ |
| 740 |
public: |
| 741 |
/** |
| 742 |
* Constructor for the polynomial with index <tt>index</tt> within the set |
| 743 |
* up polynomials of degree @p degree. |
| 744 |
*/ |
| 745 |
HermiteLikeInterpolation(const unsigned int degree, |
| 746 |
const unsigned int index); |
| 747 |
|
| 748 |
/** |
| 749 |
* Return the polynomials with index <tt>0</tt> up to <tt>degree+1</tt> in |
| 750 |
* a space of degree up to <tt>degree</tt>. |
| 751 |
*/ |
| 752 |
static std::vector<Polynomial<double>> |
| 753 |
generate_complete_basis(const unsigned int degree); |
| 754 |
}; |
| 755 |
|
| 756 |
|
| 757 |
|
| 758 |
/* |
| 759 |
* Evaluate a Jacobi polynomial $ P_n^{\alpha, \beta}(x) $ specified by the |
| 760 |
* parameters @p alpha, @p beta, @p n, where @p n is the degree of the |
| 761 |
* Jacobi polynomial. |
| 762 |
* |
| 763 |
* @note The Jacobi polynomials are not orthonormal and are defined on the |
| 764 |
* unit interval $[0, 1]$ as usual for deal.II, rather than $[-1, +1]$ often |
| 765 |
* used in literature. @p x is the point of evaluation. |
| 766 |
*/ |
| 767 |
template <typename Number> |
| 768 |
Number |
| 769 |
jacobi_polynomial_value(const unsigned int degree, |
| 770 |
const int alpha, |
| 771 |
const int beta, |
| 772 |
const Number x); |
| 773 |
|
| 774 |
|
| 775 |
/** |
| 776 |
* Compute the roots of the Jacobi polynomials on the unit interval $[0, 1]$ |
| 777 |
* of the given degree. These roots are used in several places inside the |
| 778 |
* deal.II library, such as the Gauss-Lobatto quadrature formula or for the |
| 779 |
* Hermite-like interpolation. |
| 780 |
* |
| 781 |
* The algorithm uses a Newton algorithm, using the zeros of the Chebyshev |
| 782 |
* polynomials as an initial guess. This code has been tested for alpha and |
| 783 |
* beta equal to zero (Legendre case), one (Gauss-Lobatto case) as well as |
| 784 |
* two, so be careful when using it for other values as the Newton iteration |
| 785 |
* might or might not converge. |
| 786 |
*/ |
| 787 |
template <typename Number> |
| 788 |
std::vector<Number> |
| 789 |
jacobi_polynomial_roots(const unsigned int degree, |
| 790 |
const int alpha, |
| 791 |
const int beta); |
| 792 |
} // namespace Polynomials |
| 793 |
|
| 794 |
|
| 795 |
/** @} */ |
| 796 |
|
| 797 |
/* -------------------------- inline functions --------------------- */ |
| 798 |
|
| 799 |
namespace Polynomials |
| 800 |
{ |
| 801 |
template <typename number> |
| 802 |
inline Polynomial<number>::Polynomial() |
| 803 |
: in_lagrange_product_form(false) |
| 804 |
, lagrange_weight(1.) |
| 805 |
{} |
| 806 |
|
| 807 |
|
| 808 |
|
| 809 |
template <typename number> |
| 810 |
inline unsigned int |
| 811 |
Polynomial<number>::degree() const |
| 812 |
{ |
| 813 |
if (in_lagrange_product_form == true) |
| 814 |
{ |
| 815 |
return lagrange_support_points.size(); |
| 816 |
} |
| 817 |
else |
| 818 |
{ |
| 819 |
Assert(coefficients.size() > 0, ExcEmptyObject()); |
| 820 |
return coefficients.size() - 1; |
| 821 |
} |
| 822 |
} |
| 823 |
|
| 824 |
|
| 825 |
|
| 826 |
template <typename number> |
| 827 |
inline number |
| 828 |
Polynomial<number>::value(const number x) const |
| 829 |
{ |
| 830 |
if (in_lagrange_product_form == false) |
| 831 |
{ |
| 832 |
Assert(coefficients.size() > 0, ExcEmptyObject()); |
| 833 |
|
| 834 |
// Horner scheme |
| 835 |
const unsigned int m = coefficients.size(); |
| 836 |
number value = coefficients.back(); |
| 837 |
for (int k = m - 2; k >= 0; --k) |
| 838 |
value = value * x + coefficients[k]; |
| 839 |
return value; |
| 840 |
} |
| 841 |
else |
| 842 |
{ |
| 843 |
// direct evaluation of Lagrange polynomial |
| 844 |
const unsigned int m = lagrange_support_points.size(); |
| 845 |
number value = 1.; |
| 846 |
for (unsigned int j = 0; j < m; ++j) |
| 847 |
value *= x - lagrange_support_points[j]; |
| 848 |
value *= lagrange_weight; |
| 849 |
return value; |
| 850 |
} |
| 851 |
} |
| 852 |
|
| 853 |
|
| 854 |
|
| 855 |
template <typename number> |
| 856 |
template <typename Number2> |
| 857 |
inline void |
| 858 |
Polynomial<number>::value(const Number2 x, |
| 859 |
const unsigned int n_derivatives, |
| 860 |
Number2 *values) const |
| 861 |
{ |
| 862 |
values_of_array(std::array<Number2, 1ul>{{x}}, |
| 863 |
n_derivatives, |
| 864 |
reinterpret_cast<std::array<Number2, 1ul> *>(values)); |
| 865 |
} |
| 866 |
|
| 867 |
|
| 868 |
|
| 869 |
template <typename number> |
| 870 |
template <std::size_t n_entries, typename Number2> |
| 871 |
inline |
| 872 |
#ifndef DEBUG |
| 873 |
DEAL_II_ALWAYS_INLINE |
| 874 |
#endif |
| 875 |
void |
| 876 |
Polynomial<number>::values_of_array( |
| 877 |
const std::array<Number2, n_entries> &x, |
| 878 |
const unsigned int n_derivatives, |
| 879 |
std::array<Number2, n_entries> *values) const |
| 880 |
{ |
| 881 |
// evaluate Lagrange polynomial and derivatives |
| 882 |
if (in_lagrange_product_form == true) |
| 883 |
{ |
| 884 |
// to compute the value and all derivatives of a polynomial of the |
| 885 |
// form (x-x_1)*(x-x_2)*...*(x-x_n), expand the derivatives like |
| 886 |
// automatic differentiation does. |
| 887 |
const unsigned int n_supp = lagrange_support_points.size(); |
| 888 |
const number weight = lagrange_weight; |
| 889 |
switch (n_derivatives) |
| 890 |
{ |
| 891 |
default: |
| 892 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 893 |
values[0][e] = weight; |
| 894 |
for (unsigned int k = 1; k <= n_derivatives; ++k) |
| 895 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 896 |
values[k][e] = 0.; |
| 897 |
for (unsigned int i = 0; i < n_supp; ++i) |
| 898 |
{ |
| 899 |
std::array<Number2, n_entries> v = x; |
| 900 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 901 |
v[e] -= lagrange_support_points[i]; |
| 902 |
|
| 903 |
// multiply by (x-x_i) and compute action on all derivatives, |
| 904 |
// too (inspired from automatic differentiation: implement the |
| 905 |
// product rule for the old value and the new variable 'v', |
| 906 |
// i.e., expand value v and derivative one). since we reuse a |
| 907 |
// value from the next lower derivative from the steps before, |
| 908 |
// need to start from the highest derivative |
| 909 |
for (unsigned int k = n_derivatives; k > 0; --k) |
| 910 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 911 |
values[k][e] = (values[k][e] * v[e] + values[k - 1][e]); |
| 912 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 913 |
values[0][e] *= v[e]; |
| 914 |
} |
| 915 |
// finally, multiply derivatives by k! to transform the product |
| 916 |
// p_n = p^(n)(x)/k! into the actual form of the derivative |
| 917 |
{ |
| 918 |
number k_factorial = 2; |
| 919 |
for (unsigned int k = 2; k <= n_derivatives; ++k) |
| 920 |
{ |
| 921 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 922 |
values[k][e] *= k_factorial; |
| 923 |
k_factorial *= static_cast<number>(k + 1); |
| 924 |
} |
| 925 |
} |
| 926 |
break; |
| 927 |
|
| 928 |
// manually implement case 0 (values only), case 1 (value + first |
| 929 |
// derivative), and case 2 (up to second derivative) since they |
| 930 |
// might be called often. then, we can unroll the inner loop and |
| 931 |
// keep the temporary results as local variables to help the |
| 932 |
// compiler with the pointer aliasing analysis. |
| 933 |
case 0: |
| 934 |
{ |
| 935 |
std::array<Number2, n_entries> value; |
| 936 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 937 |
value[e] = weight; |
| 938 |
for (unsigned int i = 0; i < n_supp; ++i) |
| 939 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 940 |
value[e] *= (x[e] - lagrange_support_points[i]); |
| 941 |
|
| 942 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 943 |
values[0][e] = value[e]; |
| 944 |
break; |
| 945 |
} |
| 946 |
|
| 947 |
case 1: |
| 948 |
{ |
| 949 |
std::array<Number2, n_entries> value, derivative = {}; |
| 950 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 951 |
value[e] = weight; |
| 952 |
for (unsigned int i = 0; i < n_supp; ++i) |
| 953 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 954 |
{ |
| 955 |
const Number2 v = x[e] - lagrange_support_points[i]; |
| 956 |
derivative[e] = derivative[e] * v + value[e]; |
| 957 |
value[e] *= v; |
| 958 |
} |
| 959 |
|
| 960 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 961 |
{ |
| 962 |
values[0][e] = value[e]; |
| 963 |
values[1][e] = derivative[e]; |
| 964 |
} |
| 965 |
break; |
| 966 |
} |
| 967 |
|
| 968 |
case 2: |
| 969 |
{ |
| 970 |
std::array<Number2, n_entries> value, derivative = {}, |
| 971 |
second = {}; |
| 972 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 973 |
value[e] = weight; |
| 974 |
for (unsigned int i = 0; i < n_supp; ++i) |
| 975 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 976 |
{ |
| 977 |
const Number2 v = x[e] - lagrange_support_points[i]; |
| 978 |
second[e] = second[e] * v + derivative[e]; |
| 979 |
derivative[e] = derivative[e] * v + value[e]; |
| 980 |
value[e] *= v; |
| 981 |
} |
| 982 |
|
| 983 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 984 |
{ |
| 985 |
values[0][e] = value[e]; |
| 986 |
values[1][e] = derivative[e]; |
| 987 |
values[2][e] = static_cast<number>(2) * second[e]; |
| 988 |
} |
| 989 |
break; |
| 990 |
} |
| 991 |
} |
| 992 |
return; |
| 993 |
} |
| 994 |
|
| 995 |
Assert(coefficients.size() > 0, ExcEmptyObject()); |
| 996 |
|
| 997 |
// if derivatives are needed, then do it properly by the full |
| 998 |
// Horner scheme |
| 999 |
const unsigned int m = coefficients.size(); |
| 1000 |
std::vector<std::array<Number2, n_entries>> a(coefficients.size()); |
| 1001 |
for (unsigned int i = 0; i < coefficients.size(); ++i) |
| 1002 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 1003 |
a[i][e] = coefficients[i]; |
| 1004 |
|
| 1005 |
unsigned int j_factorial = 1; |
| 1006 |
|
| 1007 |
// loop over all requested derivatives. note that derivatives @p{j>m} are |
| 1008 |
// necessarily zero, as they differentiate the polynomial more often than |
| 1009 |
// the highest power is |
| 1010 |
const unsigned int min_valuessize_m = std::min(n_derivatives + 1, m); |
| 1011 |
for (unsigned int j = 0; j < min_valuessize_m; ++j) |
| 1012 |
{ |
| 1013 |
for (int k = m - 2; k >= static_cast<int>(j); --k) |
| 1014 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 1015 |
a[k][e] += x[e] * a[k + 1][e]; |
| 1016 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 1017 |
values[j][e] = static_cast<number>(j_factorial) * a[j][e]; |
| 1018 |
|
| 1019 |
j_factorial *= j + 1; |
| 1020 |
} |
| 1021 |
|
| 1022 |
// fill higher derivatives by zero |
| 1023 |
for (unsigned int j = min_valuessize_m; j <= n_derivatives; ++j) |
| 1024 |
for (unsigned int e = 0; e < n_entries; ++e) |
| 1025 |
values[j][e] = 0.; |
| 1026 |
} |
| 1027 |
|
| 1028 |
|
| 1029 |
|
| 1030 |
template <typename number> |
| 1031 |
template <class Archive> |
| 1032 |
inline void |
| 1033 |
Polynomial<number>::serialize(Archive &ar, const unsigned int) |
| 1034 |
{ |
| 1035 |
// forward to serialization function in the base class. |
| 1036 |
ar &static_cast<EnableObserverPointer &>(*this); |
| 1037 |
ar &coefficients; |
| 1038 |
ar &in_lagrange_product_form; |
| 1039 |
ar &lagrange_support_points; |
| 1040 |
ar &lagrange_weight; |
| 1041 |
} |
| 1042 |
|
| 1043 |
|
| 1044 |
|
| 1045 |
template <typename Number> |
| 1046 |
Number |
| 1047 |
jacobi_polynomial_value(const unsigned int degree, |
| 1048 |
const int alpha, |
| 1049 |
const int beta, |
| 1050 |
const Number x) |
| 1051 |
{ |
| 1052 |
Assert(alpha >= 0 && beta >= 0, |
| 1053 |
ExcNotImplemented("Negative alpha/beta coefficients not supported")); |
| 1054 |
// the Jacobi polynomial is evaluated using a recursion formula. |
| 1055 |
Number p0, p1; |
| 1056 |
|
| 1057 |
// The recursion formula is defined for the interval [-1, 1], so rescale |
| 1058 |
// to that interval here |
| 1059 |
const Number xeval = Number(-1) + 2. * x; |
| 1060 |
|
| 1061 |
// initial values P_0(x), P_1(x): |
| 1062 |
p0 = 1.0; |
| 1063 |
if (degree == 0) |
| 1064 |
return p0; |
| 1065 |
p1 = ((alpha + beta + 2) * xeval + (alpha - beta)) / 2; |
| 1066 |
if (degree == 1) |
| 1067 |
return p1; |
| 1068 |
|
| 1069 |
for (unsigned int i = 1; i < degree; ++i) |
| 1070 |
{ |
| 1071 |
const Number v = 2 * i + (alpha + beta); |
| 1072 |
const Number a1 = 2 * (i + 1) * (i + (alpha + beta + 1)) * v; |
| 1073 |
const Number a2 = (v + 1) * (alpha * alpha - beta * beta); |
| 1074 |
const Number a3 = v * (v + 1) * (v + 2); |
| 1075 |
const Number a4 = 2 * (i + alpha) * (i + beta) * (v + 2); |
| 1076 |
|
| 1077 |
const Number pn = ((a2 + a3 * xeval) * p1 - a4 * p0) / a1; |
| 1078 |
p0 = p1; |
| 1079 |
p1 = pn; |
| 1080 |
} |
| 1081 |
return p1; |
| 1082 |
} |
| 1083 |
|
| 1084 |
|
| 1085 |
|
| 1086 |
template <typename Number> |
| 1087 |
std::vector<Number> |
| 1088 |
jacobi_polynomial_roots(const unsigned int degree, |
| 1089 |
const int alpha, |
| 1090 |
const int beta) |
| 1091 |
{ |
| 1092 |
std::vector<Number> x(degree, 0.5); |
| 1093 |
|
| 1094 |
// compute zeros with a Newton algorithm. |
| 1095 |
|
| 1096 |
// Set tolerance. For long double we might not always get the additional |
| 1097 |
// precision in a run time environment (e.g. with valgrind), so we must |
| 1098 |
// limit the tolerance to double. Since we do a Newton iteration, doing |
| 1099 |
// one more iteration after the residual has indicated convergence will be |
| 1100 |
// enough for all number types due to the quadratic convergence of |
| 1101 |
// Newton's method |
| 1102 |
|
| 1103 |
const Number tolerance = |
| 1104 |
4 * std::max(static_cast<Number>(std::numeric_limits<double>::epsilon()), |
| 1105 |
std::numeric_limits<Number>::epsilon()); |
| 1106 |
|
| 1107 |
// The following implementation follows closely the one given in the |
| 1108 |
// appendix of the book by Karniadakis and Sherwin: Spectral/hp element |
| 1109 |
// methods for computational fluid dynamics (Oxford University Press, |
| 1110 |
// 2005) |
| 1111 |
|
| 1112 |
// If symmetric, we only need to compute the half of points |
| 1113 |
const unsigned int n_points = (alpha == beta ? degree / 2 : degree); |
| 1114 |
for (unsigned int k = 0; k < n_points; ++k) |
| 1115 |
{ |
| 1116 |
// we take the zeros of the Chebyshev polynomial (alpha=beta=-0.5) as |
| 1117 |
// initial values, corrected by the initial value |
| 1118 |
Number r = 0.5 - 0.5 * std::cos(static_cast<Number>(2 * k + 1) / |
| 1119 |
(2 * degree) * numbers::PI); |
| 1120 |
if (k > 0) |
| 1121 |
r = (r + x[k - 1]) / 2; |
| 1122 |
|
| 1123 |
unsigned int converged = numbers::invalid_unsigned_int; |
| 1124 |
for (unsigned int it = 1; it < 1000; ++it) |
| 1125 |
{ |
| 1126 |
Number s = 0.; |
| 1127 |
for (unsigned int i = 0; i < k; ++i) |
| 1128 |
s += 1. / (r - x[i]); |
| 1129 |
|
| 1130 |
// derivative of P_n^{alpha,beta}, rescaled to [0, 1] |
| 1131 |
const Number J_x = |
| 1132 |
(alpha + beta + degree + 1) * |
| 1133 |
jacobi_polynomial_value(degree - 1, alpha + 1, beta + 1, r); |
| 1134 |
|
| 1135 |
// value of P_n^{alpha,beta} |
| 1136 |
const Number f = jacobi_polynomial_value(degree, alpha, beta, r); |
| 1137 |
const Number delta = f / (f * s - J_x); |
| 1138 |
r += delta; |
| 1139 |
if (converged == numbers::invalid_unsigned_int && |
| 1140 |
std::abs(delta) < tolerance) |
| 1141 |
converged = it; |
| 1142 |
|
| 1143 |
// do one more iteration to ensure accuracy also for tighter |
| 1144 |
// types than double (e.g. long double) |
| 1145 |
if (it == converged + 1) |
| 1146 |
break; |
| 1147 |
} |
| 1148 |
|
| 1149 |
Assert(converged != numbers::invalid_unsigned_int, |
| 1150 |
ExcMessage("Newton iteration for zero of Jacobi polynomial " |
| 1151 |
"did not converge.")); |
| 1152 |
|
| 1153 |
x[k] = r; |
| 1154 |
} |
| 1155 |
|
| 1156 |
// in case we assumed symmetry, fill up the missing values |
| 1157 |
for (unsigned int k = n_points; k < degree; ++k) |
| 1158 |
x[k] = 1.0 - x[degree - k - 1]; |
| 1159 |
|
| 1160 |
return x; |
| 1161 |
} |
| 1162 |
|
| 1163 |
} // namespace Polynomials |
| 1164 |
DEAL_II_NAMESPACE_CLOSE |
| 1165 |
|
| 1166 |
#endif |