Debian Codegraph @

include/deal.II/base/polynomial.h

raw
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&eacute;d&eacute;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>&nbsp;</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