A Practical Framework for Infinite-Dimensional Linear Algebra
A Practical Framework for Infinite-Dimensional Linear Algebra
复制标题
无限维线性代数的实用框架
DOI：
10.1109/hptcdl.2014.10
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Alex Townsend
中科院分区：
文献类型：
--
作者：
S. Olver;Alex Townsend
我们描述了一个用于求解一大类无限维线性方程的框架，该框架由几乎带状算子组成，可用于表示具有一般边界条件的线性常微分方程。该框架包含可以执行行运算的数据结构，允许通过自适应 QR 方法求解无限维线性方程。该算法实现了 O(nopt) 复杂度，其中 nopt 是实现所需精度所需的自由度数，该精度是自适应确定的。此外，特殊的张量积方程，例如矩形上的偏微分方程，可以通过在 y 方向上截断具有 ny 自由度的算子并使用广义 Schur 分解进行上三角化来求解，然后将自适应 QR 方法应用于 x 方向，需要 O(n3y + n2ynoptx) 运算。该框架是在用 Julia 编程语言编写的 ApproxFun 包中实现的，它通过利用 Julia 的独特功能实现了极具竞争力的计算成本。使用该框架，可以在不到 4 秒的时间内求解需要多达 250 万个未知数的偏微分方程。
We describe a framework for solving a broad class of infinite-dimensional linear equations, consisting of almost banded operators, which can be used to representing linear ordinary differential equations with general boundary conditions. The framework contains a data structure for on which row operations can be performed, allowing for the solution of infinite-dimensional linear equations by the adaptive QR approach. The algorithm achieves O(nopt) complexity, where nopt is the number of degrees of freedom required to achieve a desired accuracy, which is determined adaptively. In addition, special tensor product equations, such as partial differential equations on rectangles, can be solved by truncating the operator in the y-direction with ny degrees of freedom and using a generalized Schur decomposition to upper triangularize, before applying the adaptive QR approach to the x-direction, requiring O(n3y + n2ynoptx) operations. The framework is implemented in the ApproxFun package written in the Julia programming language, which achieves highly competitive computational costs by exploiting unique features of Julia. Using this framework, partial differential equations that require as many as 2.5 million unknowns can be solved in less than 4 seconds.