# h-Adic Polynomials and Partial Fraction Decomposition of Proper Rational Functions over R or C

Authors: Kwang Hyun Kim; Xin Zhang
Journal: International Journal of Mathematics and Mathematical Sciences
 (2018)

---

## Abstract

The partial fraction decomposition technique is very useful in many areas including mathematics and engineering. In this paper we present a new and simple method on the partial fraction decomposition of proper rational functions which have completely factored denominators overR or C. The method is based on a recursive computation of the h-adic polynomial in commutative algebra which is a generalization of the Taylor polynomial. Since its computation requires only simple algebraic operations, it does not require a computer algebra system to be programmed.


---

## Body

## 1. Introduction

LetF be R or C and R
=
F
[
x
] be a polynomial ring with the coefficients in F. We also assume the rational function to be proper (i.e., the degree of denominator is greater than the degree of numerator) with the denominator factored completely over F. Now, we will show how to apply our method to the following partial fraction decomposition over F
=
C:(1)
1
x
3
x
-
1
2
=
p
x
x
3
+
q
x
x
-
1
2
.We multiply through by the least common denominator to clear the fractions:(2)
1
=
p
x
x
-
1
2
+
q
x
x
3
,
p
x
≡
1
x
-
1
2
m
o
d
x
3
.Since R
/
x
3
≅
F
x
/
x
3, we can replace p
(
x
) with a power series in F
x. From Proposition 6(a) which we will prove later, we get(3)
1
x
-
1
2
=
1
+
2
x
+
3
x
2
+
⋯
∈
F
x
,
p
x
≡
1
+
2
x
+
3
x
2
m
o
d
x
3
.Since we have d
e
g
(
p
)
<
d
e
g
(
x
3
), p
(
x
) is equal to 1
+
2
x
+
3
x
2, which is the Taylor polynomial of order 2 for 1
/
(
x
-
1
)
2 at x
=
0. Similarly, q
(
x
) is the Taylor polynomial of order 1 for 1
/
x
3 at x
=
1 and we obtain(4)
q
x
=
1
-
3
x
-
1
.Hence(5)
1
x
3
x
-
1
2
=
1
+
2
x
+
3
x
2
x
3
+
1
-
3
x
-
1
x
-
1
2
=
1
x
3
+
2
x
2
+
3
x
+
1
x
-
1
2
+
-
3
x
-
1
.In [1], Ma et al. explained several recent approaches of pfd (partial fraction decomposition) and introduced a fast recursive method of pfd over C. Our method is more algebraic and works for pfd of any proper rational functions over R or C by extending the concept of Taylor polynomials into h-adic polynomials.


## 2.h-Adic Polynomials and Main Theorem

