B-1 Inversion of a univariate homogeneous polynomial of degree n 507
Notable for the GKS algorithm is the following. In the first step or the forward substitution, a set of
equations {x, x
2 , . . . , x
n−1 , x
n
} is constructed by substituting x(y) into the powers x, x
2 , . . . , x
n−1 , x
n ,
finally written into a matrix equation. The upper triangular matrix A is gained by a multinomial
expansion as indicated. In contrast, the second step or the backward substitution is based upon
the upper triangular matrix B :=
−1
A , the inversion of A . Its first row contains the unknown
coefficients we are looking for: {b 11 , b 12 , . . . , b 1n−1 , b 1n } The construction of A as well as
−1
A can be
based on symbolic computer manipulation. The algebraic manipulation becomes more concrete when
we pay attention to Examples B.1 and B.2. The first example aims at the inversion of an univariate
homogeneous polynomial of degree n = 2, namely y(x) = a 11 x + a 12 x
2
→ x(y) = b 11 y + b 12 y
2 . The
GKS algorithm determines the set of coefficients {b 11 , b 12 } from the two given coefficients a 11 and a 12 .
In contrast, the second example focuses on the inversion of an univariate homogeneous polynomial of
degree n = 3, namely y(x) = a 11 x + a 12 x
2 + a 13 x
3
→ x(y) = b 11 y + b 12 y
2 + b 13 y
3 . The GKS algorithm
determines the set of coefficients {b 11 , b 12 , b 13 } from the three given coefficients a 11 , a 12 , and a 13 .
Example B.1 (Inversion of an univariate homogeneous polynomial of degree n = 2).
Assume the univariate homogeneous polynomial y(x) = a 11 x + a 12 x
2 to be given and find the inverse
univariate homogeneous quadratic polynomial x(y) = b 11 y + b 12 y
2 by the GKS algorithm.
1st step:
x(y) = b 11 y + b 12 y
2 = b 11 a 11 x +
b 11 a 12 + b 12 a
2
11
x
2 + β
13 ,
x
2 (y) = b 22 y
2 + β
23 = b 22 a
2
11 x
2 + β
23 .
(B.9)
2nd step (forward substitution):
x
x
2
=
b 11 b 12
0 b 22
a 11 a 12
0 a 22
x
x
2
+
β
13
β
23
=
b 11 a 11 b 11 a 12 + b 12 a 22
0
b 22 a 22
x
x
2
+
β
13
β
23
, (B.10)
subject to a 22 = a
2
11 .
Both the matrices A := A and B := B are upper triangular such that
A B = I 2 ⇔ B =
−1
A .
(B.11)
3rd step (backward substitution):
B =
−1
A = (a 11 a 22 )
−1
a 22 −a 12
0 a 11
=
a
−1
11 −a
−3
11 a 12
0
a
−2
11
⇒ b 11 = a
−1
11 , b 12 = −a
−3
11 a 12 , (B.12)
or
b 22 a 22 = b 22 a
2
11 = 1 ⇒ b 22 = a
−1
22 = a
−2
11 , b 11 a 11 = 1 ⇒ b 11 = a
−1
11 ,
b 11 a 12 + b 12 a 22 = 0 ⇒ b 12 = −a
−1
22 a 12 b 11 = −a
−3
11 a 12 ,
(B.13)
x(y) = a
−1
11 y − a
−3
11 a 12 y
2 .
(B.14)
End of Example.
Notable for the GKS algorithm is the following. In the first step or the forward substitution, a set of
equations {x, x
2 , . . . , x
n−1 , x
n
} is constructed by substituting x(y) into the powers x, x
2 , . . . , x
n−1 , x
n ,
finally written into a matrix equation. The upper triangular matrix A is gained by a multinomial
expansion as indicated. In contrast, the second step or the backward substitution is based upon
the upper triangular matrix B :=
−1
A , the inversion of A . Its first row contains the unknown
coefficients we are looking for: {b 11 , b 12 , . . . , b 1n−1 , b 1n } The construction of A as well as
−1
A can be
based on symbolic computer manipulation. The algebraic manipulation becomes more concrete when
we pay attention to Examples B.1 and B.2. The first example aims at the inversion of an univariate
homogeneous polynomial of degree n = 2, namely y(x) = a 11 x + a 12 x
2
→ x(y) = b 11 y + b 12 y
2 . The
GKS algorithm determines the set of coefficients {b 11 , b 12 } from the two given coefficients a 11 and a 12 .
In contrast, the second example focuses on the inversion of an univariate homogeneous polynomial of
degree n = 3, namely y(x) = a 11 x + a 12 x
2 + a 13 x
3
→ x(y) = b 11 y + b 12 y
2 + b 13 y
3 . The GKS algorithm
determines the set of coefficients {b 11 , b 12 , b 13 } from the three given coefficients a 11 , a 12 , and a 13 .
Example B.1 (Inversion of an univariate homogeneous polynomial of degree n = 2).
Assume the univariate homogeneous polynomial y(x) = a 11 x + a 12 x
2 to be given and find the inverse
univariate homogeneous quadratic polynomial x(y) = b 11 y + b 12 y
2 by the GKS algorithm.
1st step:
x(y) = b 11 y + b 12 y
2 = b 11 a 11 x +
b 11 a 12 + b 12 a
2
11
x
2 + β
13 ,
x
2 (y) = b 22 y
2 + β
23 = b 22 a
2
11 x
2 + β
23 .
(B.9)
2nd step (forward substitution):
x
x
2
=
b 11 b 12
0 b 22
a 11 a 12
0 a 22
x
x
2
+
β
13
β
23
=
b 11 a 11 b 11 a 12 + b 12 a 22
0
b 22 a 22
x
x
2
+
β
13
β
23
, (B.10)
subject to a 22 = a
2
11 .
Both the matrices A := A and B := B are upper triangular such that
A B = I 2 ⇔ B =
−1
A .
(B.11)
3rd step (backward substitution):
B =
−1
A = (a 11 a 22 )
−1
a 22 −a 12
0 a 11
=
a
−1
11 −a
−3
11 a 12
0
a
−2
11
⇒ b 11 = a
−1
11 , b 12 = −a
−3
11 a 12 , (B.12)
or
b 22 a 22 = b 22 a
2
11 = 1 ⇒ b 22 = a
−1
22 = a
−2
11 , b 11 a 11 = 1 ⇒ b 11 = a
−1
11 ,
b 11 a 12 + b 12 a 22 = 0 ⇒ b 12 = −a
−1
22 a 12 b 11 = −a
−3
11 a 12 ,
(B.13)
x(y) = a
−1
11 y − a
−3
11 a 12 y
2 .
(B.14)
End of Example.