算法设计与分析笔记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:

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.