DC Field | Value | Language |
---|---|---|
dc.contributor.author | Koswara, Ivan | ko |
dc.contributor.author | Pogudin, Gleb | ko |
dc.contributor.author | Selivanova, Svetlana | ko |
dc.contributor.author | Ziegler, Martin | ko |
dc.date.accessioned | 2023-04-10T09:00:46Z | - |
dc.date.available | 2023-04-10T09:00:46Z | - |
dc.date.created | 2023-04-10 | - |
dc.date.created | 2023-04-10 | - |
dc.date.issued | 2023-06 | - |
dc.identifier.citation | JOURNAL OF COMPLEXITY, v.76 | - |
dc.identifier.issn | 0885-064X | - |
dc.identifier.uri | http://hdl.handle.net/10203/306087 | - |
dc.description.abstract | We study the bit-complexity intrinsic to solving the initial-value and (several types of) boundary-value problems for linear evolu-tionary 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/2n, so that n corresponds to the number of reliable bits of the output; bit-cost is measured with respect to n. Computa-tional 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 (un-der natural assumptions) computable using a polynomial number of memory bits, 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 're-quires' #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 P; and under additional conditions, also the solution to certain linear PDEs becomes polynomial time computable. (c) 2023 Elsevier Inc. All rights reserved. | - |
dc.language | English | - |
dc.publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE | - |
dc.title | Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations | - |
dc.type | Article | - |
dc.identifier.wosid | 000954986800001 | - |
dc.identifier.scopusid | 2-s2.0-85148754256 | - |
dc.type.rims | ART | - |
dc.citation.volume | 76 | - |
dc.citation.publicationname | JOURNAL OF COMPLEXITY | - |
dc.identifier.doi | 10.1016/j.jco.2022.101727 | - |
dc.contributor.localauthor | Ziegler, Martin | - |
dc.contributor.nonIdAuthor | Koswara, Ivan | - |
dc.contributor.nonIdAuthor | Pogudin, Gleb | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Reliable computing | - |
dc.subject.keywordAuthor | Bit-cost | - |
dc.subject.keywordAuthor | Partial differential equations | - |
dc.subject.keywordAuthor | PSPACE | - |
dc.subject.keywordPlus | COMPUTATIONAL-COMPLEXITY | - |
dc.subject.keywordPlus | COMPUTABILITY | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.