Chinese Remainder Theorem for Polynomials

15th July, 2005 : Poly_POWER.m is now corrected !

So, for most reasonable cases of Multiple Roots including Multiple Real Roots, Poly_POWER.m should now work.

********************

Functional Description of Ch_Rem_Thr_Poly.m :

Assume that we need to find a solution c_soln_Poly
such that it satisfies the foll 4 equations :
Remainder of c_soln_Poly divided by ( 16.x^3 + 5.x^2 + 9.x + 4 ) = 1
Remainder of c_soln_Poly divided by ( 2.x^3 + 11.x^2 + 7.x + 14 ) = 2
Remainder of c_soln_Poly divided by ( 3.x^3 + 10.x^2 + 6.x + 15 ) = 3
Remainder of c_soln_Poly divided by ( 13.x^3 + 8.x^2 + 12.x + 1 ) = 4

The solution c_soln_Poly is :
-0.2561.x^11 -2.1843.x^10 -5.1302.x^9 -4.4053.x^8 ...
-4.0876.x^7 +11.9307.x^6 +23.1045.x^5 +33.0426.x^4 ...
+36.8186.x^3 +20.7266.x^2 +13.9833.x +5.0903

Now, how did we find this c_soln_Poly ?
The answer is this Programme, the application of the Chinese Remainder
Theorem for Polynomials.

The above problem can be stated in a more mathematical language as :
c_soln_Poly =eqvt mod ( 1, { Poly with coeffs : [16 5 9 4] } )
c_soln_Poly =eqvt mod ( 2, { Poly with coeffs : [ 2 11 7 14] } )
c_soln_Poly =eqvt mod ( 3, { Poly with coeffs : [ 3 10 6 15] } )
c_soln_Poly =eqvt mod ( 4, { Poly with coeffs : [13 8 12 1] } )

where "=eqvt" implies "congruence" with the usual symbol of 3 equal-to lines.

The Poly coeffs used above are nothing but columns of magic(4)
ie, we have made Polynomials out of the column-wise coeffs of magic(4).
mk_Poly = magic(4) ;

That the Remainders are resp 1, 2, 3 and 4 wrt the 4 Polys of magic(4)
can be verified by :
[QT, RT] = deconv ( c_soln_Poly, mk_Poly (:, 1) ) ; % RT = 1
[QT, RT] = deconv ( c_soln_Poly, mk_Poly (:, 2) ) ; % RT = 2
[QT, RT] = deconv ( c_soln_Poly, mk_Poly (:, 3) ) ; % RT = 3
[QT, RT] = deconv ( c_soln_Poly, mk_Poly (:, 4) ) ; % RT = 4

The Chinese Remainder Theorem for Polynomials is defined in
still more mathematical notations in literature as follows
(for eg, in the book by Richard Blahut / P77) :
For any set of Pair-wise Coprime Polynomials [m1(x), m2(x), ... mk(x)],
the set of congruences :
c(x) =eqvt mod ( ck(x), mk(x) ), k = 1, 2, ... k
has a unique solution of a degree less than the degree
of M(x) = prod (m1(x), m2(x), ... mk(x)), given by :
c_soln_Poly(x) = sum ( mod ( ck(x).Nk(x).Mk(x), M(x) ) )
where Mk(x) = M(x) / mk(x), and Nk(x) is the Polynomial that satisfies
Nk(x).Mk(x) + nk(x).mk(x) = GCD = 1
(this is where we need to use my programmes Poly_GCD.m and Poly_GCD_Main.m)

I understood these notations better only after / when I read P 21
of the book by Neal Koblitz describing the Chinese Remainder Theorem
for Integers. Blahut also describes the Chinese Remainder Theorem
for Integers in P 70.
Please also refer to my programme Ch_Rem_Thr_Int.m for Integers.
This programme for Polynomials is developed partly based on similar concepts.

One of the most important prerequisites for this Theorem and
the programme, is that the Column-wise Polys of input mk_Poly
be Pair-wise Coprime. So, we first check if all the k*(k-1)/2

This programme makes heavy usage of the other programme Poly_GCD.m,
and hence, is also subject to the same constraints and limitations,
only these limitations are still more stringent here.
I have so far observed only 2 Non-convergent cases :
Poly 2 of magic(8), Poly 4 of magic(7)
These two cases can be good test cases for any future
changes in the empirical logics of this programme.
It will be highly desirable to find a logic that will give GCD = 1
for these cases.

Should also generally work for R13 and R12 (but Poly_POWER cannot work only in R12).