In this section we introduce the completion of a commutative ring which is useful in commutative algebra and algebraic geometry. We also define theh-adic polynomial of order n.Definition 1 (ch. 10 in [3]).
For any commutative ringR with unity and a proper ideal I of R, the completion of R with respect to I is(6)
R
^
I
≔
l
i
m
⟵
R
I
i
=
c
=
c
0
,
c
1
,
…
∈
∏
i
∈
N
R
I
i
∣
c
i
-
1
=
π
i
c
iwith the quotient maps π
i
:
R
/
I
i
+
1
→
π
i
R
/
I
i. We also use R
^
h if I
=
h with h
∈
R.IfR
=
F
[
x
] with a maximal ideal m
=
x, then R
^
x
≅
F
x is the ring of formal power series. For R
=
Z with a prime ideal p
=
p, R
^
p is Z
p, the ring of p-adic integers. Now we will define the h-adic polynomial of order n, which is crucial for our method.Lemma 2 (h-adic expansion and h-adic polynomial of order n).
Leth be an irreducible polynomial in R
=
F
[
x
] with deg
⁡
(
h
)
⩾
1 and h be the corresponding maximal ideal. Then, consider the following:(a)
The natural mapR
↪
R
^
h via r
→
r
^
=
(
r
,
r
,
r
,
…
) is injective and factors through the localization R
h
=
f
/
g
∣
g
∉
h of R at the maximal ideal h to R
^
h.(7)
(b)
R
↪
R
^
h induces(8)
R
h
n
R
≅
R
h
h
n
R
h
≅
R
^
h
h
n
R
^
h
,
w
h
e
r
e
n
∈
N
.
(c)
Forc
∈
R
^
h, there exists the unique h
-adic expansion
P
(
c
,
h
)
∈
R
^
h such that(9)
c
=
P
c
,
h
≔
a
0
,
a
0
+
a
1
h
,
…
,
∑
i
=
0
n
a
i
·
h
i
,
…
∈
R
^
h
,
wherea
i
∈
R is a polynomial with deg
⁡
(
a
i
)
<
deg
⁡
(
h
).Definition 3.
Forc
∈
R
^
h, f
/
g
∈
R
h, and r
∈
R, we define the h-adic polynomial of order
n for c, f
/
g, and r, respectively, as(10)
P
n
c
,
h
≔
P
c
,
h
n
=
∑
i
=
0
n
a
i
·
h
i
∈
R
,
P
n
f
g
,
h
≔
P
n
f
g
^
,
h
,
P
n
r
,
h
≔
P
n
r
^
,
h
.Proof.
(a) is true by the Krull intersection theorem for Noetherian domains (Corollary  10.18 in [3]) and (22.13) in [4]. (b) is true from Proposition  10.15 in [3].
Case (c). For c
=
(
c
0
,
c
1
,
…
)
∈
R
^
h
⊂
R
/
h
×
R
/
h
2
×
⋯, let c
n
′ be a representative of c
n in R. Now we will use induction on n. For n
=
0, let a
0 be the remainder of c
0
′
÷
h. Then a
0 is independent of choice of c
0
′, c
0
≡
a
0
m
o
d
h, and d
e
g
(
a
0
)
<
d
e
g
(
h
). Assume that there exists ∑
i
=
0
n
a
i
h
i with d
e
g
(
a
i
)
<
d
e
g
(
h
) such that c
n
≡
∑
i
=
0
n
a
i
·
h
i
m
o
d
h
n
+
1. The condition π
n
+
1
(
c
n
+
1
)
=
c
n implies that(11)
c
n
+
1
′
-
∑
i
=
0
n
a
i
h
i
=
e
n
+
1
·
h
n
+
1with e
n
+
1
∈
R. Let a
n
+
1 and q
n
+
1 be the remainder and the quotient of e
n
+
1
/
h. Then a
n
+
1 does not depend on choice of c
n
+
1
′ and we have d
e
g
(
a
n
+
1
)
<
d
e
g
(
h
). Since e
n
+
1
=
a
n
+
1
+
h
·
q
n
+
1,(12)
c
n
+
1
′
-
∑
i
=
0
n
a
i
h
i
=
a
n
+
1
+
h
·
q
n
+
1
h
n
+
1
=
a
n
+
1
·
h
n
+
1
+
q
n
+
1
·
h
n
+
2
.Hence(13)
c
n
+
1
≡
∑
i
=
0
n
+
1
a
i
h
i
m
o
d
h
n
+
2
.The uniqueness is clear by the construction.Ifh
=
x
-
a with a
∈
F, (
x
-
a
)-adic polynomial of order n for f
/
g is the Taylor polynomial of order n for f
/
g at x
=
a. Here we present the following main theorem.Theorem 4 (main theorem).
Forf
,
g
,
p
,
q
∈
R
=
F
[
x
] and n
∈
N, let h be irreducible in R with d
e
g
(
h
)
⩾
1 and g
c
d
(
h
(
x
)
,
g
(
x
)
)
∈
F. Assume that(14)
f
x
g
x
h
n
x
=
p
x
h
n
x
+
q
x
g
xwith deg
⁡
(
p
)
<
deg
⁡
(
h
n
). Then(15)
p
x
=
P
n
-
1
f
g
,
h
.Proof.
By taking the modulus ofh
n and applying Lemma 2(b), we have(16)
p
x
≡
f
x
g
x
≡
P
n
-
1
f
g
,
h
m
o
d
h
n
.
d
e
g
p
(
x
)
-
P
n
-
1
f
/
g
,
h
<
d
e
g
(
h
n
) implies that(17)
p
x
-
P
n
-
1
f
g
,
h
=
0
,from which we complete the proof.In the next section we will explain how to computeh-adic polynomials with deg
⁡
(
h
)
⩽
2.


