1,720,998 research outputs found
Bit-Complexity of Solving Systems of Linear Evolutionary Partial Differential Equations
No full textFinite Elements are a common method for solving differential equations via discretization. Under suitable hypotheses, the solution u= u(t, x→ ) of a well-posed initial/boundary-value problem for a linear evolutionary system of PDEs is approximated up to absolute error 1 / 2 n by repeatedly (exponentially often in n) multiplying a matrix An to the vector from the previous time step, starting with the initial condition u(0 ), approximated by the spatial grid vector u(0 ) n. The dimension of the matrix An is exponential in n, which is the number of the bits of the output. We investigate the bit-cost of computing exponential powers and inner products AnK·u(0)n, K∼ 2 O(n), of matrices and vectors of exponential dimension for various classes of such difference schemes An. Non-uniformly fixing any polynomial-time computable initial condition and focusing on single but arbitrary entries (instead of the entire vector/matrix) allows to improve naïve exponential sequential runtime EXP: Closer inspection shows that, given any time 0 ≤ t≤ 1 and space x→ ∈ [ 0 ; 1 ] d, the computational cost of evaluating the solution u(t, x→ ) corresponds to the discrete class PSPACE. Many partial differential equations, including the Heat Equation, admit difference schemes that are (tensor products of constantly many) circulant matrices of constant bandwidth; and for these we show exponential matrix powering, and PDE solution computable in #P. This is achieved by calculating individual coefficients of the matrix’ multivariate companion polynomial’s powers using Cauchy’s Differentiation Theorem; and shown optimal for the Heat Equation. Exponentially powering twoband circulant matrices is established even feasible in P; and under additional conditions, also the solution to certain linear PDEs becomes computable in P. © 2021, Springer Nature Switzerland AG
Symbolic Transformations of Dynamical Models
No full textThis thesis is focused on symbolic algorithms for dynamical models defined by differential or difference equations. Such algorithms aim at complementing traditional numerical tools, they are exact and often operate on the level of symbolic expressions. In the context of differential and difference equations, perhaps the most well-known symbolic algorithms are the ones for finding closed-form solutions which are available in many scientific software packages. However, a large portion (if not majority) of the equations appearing in the modeling literature do not admit such solutions. This fact does not render the symbolic methods useless. On the contrary, there is a number of ways to transform a model on the symbolic level to facilitate its further analysis. In this thesis, we discuss the following problems of this type:- eliminating a subset of the variables (for example, the latent ones) from a model;- assessing structural identifiability of parameters, that is, checking if the parameter values can be inferred uniquely from input-output data, and transforming a model into a one with better identifiability properties; - performing exact model reduction, that is mapping a model into a one of lower dimension without introducing approximation errors; - quadratizing a model, that is embedding the model into a one with at most quadratic nonlinearities. The results we present for these problems range from theorems and theoretical algorithms to practical software implementations and case studies
Persistent components in Canny\u27s Generalized Characteristic Polynomial
Full text linkWhen using resultants for elimination, one standard issue is that the resultant vanishes if the variety contains components of dimension larger than the expected dimension. J. Canny proposed an elegant construction, generalized characteristic polynomial, to address this issue by symbolically perturbing the system before the resultant computation. Such perturbed resultant would typically involve artefact components only loosely related to the geometry of the variety of interest. For removing these components, J.M. Rojas proposed to take the greatest common divisor of the results of two different perturbations. In this paper, we investigate this construction, and show that the extra components persistent under taking different perturbations must come either from singularities or from positive-dimensional fibers
Symbolic Transformations of Dynamical Models
No full textThis thesis is focused on symbolic algorithms for dynamical models defined by differential or difference equations. Such algorithms aim at complementing traditional numerical tools, they are exact and often operate on the level of symbolic expressions. In the context of differential and difference equations, perhaps the most well-known symbolic algorithms are the ones for finding closed-form solutions which are available in many scientific software packages. However, a large portion (if not majority) of the equations appearing in the modeling literature do not admit such solutions. This fact does not render the symbolic methods useless. On the contrary, there is a number of ways to transform a model on the symbolic level to facilitate its further analysis. In this thesis, we discuss the following problems of this type:- eliminating a subset of the variables (for example, the latent ones) from a model;- assessing structural identifiability of parameters, that is, checking if the parameter values can be inferred uniquely from input-output data, and transforming a model into a one with better identifiability properties; - performing exact model reduction, that is mapping a model into a one of lower dimension without introducing approximation errors; - quadratizing a model, that is embedding the model into a one with at most quadratic nonlinearities. The results we present for these problems range from theorems and theoretical algorithms to practical software implementations and case studies
Persistent components in Canny's Generalized Characteristic Polynomial
No full textInternational audienceWhen using resultants for elimination, one standard issue is that the resultant vanishes if the variety contains components of dimension larger than the expected dimension. J. Canny proposed an elegant construction, generalized characteristic polynomial, to address this issue by symbolically perturbing the system before the resultant computation. Such perturbed resultant would typically involve artefact components only loosely related to the geometry of the variety of interest. For removing these components, J.M. Rojas proposed to take the greatest common divisor of the results of two different perturbations. In this paper, we investigate this construction, and show that the extra components persistent under taking different perturbations must come either from singularities or from positive-dimensional fibers
Structural parameter identifiability with a view towards model theory
No full textNon UBCUnreviewedAuthor affiliation: École PolytechniqueResearche
Symbolic Transformations of Dynamical Models
No full textThis thesis is focused on symbolic algorithms for dynamical models defined by differential or difference equations. Such algorithms aim at complementing traditional numerical tools, they are exact and often operate on the level of symbolic expressions. In the context of differential and difference equations, perhaps the most well-known symbolic algorithms are the ones for finding closed-form solutions which are available in many scientific software packages. However, a large portion (if not majority) of the equations appearing in the modeling literature do not admit such solutions. This fact does not render the symbolic methods useless. On the contrary, there is a number of ways to transform a model on the symbolic level to facilitate its further analysis. In this thesis, we discuss the following problems of this type:- eliminating a subset of the variables (for example, the latent ones) from a model;- assessing structural identifiability of parameters, that is, checking if the parameter values can be inferred uniquely from input-output data, and transforming a model into a one with better identifiability properties; - performing exact model reduction, that is mapping a model into a one of lower dimension without introducing approximation errors; - quadratizing a model, that is embedding the model into a one with at most quadratic nonlinearities. The results we present for these problems range from theorems and theoretical algorithms to practical software implementations and case studies
Support bound for differential elimination in polynomial dynamical systems
No full textInternational audienceWe study an important special case of the differential elimination problem: given a polynomial parametric dynamical system x' = g(\mu, x) and a polynomial observation function y = f(\mu, x), find the minimal differential equation satisfied by y. In our previous work, for the case y = x_1, we established a bound on the support of such a differential equation for the non-parametric case and shown that it can be turned into an algorithm via the evaluation-interpolation approach. The main contribution of the present paper is a generalization of the aforementioned result in two directions: to allow any polynomial function y = f(x), not just a single coordinate, and to allow g and f depend on unknown symbolic parameters. We conduct computation experiments to evaluate the accuracy of our new bound and show that the approach allows to perform elimination for some cases out of reach for the state of the art software
On the dimension of the solution space of linear difference equations over the ring of infinite sequences
No full textIn memory of Marko Petkov\v{s}ekInternational audienceFor a linear difference equation with the coefficients being computable sequences, we establish algorithmic undecidability of the problem of determining the dimension of the solution space including the case when some additional prior information on the dimension is available
Projecting dynamical systems via a support bound
No full textFor a polynomial dynamical system, we study the problem of computing the minimal differential equation satisfied by a chosen coordinate (in other words, projecting the system on the coordinate). This problem can be viewed as a special case of the general elimination problem for systems of differential equations and appears in applications to modeling and control. We give a bound for the Newton polytope of such minimal equation and show that our bound is sharp in "more than half of the cases". We further use this bound to design an algorithm for computing the minimal equation following the evaluation-interpolation paradigm. We demonstrate that our implementation of the algorithm can tackle problems which are out of reach for the state-of-the-art software for differential elimination
- …
