Fast Algorithms for Partial Fraction Decomposition

作者：H. T. Kung, Dezhong Tong · 发表于：SIAM Journal on Computing · 年份：1977 · DOI：10.1137/0206042 · 被引用次数：37 · 研究领域：Digital Filter Design and Implementation、Numerical Methods and Algorithms、Polynomial and algebraic computation

The partial fraction decomposition of a proper rational function whose denominator has degree n and is given in general factored form can be done in $O(n \log^{2}n)$ operations in the worst case. Previous algorithms require $O(n^{3})$ operations, and $O(n \log^{2}n)$ operations for the special case where the factors appearing in the denominator are all linear.