## 3. Formulas ofh-Adic Polynomials with d
e
g
(
h
)
⩽
2 and the Product of h-Polynomials

ForF
=
R or C, an irreducible polynomial h has at most degree 2. Since we can convert x
-
a and (
x
-
a
)
2
+
c
2 into t and t
2
+
c
2, respectively, by replacing x
-
a with t, we only present recursive formulas of (
x
)-adic polynomials and (
x
2
+
c
2
)-adic polynomials.Lemma 5.
Forp
(
≠
0
)
∈
R
=
F
[
x
] with g
c
d
(
p
,
h
)
=
1, let y
=
p
-
m
∈
R
h with m
∈
Z. Then(18)
m
·
d
d
x
p
·
y
+
p
·
d
d
x
y
=
0
.Proof.
p
m
·
y
=
1 implies m
·
p
m
-
1
d
/
d
x
(
p
)
·
y
+
p
m
·
d
/
d
x
(
y
)
=
p
m
-
1
m
·
d
/
d
x
(
p
)
·
y
+
p
·
d
/
d
x
(
y
)
=
0.Proposition 6.
We present two formulas forh-adic polynomials with h
=
x:(a)
Iff
(
x
)
=
(
x
-
a
)
-
m
=
∑
i
=
0
∞
c
i
x
i with m
∈
Z and a
≠
0, then c
0
=
(
-
a
)
-
m and(19)
c
k
+
1
=
m
+
k
a
k
+
1
c
k
k
⩾
0
.
(b)
Iff
(
x
)
=
(
x
-
a
)
2
+
b
2
-
m
=
∑
i
=
0
∞
c
i
x
i with m
∈
Z and a
2
+
b
2
≠
0, then c
0
=
(
a
2
+
b
2
)
-
m
,
c
-
1
=
0, and(20)
c
k
+
1
=
2
a
m
+
k
a
2
+
b
2
k
+
1
c
k
-
2
m
+
k
-
1
a
2
+
b
2
k
+
1
c
k
-
1
k
⩾
0
.Proof.
Case  (a). From Lemma 5 with p
=
x
-
a and y
=
∑
i
=
0
∞
c
i
x
i, we have(21)
m
·
1
·
∑
i
=
0
∞
c
i
x
i
+
x
-
a
∑
i
=
1
∞
i
·
c
i
x
i
-
1
=
0
.By comparing the coefficients of x
k, one can find(22)
x
k
:
m
·
c
k
+
k
·
c
k
-
a
·
k
+
1
·
c
k
+
1
=
0
.Thus c
k
+
1
=
(
m
+
k
)
/
a
(
k
+
1
)
c
k
(
k
⩾
0
), where c
0
=
(
-
a
)
m.
Case  (b). We can also prove part (b) by repeating the same argument with p
=
(
x
-
a
)
2
+
b
2.To compute theh-adic polynomial of a polynomial, we need formulas of the Taylor shift.Definition 7 (coefficient vector of ah-adic polynomial of order n).
For a givenh-adic polynomial f
=
∑
i
=
0
n
a
i
h
i
∈
R of order n
⩾
1, we define the corresponding coefficient vectors v
f
(
h
), v
f
odd
(
h
), and v
f
even
(
h
), respectively, as(23)
v
f
h
,
n
≔
a
0
,
a
1
,
…
,
a
n
t
,
v
f
even
h
,
n
≔
a
0
,
a
2
,
…
,
a
2
·
n
/
2
t
,
v
f
odd
h
,
n
≔
a
1
,
a
3
,
…
,
a
2
·
n
-
1
/
2
+
1
t
,where v
t is the transpose of a row vector v and x
≔
m
a
x
{
k
∈
Z
:
k
⩽
x
} (the floor function).Definition 8 (the Taylor shift matrix).
Fors
∈
F with r
,
c
∈
N
∪
{
0
}, (
r
+
1
)
×
(
c
+
1
) matrix T
r
,
c
(
s
) is(24)
T
r
,
c
s
=
t
i
,
j
s
0
⩽
i
⩽
r
,
0
⩽
j
⩽
c
w
h
e
r
e
t
i
,
j
s
=
j
i
·
s
j
-
i
,
i
⩽
j
0
,
i
>
j
,
j
i
=
j
!
j
-
i
!
·
i
!
w
i
t
h
j
⩾
i
⩾
0
.From the binomial expansion,∑
j
=
0
n
a
j
(
x
+
s
)
j
=
∑
i
=
0
n
∑
j
=
i
n
a
j
j
i
·
s
j
-
i
x
i, we obtain the following Taylor shift formulas for the coefficient vectors.Proposition 9 (Taylor shift).
For a polynomialf
∈
R with d
e
g
(
f
)
=
d,(25)
v
f
x
-
s
,
n
=
T
n
,
d
s
·
v
f
x
,
d
,where s
∈
F and n
∈
{
0,1
,
2
,
…
}.Remark 10.
To compute the Taylor shift matrix which is a Toeplitz matrix, we may use recursive formulas given by(26)
t
0,0
=
1
,
t
0
,
j
=
s
·
t
0
,
j
-
1
f
o
r
j
⩾
0
,
t
i
,
j
=
j
-
i
+
1
s
·
i
·
t
i
-
1
,
j
f
o
r
j
⩾
i
⩾
1
.Proposition 11.
We present three formulas forh-adic polynomials with h
=
x
2
+
c
2:
(a) (h
-Adic shift for
deg
⁡
(
h
)
=
2) for a polynomial f
∈
R
=
F
[
x
] with deg
⁡
(
f
)
=
d
⩾
1, the corresponding h-adic polynomial of order n, P
n
(
f
,
h
)
=
∑
i
=
0
n
(
β
i
+
α
i
x
)
h
i with α
i
,
β
i
∈
F, is determined by(27)
v
β
=
β
0
,
β
1
,
…
,
β
n
t
=
T
n
,
d
/
2
-
c
2
·
v
f
even
x
,
d
,
v
α
=
α
0
,
α
1
,
…
,
α
n
t
=
T
n
,
d
-
1
/
2
-
c
2
·
v
f
odd
x
,
d
.If d
=
0, then f
∈
F and(28)
P
n
f
,
h
=
f
+
∑
i
=
1
n
0
·
h
i
.
(b) Fora
≠
0 with m
∈
N,(29)
x
-
a
-
m
=
h
-
a
2
+
c
2
-
m
·
x
+
a
m
.For a
=
0, let q
=
m
+
1
/
2 and δ
=
2
q
-
m. Then m
=
2
q
-
δ with δ
∈
{
0,1
} and(30)
x
-
m
=
h
-
c
2
-
q
·
x
δ
.
(c) Fora
≠
0
,
b
≠
0, and m
∈
N,(31)
x
-
a
2
+
b
2
-
m
=
h
-
A
2
+
B
2
-
m
·
x
+
a
2
+
b
2
m
where
A
=
a
2
-
b
2
+
c
2
,
B
=
2
a
b
.For a
=
0
,
b
≠
0
,
b
2
≠
c
2, and m
∈
N,(32)
x
2
+
b
2
-
m
=
h
-
-
b
2
+
c
2
-
m
.Proof.
Case (a). You can find a similar argument on p. 591 in [2]. For d
=
0, it is clear. For f
(
x
)
=
∑
i
=
0
d
a
0
x
i
∈
R with d
⩾
1, we have(33)
f
x
=
∑
i
=
0
d
/
2
a
2
i
x
2
i
+
x
∑
i
=
0
d
-
1
/
2
a
2
i
+
1
x
2
i
=
∑
i
=
0
d
/
2
a
2
i
h
-
c
2
i
+
x
∑
i
=
0
d
-
1
/
2
a
2
i
+
1
h
-
c
2
i
=
∑
i
=
0
d
/
2
β
i
h
i
+
x
∑
i
=
0
d
-
1
/
2
α
i
h
i
.Hence α
i and β
i can be computed by the Taylor shift (Proposition 9).
Cases (b) and (c). (b) and (c) are clear by direct computations.To geth-adic polynomials of arbitrary rational functions, we just multiply simple h-adic polynomials which are computed using Propositions 6, 9, and 11. In general, the product of two h-adic polynomials may carry a term like(34)
1
+
x
+
1
-
x
1
+
x
2
·
1
-
x
+
1
+
x
1
+
x
2
=
1
-
x
2
+
2
1
+
x
2
2
+
1
-
x
2
1
+
x
2
2
=
2
-
1
1
+
x
2
+
4
1
+
x
2
2
-
1
1
+
x
2
3
.But if the coefficients of one of two h-adic polynomials are in F, then the product is carryless multiplication and the classic Cauchy product (convolution) formula still holds.Proposition 12 (h-adic Cauchy product formula).
Forr
1
^
,
r
2
^
∈
R
^
h, let P
n
(
r
1
^
,
h
)
=
∑
i
=
0
n
a
i
h
i, P
n
(
r
2
^
,
h
)
=
∑
i
=
0
n
b
i
h
i, and P
n
(
r
1
^
·
r
2
^
,
h
)
=
∑
i
=
0
n
c
i
h
i and assume a
i
∈
F. Then(35)
c
k
=
∑
i
=
0
k
a
i
·
b
k
-
i
,where 0
⩽
k
⩽
n.


