CSCE 411 Lecture 6

Lecture Slides

« previous | Friday, September 7, 2012 | next »

Master Theorem

$T(n)=aT\left(\frac{n}{b}\right)+f(n)$

We assume $a\ge 1$, $b>1$, and $f(n)$ eventually positive

1. $f(n)=O(n^{{\log }_{b}a-ϵ})⟶T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$
2. $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a})⟶T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log n)$
3. $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})⟶T(n)=\mathrm{\Theta }(f(n))$

Note: For case 3, $f(n)$ must be regular

Matrix Multiplication

Classic algorithm

$AB=(\sum {j=1}^n{a}_{ij}{b}_{jk})$ for $1\le (i,j,k)\le n$

for i from 1 to n do:

 for j from 1 to k do:
   for t from 1 to m do:

   end for
 end for

end for

Approx $\mathrm{\Theta }(n^3)$

Divide and Conquer

$\left[\begin{array}{cc}{A}_0& A_1\\ A_2& A_3\end{array}\right]\times \left[\begin{array}{cc}{B}_0& B_1\\ B_2& B_3\end{array}\right]=\left[\begin{array}{cc}{A}_0\times B_0+A_1\times B_2& A_0\times B_1+A_1\times B_3\\ A_2\times B_0+A_3\times B_2& A_2\times B_1+A_3\times B_3\end{array}\right]$

Divide batrices $A$ and $B$ into four smaller matrices:

• 8 matrix multiplications on submatrices of $A$ and $B$
• $\mathrm{\Theta }(n^2)$ scalar additions

Running Time

• $T(n)=8T\left(\frac{n}{2}\right)+\mathrm{\Theta }{n}^2$
• $T(2)=\mathrm{\Theta }(1)$
• $T(n)\in \mathrm{\Theta }(n^3)$ great, all that work for nothing.

Can we do fewer operations?

Strassen's Matrix

Just calculate 7 products and do a bunch of cheap additions

$T(n)=7T\left(\frac{n}{2}\right)+\mathrm{\Theta }(n^2)\in O(n^{2.807})$

Integer Multiplication

Elementary school algorithm $41\times 42=101001_2\times 101010_2=1010100_2+101010000_2+10101000000_2=11010111010_2=1722_{10}$

Multiplication of 2 $n$-bit numbers takes $\mathrm{\Omega }(n^2)$.

Kolmogrov (at one of his seminars) conjectured that we can't do better, but Karatsuba proved him wrong a week later.

Dividery and Conquery

Split $x$ and $y$ into two smaller parts: their most significant and least significant parts:

• $x=2^{\frac{n}{2}}A+B$, where $A$ and $B$ are n/2-bit algorithms
• $x=2^{\frac{n}{2}}C+D$, where $C$ and $D$ are n/2-bit algorithms
• $xy=2^{n}AC+2^{\frac{n}{2}}BC+2^{\frac{n}{2}}AD+BD$ still $T(n)=4T\left(\frac{n}{2}\right)+\mathrm{\Theta }(n)=\mathrm{\Theta }(n^2)$

What if we multiply $(A+B)(C+D)=AC+AD+BC+BD$? Just correct the terms:

$xy=(2^n-2^{\frac{n}{2}})AC+2^{\frac{n}{2}}(A+B)(C+D)+(1-2^{\frac{n}{2}})BD$

This has only 3 multiplications, so $T(n)=3\left(\frac{n}{2}\right)+\mathrm{\Theta }(n)=\mathrm{\Theta }(n^{{\log }_{2}3})$

Summary of Dividery and Conquery

1. Split $x$ into two parts $A$ and $B$
2. Split $y$ into two parts $C$ and $D$
3. calculate $AC$, $(A+B)(C+D)$, and $BD$
4. shift each of the results by a certain amount and add all of those together