Christoph Koutschan

Christoph Koutschan, Christoph Lehrenfeld, Joachim Schoeberl

We consider the numerical discretization of the time-domain Maxwell's equations with an energy-conserving discontinuous Galerkin finite element formulation. This particular formulation allows for higher order approximations of the electric and magnetic field. Special emphasis is placed on an efficient implementation which is achieved by taking advantage of recurrence properties and the tensor-product structure of the chosen shape functions. These recurrences have been derived symbolically with computer algebra methods reminiscent of the holonomic systems approach.

Ronny Ramlau, Christoph Koutschan, Bernd Hofmann

In theory and practice of inverse problems, linear operator equations $Tx=y$ with compact linear forward operators $T$ having a non-closed range $\mathcal{R}(T)$ and mapping between infinite dimensional Hilbert spaces plays some prominent role. As a consequence of the ill-posedness of such problems, regularization approaches are required, and due to its unlimited qualification spectral cut-off is an appropriate method for the stable approximate solution of corresponding inverse problems. For this method, however, the singular system $\{σ_i(T),u_i(T),v_i(T)\}_{i=1}^\infty$ of the compact operator $T$ is needed, at least for $i=1,2,...,N$, up to some stopping index $N$. In this note we consider $n$-fold integration operators $T=J^n\;(n=1,2,...)$ in $L^2([0,1])$ occurring in numerous applications, where the solution of the associated operator equation is characterized by the $n$-th generalized derivative $x=y^{(n)}$ of the Sobolev space function $y \in H^n([0,1])$. Almost all textbooks on linear inverse problems present the whole singular system $\{σ_i(J^1),u_i(J^1),v_i(J^1)\}_{i=1}^\infty$ in an explicit manner. However, they do not discuss the singular systems for $J^n,\;n \ge 2$. We will emphasize that this seems to be a consequence of the fact that for higher $n$ the eigenvalues $σ^2_i(J^n)$ of the associated ODE boundary value problems obey transcendental equations, the complexity of which is growing with $n$. We present the transcendental equations for $n=2,3,...$ and discuss and illustrate the associated eigenfunctions and some of their properties.

Christoph Koutschan, Martin Neumüller, Cristian-Silviu Radu

In the convergence analysis of numerical methods for solving partial differential equations (such as finite element methods) one arrives at certain generalized eigenvalue problems, whose maximal eigenvalues need to be estimated as accurately as possible. We apply symbolic computation methods to the situation of square elements and are able to improve the previously known upper bound, given in "p- and hp-finite element methods" (Schwab, 1998), by a factor of 8. More precisely, we try to evaluate the corresponding determinant using the holonomic ansatz, which is a powerful tool for dealing with determinants, proposed by Zeilberger in 2007. However, it turns out that this method does not succeed on the problem at hand. As a solution we present a variation of the original holonomic ansatz that is applicable to a larger class of determinants, including the one we are dealing with here. We obtain an explicit closed form for the determinant, whose special form enables us to derive new and tight upper resp. lower bounds on the maximal eigenvalue, as well as its asymptotic behaviour.

Christoph Koutschan, Anton Ponomarchuk, Josef Schicho

Any continuous piecewise-linear function $F\colon \mathbb{R}^{n}\to \mathbb{R}$ can be represented as a linear combination of $\max$ functions of at most $n+1$ affine-linear functions. In our previous paper [``Representing piecewise linear functions by functions with small arity'', AAECC, 2023], we showed that this upper bound of $n+1$ arguments is tight. In the present paper, we extend this result by establishing a correspondence between the function $F$ and the minimal number of arguments that are needed in any such decomposition. We show that the tessellation of the input space $\mathbb{R}^{n}$ induced by the function $F$ has a direct connection to the number of arguments in the $\max$ functions.

Christoph Koutschan, Bernhard Moser, Anton Ponomarchuk et al.

A piecewise linear function can be described in different forms: as an arbitrarily nested expression of $\min$- and $\max$-functions, as a difference of two convex piecewise linear functions, or as a linear combination of maxima of affine-linear functions. In this paper, we provide two main results: first, we show that for every piecewise linear function there exists a linear combination of $\max$-functions with at most $n+1$ arguments, and give an algorithm for its computation. Moreover, these arguments are contained in the finite set of affine-linear functions that coincide with the given function in some open set. Second, we prove that the piecewise linear function $\max(0, x_{1}, \ldots, x_{n})$ cannot be represented as a linear combination of maxima of less than $n+1$ affine-linear arguments. This was conjectured by Wang and Sun in 2005 in a paper on representations of piecewise linear functions as linear combination of maxima.

Matteo Gallet, Christoph Koutschan, Zijia Li et al.

Designing mechanical devices, called linkages, that draw a given plane curve has been a topic that interested engineers and mathematicians for hundreds of years, and recently also computer scientists. Already in 1876, Kempe proposed a procedure for solving the problem in full generality, but his constructions tend to be extremely complicated. We provide a novel algorithm that produces much simpler linkages, but works only for parametric curves. Our approach is to transform the problem into a factorization task over some noncommutative algebra. We show how to compute such a factorization, and how to use it to construct a linkage tracing a given curve.