Multistep and Multistage Convolution Quadrature for the Wave Equation: Algorithms and Experiments
Multistep and Multistage Convolution Quadrature for the Wave Equation: Algorithms and Experiments
复制标题
波动方程的多步和多级卷积求积：算法和实验
DOI：
10.1137/090775981
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
L. Banjai
中科院分区：
文献类型：
--
作者：
L. Banjai
我们描述了如何在均匀介质中的时间离散波动方程可以解决边界积分方法。时间离散化可以是多步、龙格-库塔或更一般的多步-多级方法。由此产生的卷积系统的边界积分方程属于家庭的卷积求积的卢比希。这项工作的目的是双重的。它描述了一种高效，鲁棒，易于并行化的方法来解决半离散系统。所得算法具有时间步进方法和傅里叶合成的主要优点：在每个时间步，需要求解具有相同系统矩阵的线性方程组，但计算可以很容易地并行进行;计算成本几乎与时间步数成线性关系;并且只需要对时域基本解进行拉普拉斯变换。该算法的新方面是，所有这一切都是可能的，而无需显式地构造卷积求积的权重。这种方法也很容易允许使用现代数据稀疏技术来有效地执行空间计算。我们从理论上和数值上研究在何种程度上层次矩阵（$\mathcal H$-矩阵）技术可以用来加快空间计算。本文的第二个目的是进行一系列大规模的3D实验与一系列的多步和多级时间离散方法：向后差分公式的顺序2（BDF 2），梯形规则，和3阶段Radau IIA方法进行了详细研究。实验的结论之一是，Radau IIA方法通常比线性多步法表现得更好，特别是对于具有许多反射的问题，然而，与双曲问题有关，BDF迄今为止在卷积求积的文献中占主导地位。
We describe how a time-discretized wave equation in a homogeneous medium can be solved by boundary integral methods. The time discretization can be a multistep, Runge-Kutta, or a more general multistep-multistage method. The resulting convolutional system of boundary integral equations belongs to the family of convolution quadratures of Lubich. The aim of this work is twofold. It describes an efficient, robust, and easily parallelizable method for solving the semidiscretized system. The resulting algorithm has the main advantages of time-stepping methods and of Fourier synthesis: at each time-step, a system of linear equations with the same system matrix needs to be solved, yet computations can easily be done in parallel; the computational cost is almost linear in the number of time-steps; and only the Laplace transform of the time-domain fundamental solution is needed. The new aspect of the algorithm is that all this is possible without ever explicitly constructing the weights of the convolution quadrature. This approach also readily allows the use of modern data-sparse techniques to efficiently perform computation in space. We investigate theoretically and numerically to which extent hierarchical matrix ($\mathcal H$-matrix) techniques can be used to speed up the space computation. The second aim of this article is to perform a series of large-scale 3D experiments with a range of multistep and multistage time discretization methods: the backward difference formula of order 2 (BDF2), the Trapezoid rule, and the 3-stage Radau IIA methods are investigated in detail. One of the conclusions of the experiments is that the Radau IIA method often performs overwhelmingly better than the linear multistep methods, especially for problems with many reflections, yet, in connection with hyperbolic problems, BDFs have so far been predominant in the literature on convolution quadrature.