## 4. Example

Example 1.
We compute the following partial fraction decomposition:(36)
x
2
+
x
x
-
1
3
x
2
+
4
2
=
p
x
x
-
1
3
+
q
x
x
2
+
4
2
.
(i)
h
=
x
-
1: from Theorem 4, we get(37)
p
x
=
P
2
x
2
+
x
x
2
+
2
2
2
,
h
=
P
2
P
2
x
2
+
x
,
h
·
P
2
1
x
2
+
4
2
,
h
,
h
.
From the Taylor shift (Proposition9), we have P
2
(
x
2
+
x
,
h
)
=
2
+
3
h
+
h
2.
From Proposition6(b), we compute(38)
P
2
1
x
2
+
4
2
,
h
=
P
2
h
+
1
2
+
2
2
-
2
,
h
=
1
25
-
4
125
h
+
2
625
h
2
.
Hence(39)
p
x
=
P
2
2
+
3
h
+
h
2
·
1
25
-
4
125
h
+
2
625
h
2
,
h
=
2
25
+
7
125
x
-
1
-
31
625
x
-
1
2
.
(ii)
h
=
x
2
+
2
2: using Proposition 11(b), we get 1
/
(
x
-
1
)
3
=
(
x
+
1
)
3
·
(
h
-
5
)
-
3. From Theorem 4, we have(40)
q
x
=
P
1
x
2
+
x
x
-
1
3
,
h
=
P
1
h
-
5
-
3
·
x
2
+
x
x
+
1
3
,
h
.
From Proposition6(a), we compute P
1
(
(
h
-
5
)
-
3
,
h
)
=
-
1
/
125
-
3
/
625
h.
Using Propositions6(b) and 12, we get(41)
x
2
+
x
x
+
1
3
=
0
+
x
+
x
2
1
+
3
x
+
3
x
2
+
x
3
=
0
+
4
x
2
+
4
x
4
+
1
x
+
6
x
3
+
1
x
5
.
From Proposition11(a), we compute(42)
1
-
4
16
0
1
-
8
0
4
4
=
48
-
28
,
1
-
4
16
0
1
-
8
1
6
1
=
-
7
-
2
⟹
P
1
x
2
+
x
x
+
1
3
,
h
=
48
-
7
x
-
28
+
2
x
h
.
Using Proposition12, we get(43)
q
x
=
P
1
-
1
125
-
3
625
h
·
48
-
7
x
-
28
+
2
x
h
,
h
=
-
48
+
7
x
125
+
-
4
+
31
x
625
h
.
Hence(44)
x
2
+
x
x
-
1
3
x
2
+
4
2
=
2
25
x
-
1
3
+
7
125
x
-
1
2
-
31
625
x
-
1
+
-
48
+
7
x
125
x
2
+
4
2
+
-
4
+
31
x
625
x
2
+
4
.


