1. High Order Finite Elements
Basis functions minimizing the condition number.
In [1] the construction
of basis functions minimizing the iteration number is
described. The resulting shape functions are
compositions of certain orthogonal polynomials involving
integration and linear combinations. Using his symbolic
summation package Sigma [11] C. Schneider
derived recurrence relations allowing an efficient
computation of the functions .
Inner shape functions using integrated Jacobi
polynomials.
In [2] shape functions for
triangular -FEM
are described which are constructed using products of
specific Jacobi polynomials The parameters
are chosen to obtain a sparse system matrix in the case of a
constant coefficient function and a polygonally bounded
domain. For the case of a curved domain or a non constant
coefficient function an efficient preconditioner is derived.
The idea of this design was carried over to tetrahedral
finite elements. To obtain the correct parameters in
the definition of the basis functions and especially to prove
the sparsity of the system matrix, the assistance of computer
algebra software was needed.
With a Mathematica program we proved the nonzero pattern of
the interior block of the system matrix, i.e.,
Currently we are investigating the numerical properties of
these basis functions as well as the construction of an
efficient preconditioner for the system matrix.
A Mathematica FEM package.
In order to have a platform for numerical-symbolic
interaction V. Pillwein developed the Mathematica
package Fem2D. Within this program the RISC symbolic
summation package (including Sigma,
MultiSum, ...) can be invoked directly.
Orthogonal polynomials, which are widely used in the design of fe-basis functions, can be represented in different ways such as using their recursive description or hypergeometric sum representation. In a symbolic framework one can exploit this variety and study the benefits of different representations.
In the example described above, carefully chosen Jacobi polynomials were used in the construction of new shape functions. The Mathematica FEM package allows to generalize this idea to a systematic application of CA in the designing process. In Fem2D it is possible to implement families of basis functions leaving some parameters unknown, which are later specified according to desired numerical properties.
2. Symbolic Integration of Special Functions
The particular need within F1301 for a symbolic integration algorithm that can do definite integrals arising in connection with high order finite element methods such as
involving Jacobi polynomials led B. Zimmermann to a new symbolic algorithm for doing definite integrals of a large class of special functions that depend on a discrete parameter.
A function is called elementary if it is obtained by composing exponentials, logarithms, algebraic functions, and field operations. Risch gave a complete algorithm for the symbolic integration of elementary functions. Given an elementary function , it decides if an elementary function exists such that . If such a exists, it returns it. Note that Risch's algorithm does not apply to integrals such as (1) for two reasons. First, the Jacobi polynomials appearing in (1) are not elementary (when is undetermined); in fact, most of the classical special functions from mathematical physics are not elementary. Second, Risch's algorithm is restricted to indefinite integration problems, while (1) is definite.
A recent algorithm that applies to a wide class of non-elementary special functions is Manuel Bronstein's Poor Man's Integrator [3]. It is a variant of Risch-Norman's parallel integration method, based on a new structure theorem of Manuel Bronstein.
Within the frame of F1301, B. Zimmermann extended Bronstein's Poor Man's Integrator to definite integration problems where the integrand depends on a discrete parameter . Given such an integrand and a natural number , his algorithm looks for coefficients and a function such that
this relation implies the linear recurrence
Zimmermann's extension of the Poor Man's Integrator is inspired by Doron Zeilberger's extension of Gosper's algorithm for hypergeometric summation (Zeilberger's algorithm). The same method was used by C. Schneider [11] in his extension of Karr's summation algorithm to definite summation. In all three cases, the key is to observe that the underlying algorithm has the special property that it can be applied to an input , where , ..., are initially undetermined coefficients and , ..., are given. These coefficients show up as additional variables in the linear equation system which the underlying algorithm solves. That way, the underlying algorithm determines them, in addition to determining a suitable such that . To find recurrences for integrals, one uses this with for .
The new algorithm works in a field of of rational functions where with a field. is endowed with a shift and a derivation , which commute with each other, and such that the field of constants of is and that is in the field of constants of . Each indeterminate corresponds to some term which possibly involves and , the shift corresponds to the shift , and the derivation corresponds to the partial derivative . For any P-finite function one can construct such a suitable field which models the field of functions generated by all the shift-derivatives of . Given in , the new algorithm returns a basis for the -vector space of all such that and is an elementary extension of the differential field . As the algorithm is based on Bronstein's heuristic Poor Man's Integrator, it may, in rare occasions, return a basis for a proper subspace of this -vector space.
So far, the best computer algebra methods for definite symbolic integration of special functions were based on elimination in Ore Algebras by Gröbner basis methods (e.g. [4])). These methods are restricted to P-finite integrands, and they are known to terminate for the class of holonomic integrands, which form a subclass of the class of P-finite integrands. While Zimmermann's extension also handles any P-finite integrand and terminates on holonomic input, it can handle a wider class of inputs. The class of inputs which it can handle is closed under composition - unlike the class of P-finite functions. It contains certain non-P-finite functions such as the tangent function and Lambert's function.
The new algorithm is not yet published; it will appear in
a forthcoming Ph.D. thesis [13].
3. Applications of Gröbner Bases
3.1 Implementations of Gröbner Bases
In the algebraic treatment of systems of equations involving linear operators (like partial differentiation, partial difference and so on), the choice of coefficient domain leads us to different algebraic structures. For the case of constant (scalar) coefficients, the underlying system algebra is commutative. If the coefficients are polynomial in the variables of the system, we obtain a non-commutative -algebra (e.g. [8]). Numerous algorithms, based on Gröbner bases for these two cases, are implemented in the specialized Computer Algebra System SINGULAR [7]. The system is freely available for the non-commercial use and, moreover, is widely known for its performance. In 2004, the SINGULAR team was awarded with the Richard D. Jenks Memorial Prize for Excellence in Software Engineering for Computer Algebra. The non-commutative subsystem SINGULAR:PLURAL [6] handles the algebras arising from systems with polynomial coefficients, including algebras with additional polynomial identities. For example, the algebra of linear differential operators with polynomial coefficients in trigonometric functions is realized as a factor algebra. Let be the algebra generated by over subject to the relations , and . Then, we consider the two-sided ideal , compute its two-sided Gröbner basis (which is just in this case) and pass to the factor algebra , where the further computations will take place.
Generalization of Gröbner Bases.
In order to treat the case of rational functions in the
variables as the coefficient domain, we employ the notion of
an Ore localization. Our aims are to extend the
Gröbner bases theory to the Ore-localized -algebras, not
restricting ourselves to the case of so-called Ore
algebras ([4], [5]), to investigate the criteria
for discarding the critical pairs and to implement
efficiently Gröbner bases and related algorithms
(involving advanced ones as in e.g. [8]) in the framework of
SINGULAR. One of the most important tasks is
to provide powerful algorithms and their efficient
implementation for the complicated arithmetics over rings of
quotients of non-commutative domains.
Intercommunication packages.
With the help of recent packages, the fast and functionally
rich implementation of algorithms, relying on Gröbner
bases in SINGULAR, became available to the
general purpose systems. The package, allowing
MATHEMATICA to exchange data and to call
SINGULAR externally, is being developed by
Manuel Kauers, F1305.
3.2 Symbolic Generation and Stability Analysis of Finite Difference Schemes
For the linear PDEs with constant coefficients the process of generating finite difference schemes may be performed symbolically, with the help of Gröbner bases for submodules of free modules over a commutative polynomial ring. We propose a more efficient method than the one proposed in [12]. Our method can be applied, in particular, for higher spatial dimensions without significant loss of performance. It can be shown that applying several symbolic approaches we are able to reproduce all the classical finite difference schemes. The input data consist of equations and corresponding approximation rules for the partial derivatives, written in terms of polynomials in partial difference operators like , where for discrete indices .
For the equation with some initial conditions, we apply the 2nd order central approximations for both and in the vector operator form, e. g. . With this symbolic data we form a submodule of a free module involving partial difference operators. By using Gröbner bases, we eliminate certain module components from a given module and obtain a submodule, corresponding to the operators, which depend only on and not on its derivatives.
We denote , and obtain the scheme, written in terms of operators,
Using specially developed visualization tools (e. g. a SINGULAR library discretize.lib), in a semi-automatic way we are able to present the scheme above in the more convenient nodal form, namely as
With our methods we are able to generate all the classical linear schemes (as it has been noted in [12]) as well as more complicated schemes, including the schemes with parametric switches.
Using the efficient implementation of Gröbner bases, these 1-dimensional examples both in time and space can be computed in seconds.
Von Neumann Stability Analysis.
Also, the investigation of von Neumann stability of a given
finite difference scheme can be done by symbolic methods.
Moreover, for (un-)conditionally stable schemes we can
perform the dispersion analysis. For both applications the
system SINGULAR is used for polynomial
computations, mappings and the translation of the output to
the special (nodal) form, used in the literature on finite
difference schemes. MATHEMATICA is used for
computing the Cylindrical Algebraic Decomposition, arising in
the final stage of both stability and dispersion
analysis.
In the example above, we employ the stability morphism from the ring , sending and to the ring . Here, and for some . After the purely algebraic simplification in the ring , we obtain the stability polynomial in one variable , where . A scheme given by a polynomial in one variable is von Neumann stable, if the modulus of every root is at most 1. In our example, the stability polynomial has roots . If , the absolute value of one of the roots is bigger than one. If , the modulus of both roots is equal to 1. Moreover, . Hence, the investigated scheme is conditionally stable with the condition for the Courant number .
We are going to apply the developed methods for finite difference schemes in cases of higher spatial dimensions, for systems of multidimensional equations, for two-step schemes like Lax-Wendroff etc.
A very important direction of further research (discussed
with Prof. W. Zulehner, F1306) is to elaborate the
conditions for boundary value problems, for which von Neumann
stability (which can be checked by symbolic methods as we
have sketched above) implies the numerical stability.
3.3 Control Theory
Algebraic Analysis.
Given a module over
an algebra , we
can present it as a sum , where is a torsion submodule of and a torsion-free
submodule. In Control Theory, there is a correspondence
between this presentation and the decomposition of a system
into a controllable part (torsion-free submodule) and an
autonomous part (torsion submodule). For systems of
equations, involving linear operators, the torsion submodule
can be described and computed with the help of homological
algebra [5], which in turn
depend heavily (both algorithmically and in the
implementation) on Gröbner bases.
The methods of algebraic analysis, applied to the problems of Control Theory, have been implemented for the case of constant coefficients [9] in the library control.lib for the system SINGULAR [7]. The development of the generalization to the case of variable coefficients is in progress. It relies on the implementation of Gröbner bases in the system SINGULAR:PLURAL [6] and on the library for non-commutative homological algebra.
Genericity of Parameters.
In systems, containing parameters, it often happens that some
structural properties, like controllability or autonomy, hold
only for the generic case, that is, for almost all
values of parameters. It means, there might exist such values
of parameters that, e.g. a generically controllable
system, specialized at these values, becomes
non-controllable. We provide an algorithmic way to detect
such and similar phenomena, which we call the genericity
violation. The results for 1-dimensional systems appear
in [10], while in the future
we concentrate on the general situation.
Bibliography
- 1
- A. BECIROVIC, P. PAULE,
V. PILLWEIN, A. RIESE, C.
SCHNEIDER, AND J.
SCHÖBERL.
Hypergeometric Summation Methods for High Order Finite Elements.
Tech. Rep. 2006-8, SFB F013, J. Kepler University Linz, 2006. - 2
- BEUCHLER, S., AND
SCHÖBERL, J.
New shape functions for triangular -FEM using integrated Jacobi polynomials.
Num. Mathematik (2006).
to appear. - 3
- BRONSTEIN, M.
Symbolic Integration I (Transcendental Functions), 2nd ed.
Springer, 2005. - 4
- CHYZAK, F. AND
SALVY, B.
Non-commutative Elimination in Ore Algebras Proves Multivariate Identities.
J. Symbolic Computation 26, 2 (1998), 187-227. - 5
- CHYZAK, F., QUADRAT, A.
AND ROBERTZ, D.
Linear control systems over Ore algebras. Effective algorithms for the computation of parametrizations.
In Proc. TDS'03 (2003), INRIA. - 6
- GREUEL, G.-M.,
LEVANDOVSKYY, V., AND
SCHÖNEMANN H.
PLURAL, a SINGULAR 3.0 Subsystem for Computations with Non-commutative Polynomial Algebras. University of Kaiserslautern, 2005. - 7
- GREUEL, G.-M., PFISTER
G., AND SCHÖNEMANN H.
SINGULAR 3.0. A Computer Algebra System for Polynomial Computations. Centre for Computer Algebra, University of Kaiserslautern, 2005.
Available from http://www.singular.uni-kl.de. - 8
- LEVANDOVSKYY, V.
Intersection of Ideals with Non-commutative Subalgebras.
Tech. Rep. 2006-14, SFB F013, J. Kepler University Linz, 2006. - 9
- LEVANDOVSKYY, V. AND
ZERZ, E.
Computer algebraic methods for the structural analysis of linear control systems.
PAMM 5 (2005), 717-718. - 10
- LEVANDOVSKYY, V. AND
ZERZ, E.
Algebraic systems theory and computer algebraic methods for some classes of linear control systems.
In Proc. MTNS'06 (2006).
to appear. - 11
- SCHNEIDER, C.
A new Sigma approach to multi-summation.
Advances in Applied Math. 34, 4 (2005), 740-767. - 12
- V. P. GERDT, Y. A. BLINKOV,
AND V. V. MOZZHILKIN.
Gröbner Bases and Generation of Difference Schemes for Partial Differential Equations.
SIGMA 2 (2006), 051. - 13
- ZIMMERMANN, B.
Symbolic Definite Integration and Summation of Special Functions.
PhD thesis, RISC, J. Kepler University Linz, 2006.
In preparation.
SpezialForschungsBereich SFB F013 | Special Research Program of the FWF - Austrian Science Fund