Chinese Remainder Theorem for Polynomials 1.0 
Date Added: June 01, 2013  Visits: 178 


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_Polysuch that it satisfies the foll 4 equations :Remainder of c_soln_Poly divided by ( 16.x^3 + 5.x^2 + 9.x + 4 ) = 1Remainder of c_soln_Poly divided by ( 2.x^3 + 11.x^2 + 7.x + 14 ) = 2Remainder of c_soln_Poly divided by ( 3.x^3 + 10.x^2 + 6.x + 15 ) = 3Remainder of c_soln_Poly divided by ( 13.x^3 + 8.x^2 + 12.x + 1 ) = 4The 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.0903Now, how did we find this c_soln_Poly ?The answer is this Programme, the application of the Chinese RemainderTheorem 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 equalto lines.The Poly coeffs used above are nothing but columns of magic(4)ie, we have made Polynomials out of the columnwise 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 = 4The Chinese Remainder Theorem for Polynomials is defined instill more mathematical notations in literature as follows(for eg, in the book by Richard Blahut / P77) :For any set of Pairwise Coprime Polynomials [m1(x), m2(x), ... mk(x)],the set of congruences :c(x) =eqvt mod ( ck(x), mk(x) ), k = 1, 2, ... khas a unique solution of a degree less than the degreeof 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 satisfiesNk(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 21of the book by Neal Koblitz describing the Chinese Remainder Theoremfor Integers. Blahut also describes the Chinese Remainder Theoremfor 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 andthe programme, is that the Columnwise Polys of input mk_Polybe Pairwise Coprime. So, we first check if all the k*(k1)/2This 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 Nonconvergent cases :Poly 2 of magic(8), Poly 4 of magic(7)These two cases can be good test cases for any futurechanges in the empirical logics of this programme.It will be highly desirable to find a logic that will give GCD = 1for these cases.Should also generally work for R13 and R12 (but Poly_POWER cannot work only in R12).

License: Shareware  Size: 112.64 KB 
Development Tools

A Benchmark Problem for Model Based Control System Tests  001 1.0
Today safety critical flight control systems are tested using model based approach. The model blocks are proprietary and seldom shared in the open. A benchmark problem was designed as part of a research activity to test out certain test case... 
3.33 MB  
Development Tools

Converts between decimal integers to multiple based numbers 1.0
DEC2MBASE: converts decimal integers to multiple based numbers.MBASE2DEC: the inverse function of DEC2MBASE.Two corresponding html documents are also supplied for detailed documentation. 
10 KB  
Development Tools

Euler_Phi and Its Applications 1.0
Euler_Phi.zip is a suite of the foll Programmes :1) Euler_Phi (n) returns the no of positive integers less than n which are prime to n.2) a_k_mod_m_LCM_Method (a, m, k) : Imagine computing mod(14^26, 45) or mod(56^3005, 1125).This programme... 
10 KB  
Utilities

Source Mage GNU/Linux 0.9.6.3
Source Mage GNU/Linux distribution is based on a sorcerous metaphor of "casting" and "dispelling" packages, which we refer to as "spells". This is a development ISO and potentially loaded with bugs and glitches. This is where you come in. We... 
247 MB  
Utilities

Source Mage GNU/Linux 0.9.6 PPC
Source Mage GNU/Linux distribution is based on a sorcerous metaphor of "casting" and "dispelling" packages, which we refer to as "spells". This is a development ISO and potentially loaded with bugs and glitches. This is where you come in. We... 
207.9 MB  
Utilities

phpXIedit 0_7_beta
phpXIedit is a web based application to edit, validate and preview XML documents. This document describes the installation and basic functionality of phpXIedit. The package can be downloaded at http://sourceforge.net 
409.6 KB  
Development Tools

Digital Control System Analysis and Design, 3e 1.0
Designed for a seniorlevel course in digital or discretetime controls, this third edition has been updated to include MATLAB based examples for problem solving.For a full book description and ordering information, please refer to... 
61.44 KB  
Development Tools

Using MathWorks Tools to Apply ModelBased Design for DO178B Applications 1.0
This example demonstrates the use of The MathWorks product family to apply ModelBased Design in the development of applications that may be certified using DO178B or ARP4754 standards.This example will step through the complete software... 
2.56 MB  
Development Tools

MATLAB Contest Paper 1.0
This paper describes the webbased MATLAB programming contests and points out some interesting connections between the contests and opensource software development.[This paper was presented at CHI 2001.] 
102.4 KB  
Development Tools

Differential Evolution Based Channel and Feature Selection 1.0
One of the fundamental motivations for feature selection is to overcome the curse of dimensionality problem. This code presents a novel feature selection method utilizing a combination of differential evolution (DE) optimization method and a... 
10 KB 
Scripts

Freelancer Script 5.05
Main Features: 100% Secured. Email Support (3 Years). FREE Updates (3 Years). Post projects. Featured projects. Private projects. Sealed projects. Edit/delete projects. Select freelancers.... 
5.49 MB  
Scripts

B2B Script 4.20
Main Features: 100% Secured. Email Support (3 Years). FREE Updates (3 Years). Signup Account (Registration of account). Lead generation tools (for the sellers). Email verification to... 
5.49 MB  
Scripts

B2C Script 5.06
Main Features: 100% Secured. Email Support (3 Years). FREE Updates (3 Years). The script comes with totally editable site colors, icons and graphics Multilevel categories allows extensive browsing Admin can change Category ordering or... 
5.49 MB  
Scripts

Social Networking Script 2.86
Main Features: 100% Secured. Email Support (3 Years). FREE Updates (3 Years). Registration with name, email, password, date of birth etc. User can add multiple school, college, university with start... 
5.49 MB  
Scripts

Business Networking Script 8.04
Main Features: 100% Secured. Email Support (3 Years). FREE Updates (3 Years). Ajax based interface. Profile creation. Different types of profile. Profile for jobseekers, employers and employed... 
5.49 MB  
Development Tools

VMP Viewer 1.0
This is a very rudimentary tool to visualize the VMP files generated by BrainVoyager. Useful to share files with people who do not have BV. 
10 KB  
Development Tools

Sending reports and timestamped file by emailing 1.0
main executing reference usage:[1] usage_send_mail.mIllustrates email sending with multiple separate files or single timestamped tar file. Attachment failure is properly handled, with continuation of report emailing without the attachment.[2]... 
768 KB  
Development Tools

IrisMVC 2.0 rc1
IrisMVC is an OOP PHP framework that developers can use as a strong and secure foundation to build on various web applications following the ModelViewController (MVC) pattern. It provides the basic functionality developers need, without... 
51.2 KB  
Development Tools

7Zip for Script 4.42
7Zip is a file archiver with a high compression ratio.Features: High compression ratio in new 7z format with LZMA compression Supported formats: Packing / unpacking: 7z, ZIP, GZIP, BZIP2 and TAR Unpacking only: RAR, CAB, ISO, ARJ, LZH, CHM,... 
624.64 KB  
Development Tools

Barnardextest 1.0
This file, as the Fisher's exact test, performs the exact probability test for a table of frequency data crossclassified according to two categorical variables, each of which has two levels or subcategories (2x2). It is a nonparametric... 
10 KB 