Parallelization of the Rational Arnoldi Algorithm
Parallelization of the Rational Arnoldi Algorithm
复制标题
Rational Arnoldi 算法的并行化
DOI：
--
复制
发表时间：
2017
影响因子：
3.1
通讯作者：
S. Güttel
中科院分区：
文献类型：
--
作者：
Mario Berljafa;S. Güttel
有理Krylov方法适用于广泛的科学计算问题，并且有理Arnoldi算法是用于计算有理Krylov空间的标准正交基的常用程序。通常，该算法的计算上最昂贵的组件是在每次迭代时求解大型线性方程组。我们探讨的选择，同时解决几个线性系统，从而并行构建合理的Krylov基础。如果不仔细地做这件事，被正交化的基可能变得条件不良，导致正交化过程中的数值不稳定性。我们引入了新的概念，连续对产生一个接近最佳的并行化策略，允许控制增长的条件数的非正交基础。因此，我们获得了更加准确和可靠的并行有理Arnoldi算法。使用几个数值例子从不同的应用领域的计算效益。
Rational Krylov methods are applicable to a wide range of scientific computing problems, and the rational Arnoldi algorithm is a commonly used procedure for computing an orthonormal basis of a rational Krylov space. Typically, the computationally most expensive component of this algorithm is the solution of a large linear system of equations at each iteration. We explore the option of solving several linear systems simultaneously, thus constructing the rational Krylov basis in parallel. If this is not done carefully, the basis being orthogonalized may become badly conditioned, leading to numerical instabilities in the orthogonalization process. We introduce the new concept of continuation pairs which gives rise to a near-optimal parallelization strategy that allows to control the growth of the condition number of this nonorthogonal basis. As a consequence we obtain a significantly more accurate and reliable parallel rational Arnoldi algorithm. The computational benefits are illustrated using several numerical examples from different application areas.