Bit-Complexity of Solving Systems of Linear Evolutionary Partial Differential Equations
Bit-Complexity of Solving Systems of Linear Evolutionary Partial Differential Equations
复制标题
线性进化偏微分方程组求解的位复杂度
DOI：
10.1007/978-3-030-79416-3_13
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Ziegler, M.
中科院分区：
文献类型：
--
作者：
Koswara, I.;Pogudin, G.;Selivanova, S.;Ziegler, M.
有限元是通过离散化求解微分方程的一种常用方法。在适当的假设下，线性偏微分方程组的适定初边值问题的解可以通过重复地(通常是指数地)将一个矩阵与由空间网格向量逼近的前一个时间步中的向量相乘而逼近到绝对误差。矩阵的维度是指数空间，它是输出的位数。我们研究了不同类型的这类差分格式计算指数维矩阵和向量的指数幂和内积的比特开销。不一致地固定任何多项式时间可计算的初始条件，并集中于单个但任意的项(而不是整个向量/矩阵)允许改进朴素的指数序列运行时间EXP：更仔细的检查表明，在任何时间和空间，求解的计算成本对应于离散类PSPACE。许多偏微分方程组，包括热方程，承认差分格式是(恒定多个)恒定带宽的循环矩阵的张量积；对于这些，我们证明了指数矩阵的幂，并且PDE解在#P中是可计算的，这是通过利用柯西微分定理计算矩阵的多元伴随多项式的幂的单个系数来实现的；并显示了热方程的最佳值。建立了指数幂的两带循环矩阵，即使是可行的INP；在附加条件下，某些线性偏微分方程组的解也是可计算的INP。
Finite Elementsare a common method for solving differential equations via discretization. Under suitable hypotheses, the solutionof a well-posed initial/boundary-value problem for a linear evolutionary system of PDEs is approximated up to absolute errorby repeatedly (exponentially often inn) multiplying a matrixto the vector from the previous time step, starting with the initial condition, approximated by the spatial grid vector. The dimension of the matrixis exponential inn, which is the number of the bits of the output.We investigate the bit-cost of computing exponential powers and inner products,, of matrices and vectors of exponential dimension for various classes of suchdifference schemes. 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 runtimeEXP: Closer inspection shows that, given any timeand space, the computational cost of evaluating the solutioncorresponds to the discrete classPSPACE.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 inP; and under additional conditions, also the solution to certain linear PDEs becomes computable inP.
登录
查看更多内容
求解无界域上多项式时间内的解析微分方程
DOI：
--
发表时间：
2011
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
Olivier Bournez;D. Graça;Amaury Pouly
通讯作者：
Amaury Pouly
Lipschitz 连续常微分方程是多项式空间完备的
DOI：
--
发表时间：
2009
期刊：
2009 24th Annual IEEE Conference on Computational Complexity
影响因子：
--
作者：
A. Kawamura
通讯作者：
A. Kawamura
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
M. Epstein
通讯作者：
M. Epstein
偏微分方程对称双曲系统计算解的位复杂度（扩展摘要）
DOI：
--
发表时间：
2018
期刊：
Conference on Computability in Europe
影响因子：
--
作者：
S. Selivanova;V. Selivanov
通讯作者：
V. Selivanov
具有可计算初始数据的波动方程，其唯一解不可计算
影响因子：
1.7
作者：
M. B. Pour;I. Richards
通讯作者：
I. Richards