A uniform approach for the fast computation of Matrix-type Pad'e approximants
A uniform approach for the fast computation of Matrix-type Pad'e approximants
复制标题
矩阵型Pade近似快速计算的统一方法
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. G. Bruin
中科院分区：
文献类型：
--
作者：
M. G. Bruin
最近，为基质型垫E近似值的不同概念提供了一种均匀的方法，例如对载体和矩阵垫E近似值的描述以及同时和赫米特垫E近似值的概括。本文中的考虑是基于这种经典标量HERMITE PAD E近似问题的广义形式，功率Hermite Pad E近似。特别是我们研究计算这些新近似值的问题。提出了复发关系，以计算这些近似值的相应线性解空间的基础。这种复发还为特定子问题提供了基础。这概括了范·巴雷尔（Van Barel）和邦泰（Bultheel）的先前工作，并以更通用的形式概括了贝克曼（Beckermann）。基础的计算具有复杂性o（2），其中所需的近似值的顺序，并且不需要输入数据的条件。还提出了第二种使用相同复发关系以及分裂和诱使方法的算法。当COE Cient ELD允许快速多项式乘法时，第二种算法将计算超快速复杂性O（log 2）中的基础。在这两种情况下，算法在精确的算术中都是可靠的，也就是说，它们永远不会分解，复杂性既不取决于任何正态性假设，也不取决于相应的解决方案表的奇异结构。作为进一步的应用，我们的方法导致了逆转条纹Hankel，分层Hankel和（矩形）块 - 储物基矩阵的快速（和超快），可靠的算法。
Recently, a uniform approach was given [5] for di erent concepts of matrix-type Pad e approximants, such as descriptions of vector and matrix Pad e approximants along with generalizations of simultaneous and Hermite Pad e approximants. The considerations in this paper are based on this generalized form of the classical scalar Hermite Pad e approximation problem, power Hermite Pad e approximation. In particular we study the problem of computing these new approximants. A recurrence relation is presented for the computation of a basis for the corresponding linear solution space of these approximants. This recurrence also provides bases for particular subproblems. This generalizes previous work by Van Barel and Bultheel and, in a more general form, by Beckermann. The computation of the bases has complexity O( 2 ) where is the order of the desired approximant, and requires no conditions on the input data. A second algorithm using the same recurrence relation along with divide-and-conquer methods is also presented. When the coe cient eld allows for fast polynomial multiplication this second algorithm computes a basis in the superfast complexity O( log 2 ). In both cases the algorithms are reliable in exact arithmetic, that is, they never break down, and the complexity depends neither on any normality assumptions nor on the singular structure of the corresponding solution table. As a further application, our methods result in fast (and superfast), reliable algorithms for the inversion of striped Hankel, layered Hankel and (rectangular) block-Hankel matrices.