算法设计与分析笔记0x06 —— 分治法(2)

Integer Multiplication

Brute force solution: $\Theta(n^2)$ bit operations.
To multiply two n-digit integers: (warm up)

  • Multiply four n/2-digit integers.
  • Add two n/2-digit integers, and shift to obtain result.

$x = 1000 1101$, $x_1 = 1000$, $x_0 = 1101$

$$x=2^{n/2} x_1 + x_0$$
$$y=2^{n/2} x_1 + y_0$$
$$xy=(x^{n/2} x_1 + x_0)(2^{n/2} x_1 + y_0)=x^n x_1 y_1 + 2^{n/2}(x_1 y_0+x_0 y_1)+x_0 y_0$$
$$T(n)=4T(n/2)+\Theta(n)=\Theta(n^2)$$

Karatsuba Multiplication

$$x=2^{n/2} x_1 + x_0$$
$$y=2^{n/2} x_1 + y_0$$
$$xy=2^n x_1 y_1 + 2^{n/2} (x_1 y_0+x_0 y_1) + x_0 y_0$$
$$xy=2^n x_1 y_1 + 2^{n/2} ((x_1 + x_0)(y_0 + y_1) – x_1 y_1 – x_0 y_0) + x_0 y_0$$
$$T(n)\leq T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + T(1+\lceil n/2 \rceil)+\Theta(n)$$
$$\Rightarrow T(n)=O(n^{log_{2}{3}})=O(n^{1.585})$$

Matrix Multiplication

Matrix C=AB, $C_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj}$
Brute force: $\Theta(n^3)$.

Warm Up

  • Divide: partition A and B into n/2-by-n/2 blocks.
  • Conquer: multiply 8 n/2-by-n/2 recursively.
  • Combine: add appropriate products using 4 matrix additions.



Key Idea: multiply 2-by-2 block matrices with only 7 multiplications.

  • Divide: partition A and B into n/2-by-n/2 blocks.
  • Compute: 14 n/2-by-n/2 matrices via 10 matrix additions.
  • Conquer: multiply 7 n/2-by-n/2 matrices recursively.
  • Combine: 7 products into 4 terms using 8 matrix additions.

|

$A(x)=a_0+a_1 x+a_2 x^2+…+a_{n-1}x^{n-1}$
$B(x)=b_0+b_1 x+b_2 x^2+…+b_{n-1}x^{n-1}$
$A(x)=a_0+(x(a_1 + x(a_2+…+x(a_{n-2}+x(a_{n-1}))…))$

Polynomials: Point-Value Representation

A(x): $(x_0,y_0)$,…,$(x_{n-1},y_{n-1})$
B(x): $(x_0,z_0)$,…,$(x_{n-1},z_{n-1})$

  • Add: $O(n)$
    • A(x) + B(x): $(x_0,y_0 + z_0)$,…,$(x_{n-1},y_{n-1}+z_{n-1})$
  • Multiply: $O(n)$, but need 2n-1 points?
    • A(x) × B(x): $(x_0,y_0 \times z_0)$,…,$(x_{2n-1},y_{2n-1}\times z_{2n-1})$
  • Evaluate: $O(n^2)$ using Lagrange’s formula
    • $$A(x)=\sum_{k=0}^{n-1} y_k \frac{\prod_{j\neq k}(x-x_j)}{\prod_{j\neq k}(x_k – x_j)}$$

Representation Converting

  • $A(x)=a_0 + a_1 x+ a_2 x^2 + a_3 x^3$
  • $A_{even} (x)=a_0 + a_2 x$
  • $A_{odd} (x)=a_1 + a_3 x$
  • $A(x) = A_{even}(x^2)+x A_{odd}(x^2)$
  • $A(-x) = A_{even}(x^2)-x A_{odd}(x^2)$
    • Can evaluate polynomial of degree ≤ n at 2 points by evaluating two polynomials of degree ≤ n/2 at 1 point.
    • $A(1) = A_{even}(1)+1 A_{odd}(1)$
    • $A(-1) = A_{even}(1)-1 A_{odd}(1)$
    • $A(i) = A_{even}(-1)+i A_{odd}(-1)$
    • $A(-i) = A_{even}(-1)-i A_{odd}(-1)$

Roots of Unity

Goal Choose n points s.t.

  • Can evaluate polynomial of degree ≤ n at n points by evaluating two polynomials of degree ≤ n/2 at n/2 point.
  • But also: can evaluate polynomial of degree ≤ n/2 at n/2 points by evaluating two polynomials of degree ≤ n/4 at n/4 point, and so on.

Def. An nth root of unity is complex number x such that $x^n = 1$.

  • The $n^{th}$ roots of unity are: $\omega ^0$, $\omega ^1$,…, $\omega ^{n-1}$ where $\omega=e^{2\pi i/n}$
    • $(\omega^k)^n = (e^{2\pi ik/n})^n=(e^{\pi i})^{2k}=(-1)^{2k}=1$
  • The $\frac{1}{2} n^{th}$ roots of unity are: $v^0$, $v^1$,…,$v^{n/2-1}$ where $v=e^{4\pi i/n}$.
  • $\omega ^2=v$ and $(\omega ^2)^k = v^k$.


Fast Fourier Transform

Goal Evaluate a degree n-1 polynomial $A(x)=a_0+…+a_{n-1}x^{n-1}$ at its $n^{th}$ roots of unity: $\omega ^0$, $\omega ^1$,…, $\omega ^{n-1}$.

  • Divide
    • $A_{even}(x)=a_0+a_2 x+a_4 x^2 +…+a_{n/2-2} x^{(n-1)/2}$.
    • $A_{odd}(x)=a_1+a_3 x+a_5 x^2 +…+a_{n/2-1} x^{(n-1)/2}$.
    • $A(x) = A_{even}(x^2)+x A_{odd}(x^2)$
  • Conquer: Evaluate degree $A_{even}(x)$ and $A_{odd}(x)$ at its $\frac{1}{2}n^{th}$ roots of unity: $v^0$, $v^1$,…, $v^{n/2-1}$.
  • Combine
    • $A(\omega ^k)=A_{even}(v^k)+\omega ^k A_{odd}(v^k)$, $0\leq k < n/2$
    • $A(\omega ^{k+n/2})=A_{even}(v^k)-\omega ^k A_{odd}(v^k)$, $0\leq k < n/2$

FFT Algorithm

$$T(2n)=2T(n)+O(n)=O(nlogn)$$

IFFT Algorithm


The inverse matrix is:


Summation lemma:
Summation Lemma

Now we can convert between the two representations in O(nlogn).

  • Can’t compare directly between digit operation and complex number operation.
  • We uses brute force, Karatsuba and FFT, depending on the size of n.

Leave a Reply

Your email address will not be published.