Bit-Complexity of Solving Systems of Linear Evolutionary Partial Differential Equations

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 95
  • Download : 0
Finite 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.
Publisher
Springer Science and Business Media Deutschland GmbH
Issue Date
2021-07
Language
English
Citation

16th International Computer Science Symposium in Russia, CSR 2021, pp.223 - 241

ISSN
0302-9743
DOI
10.1007/978-3-030-79416-3_13
URI
http://hdl.handle.net/10203/288647
Appears in Collection
CS-Conference Papers(학술회의논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0