## 5. Main Algorithm (Algorithm1)

For a given proper (deg
⁡
(
N
)
<
deg
⁡
(
D
)) fraction(45)
N
x
D
x
=
N
x
∏
i
=
1
k
1
x
-
a
i
m
i
∏
i
=
1
k
2
x
-
b
i
2
+
c
i
2
n
i
,where (
x
-
a
i
) and (
x
-
b
i
)
2
+
c
i
2 are relatively prime, respectively, we return C
1
,
…
,
C
k
1 ((
x
-
a
i
)-adic polynomials of order (
m
i
-
1
)) and D
1
,
…
,
D
k
2 ((
x
-
b
i
)
2
+
c
i
2-adic polynomial of order (
n
i
-
1
)) such that(46)
N
x
∏
i
=
1
k
1
x
-
a
i
m
i
∏
i
=
1
k
2
x
-
b
i
2
+
c
i
2
n
i
=
∑
i
=
1
k
1
C
i
x
x
-
a
i
m
i
+
∑
i
=
1
k
2
D
i
x
x
-
b
i
2
+
c
i
2
n
i
.Algorithm 1:Main algorithm.
Output: C
i for i
=
1
,
…
,
k
1 and D
i for i
=
1
,
…
,
k
2.
(
1
)
for
i
←
1
to
k
1
do
(
2
)   Let h
=
x
-
a
i and find N
~
(
h
)
=
N
(
x
) using the Taylor shift (Proposition 9). Compute C
i:
C
i
=
P
m
i
N
x
D
x
-
1
x
-
a
i
m
i
,
x
-
a
i
=
P
m
i
N
~
h
∏
j
=
1
,
j
≠
i
k
1
h
-
a
j
-
a
i
-
m
j
∏
j=1
k
2
h-
b
j
-
a
i
2
+
c
i
2
-
n
i
,
h
using a binary splitting scheme (Lemma  4.1 on [2]), Proposition 6 and the h-adic Cauchy product formula (Proposition 12).
(
3
)
end
(
4
)
for
i
←
1
to
k
2
do
(
5
)   Let t
=
x
-
b
i and h
=
t
2
+
c
i
2. Using the Taylor shift (Proposition 9), find N
~
(
t
)
=
N
(
x
). Using the h-adic shift
(Proposition11(a)), find
M
~
h
=
N
~
t
∏
j
=
1
,
a
j
≠
b
i
k
1
t
+
a
j
-
b
i
m
j
∏
j
=
1
,
a
j
=
b
i
k
1
t
δ
j
∏
j
=
1
,
b
j
≠
b
i
k
2
t
+
b
j
-
b
i
2
+
c
j
2
n
i
whereq
j
=
m
j
+
1
/
2 and δ
j
=
2
q
j
-
m
j in Proposition 11(b). Compute D
i:
D
i
=
P
n
i
N
x
D
x
-
1
x
-
b
i
2
+
c
i
2
n
i
,
x
-
b
i
2
+
c
i
2
=
P
n
i
M
~
h
⋅
∏
j
=
1
,
a
j
≠
b
i
k
1
h
-
a
j
-
b
i
2
+
c
j
2
-
m
j
∏
j
=
1
,
a
j
=
b
i
k
1
h
-
c
i
2
-
q
j
⋅
∏
j
=
1
,
b
j
≠
b
i
k
2
h
-
b
j
-
b
i
2
-
c
j
2
+
c
i
2
2
+
2
b
j
-
b
i
c
j
2
-
n
i
∏
j
=
1
,
i
≠
j
,
b
j
=
b
i
k
2
h
-
-
c
j
2
+
c
i
2
-
n
i
,
h
using a binary splitting scheme (Lemma  4.1 on [2]), Proposition 6 and the h-adic Cauchy product formula (Proposition 12).
(6)endFrom the computation of Theorems  3.1 and   6.1 in [2], the complexity of the main algorithm (Algorithm 1) with simple algebraic operations is given by O
(
k
·
n
2
) with M
(
n
)
=
O
(
n
2
), where k
=
k
1
+
k
2, n
=
deg
⁡
(
D
(
x
)
), and M
(
n
) is any upper bound on the number of operations needed to multiply two n-th degree polynomials. Since F
=
R or C, if an FFT (fast Fourier transform) is used, we can reduce the complexity to O
(
k
·
(
n
log
⁡
n
)
) since M
(
n
)
=
O
(
n
log
⁡
n
) with FFT (Ch. 2 in [5]). For k
2
=
0, the best known complexity is O
(
(
log
⁡
k
)
·
(
n
log
⁡
n
)
) in [2]. If k is not big enough, our algorithm is still effective since it does not require computing(47)
R
x
=
∑
i
=
1
k
∏
j
=
1
,
j
≠
i
k
R
j
xwhich is an overhead of the algorithm in [2], where R
j
(
x
) is (
x
-
a
j
)
m
j or (
x
-
b
j
)
2
+
c
j
2
n
j.


