Polynomials & Matrices

¡EPolynomial:    P(x)=X4+4X3+3X+1
             array:    P[0...4]=[1,3,0,4,1]            P[i]¡ö¡÷PiXi
 

¡EMatrix:
      array:    M[i,j]¡ö¡÷Mij
      double linked list:    (Sparse matrix)

Polynomials    p(x)=anxn+...+a1x+a0

        x1                 y=p(x1)
        x2     p(x)      y=p(x2)
       ¡G    ¡X¡÷      ¡G
       ¡G                  ¡G
        xN                 y=p(xN)
 

¡Ecompute    y:    evaluation
                     p:    interpolation
                     x:    find root    :Newton's method...
 

Evaluation    y=p(x)=2x4+3x3-6x2+2x+1
¡EBrute-force:
    2x4, 3x3, (-6)x2, ...    "*": 4+3+2+1=N(N+1)/2
    (x4+3x3)+...                 "+": 4             =N

    problems:    x3, x4 ­«½Æ­pºâ

¡EHorner's rule:
        p(x)=x*(x*(x*(x*2+3)-6)+2)+1    :4"*"+4"+"

¡EFFT(Fast Fourier Transforms in Chap.41)
        can evaluate at N points with NlogN "*"

¡EXN only :

    X55 =X[ 1 1 0 1 1 1] 2
           =X32 * X16 * X4 * X2 * X1
           =X2^5+2^4+0*2^3+2^2+2^1+1
           =X((((1*2+1)*2+0)*2+1)*2+1)*2+1
           =(((((12 * X)2  * X)2 *1 )2 *X )2 *X)2 *X

    55=[   1 , 1 , 0 , 1 ,1 , 1  ] 2
    Xa*b =( Xa )b
    Xa+b  =Xa* Xb

Interpolation    :p(x)=?
    such that p(x1)=y1, ... , p(xN)=yN

¡ELagrange method:

    Example:    p(1)=3, p(2)=7, p(3)=13
                      p(x)=3*(x-2)(x-3)     +    7*(x-1)(x-3)     +    13*(x-1)(x-2)
                                   (1-2)(1-3)               (2-1)(2-3)                (3-1)(3-2)
                            =X2+ X + 1

                      p(1)=3*1+7*0+13*0
                      p(2)=3*0+7*1+13*0
                      p(3)=3*0+7*0+13*1

¡EO(N2)    operations

Multiplication
P (x) = P0 +   P1X + .....+PN-1 XN-1
Q(x) = Q0 +  Q1X +.....+QN-1 XN-1

P(x) * Q(x) =?

¡EBrute-force: N  "*"

¡EDivide + Conquer
    P(x)=(P0 + P1X+...+PN/2-1 XN/2-1)+X N/2(PN/2 + PN/2+1X+...+PN-1XN/2-1)
          =Pl(x)+XN/2 Ph(x)
    Q(x)=Ql(x)+XN/2Qh(x)

    =>P(x)*Q(x)=Pl*Ql+(PlQh+Ph*Ql)XN/2+(Ph*Qh)XN

    ¡· PlQh+Ph*Ql=(Pl+Ph)*(Ql+Qh)-PlQl-PhQh

¡EM(N) = # "* " for P(x)*Q(x)
    M(N)=3M(N/2)           N=2n
                 =3M(2n-1)
             =32M(2n-2)
             .
             .
             =3nM(20)
             =3n=(2log23 )n = (2n)log23
             =N1.58

    Example :
        P(x)=1+x+3x -4x = (1+x) + x2 (3-4x)=Pl  +x2Ph
        Q(x)=1+2x-5x -3x = (1+2x) + x2 (-5-3x)=Ql   +x2Qh
 
Large numbers

¡Ep=0 1 2 0 2 0 0 1 0 3 1 1 0 0 0 1 2 0 0 0 0 4 0 1 2 3 1 4
    p(x)=x26+2x25+2x24+...+x4+2x3+3x2+x+4 | x=10
    P(x)=120x6+2001x5+311x4+x3+2000x2+401x+2314 | x=10000

¡E p*q=p(x)*q(x) |x=10
           =P(x)*Q(x) |x=10000

    Example:    p=4385                        q=6857
                      p(x)=4x3+3x2+8x+5     q(x)=6x3+8x2+5x+7
                      p(x)*q(x)=24x6+50x5+92x4+137x3+101x2+81x+35
                                          60  106  147  109    84
                      p*q=    30      0      6      7      9      4      5

¡E (p*q) mod N    (pk mod N)
     Theorem: (x+y) mod N = x mod N + y mod N    mod N
                    (x*y) mod N = (x mod N) + (y mod N)    mod N
     P mod N
     = 120 (x6 mod N) + 2001( x5 mod N) + 311 (x4 mod N) +
        (x3 mod N) + 2000(x2 mod N) + 401(x mod N) + 2314
        mod N