Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming seminars




Seminars "Proof Theory" and "Logic Online Seminar"
February 13, 2023 18:30, Moscow, Steklov Mathematical Institute (8 Gubkina), room 313 + Zoom
 


Bit-Complexity of Classical Solutions of Linear Evolutionary Systems of Partial Differential Equations

Martin Ziegler

Korea Advanced Institute of Science and Technology
Video records:
MP4 262.1 Mb

Number of views:
This page:166
Video files:21



Abstract: We study the bit-complexity intrinsic to solving the initial-value and (several types of) boundary-value problems for linear evolutionary systems of partial differential equations (PDEs), based on the Computable Analysis approach. Our algorithms are guaranteed to compute classical solutions to such problems approximately up to error $1/2^n$, so that $n$ corresponds to the number of reliable bits of the output; bit-cost is measured with respect to $n$.
Computational Complexity Theory allows us to prove in a rigorous sense that PDEs with constant coefficients are algorithmically ‘easier’ than general ones. Indeed, solutions to the latter are shown (under natural assumptions) computable using a polynomial amount of memory, and we prove that the complexity class PSPACE is in general optimal; while the case of constant coefficients can be solved in #P – also essentially optimally so: the Heat Equation ‘requires’ #P1.
Our algorithms raise difference schemes to exponential powers, efficiently: we compute any desired entry of such a power in #P, provided that the underlying exponential-sized matrices are circulant of constant bandwidth. Exponentially powering modular two-band circulant matrices is established even feasible in PTIME; and under additional conditions, also the solution to certain linear PDEs becomes polynomial-time computable.

Language: English
Series of reports
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024