## 6. Discussion

The main theorem and Propositions6, 9, 11, and 12 still hold for any field with characteristic zero. Since an irreducible polynomial h over R or C has at most degree 2, our recursive formulas for deg
⁡
(
h
)
⩽
2 cover all possible proper rational functions over R or C. If deg
⁡
(
h
)
>
2, we need to replace Propositions 6, 11(b), and 11(c) with the Extended Euclidean algorithm (Ch. 2 in [5]) which requires an algebra system to be implemented. To compute a h-adic polynomial P
n
(
f
,
n
)
=
∑
i
=
0
n
r
i
h
i of a polynomial f, we use the repeated division of f by h instead of Propositions 9 and 11(c). Then we obtain {
r
i
} as the remainders.(48)
f
=
q
1
h
+
r
0
q
1
=
q
2
h
+
r
1
⋮
q
n
=
q
n
+
1
h
+
r
n
.We can compute it quickly by applying the divide-and-conquer method (Problem 3.5 of [6]).


## 7. Conclusion

This paper shows that the partial fraction of a proper rational function with denominator factored completely overR or C can be found by computing suitable h-adic polynomials with deg
⁡
(
h
)
⩽
2. We also present recursive formulas (Propositions 6, 9, 11, and 12) to compute h-adic polynomials with deg
⁡
(
h
)
⩽
2. Since this algorithm only requires simple arithmetic operations, it can be implemented easily without a complex computer algebra system.



---

*Source: 7495964-2018-04-02.xml*