Algorithms: divide & conquer question How to compute this? (pseudocode) Consider

Question

Algorithms: divide & conquer question

How to compute this? (pseudocode)

Consider the matrix-vector product c = W middot b, where W is an nxn matrix. The time complexity is o(n^2]. Let us restrict W to be a type of matrix that we will call Weird-Matrices. These weird matrices have sizes that are powers of 2. Weird- Matrix Wk has size 2^k. Weird-matrices of difference sizes are defined as follows. W_o = [3] W_k = 3W k-1 W k-1 2W k-1 4W k-1 k>0 Give pseudo-code for a divide and conquer algorithm to compute Wn middot b in time o(n log n). WEIRD-MULTIPLY(k, v) should return Wn middot b. Show the recurrence for the time complexity and use the master theorem to prove that it has the desired time complexity.

Explanation / Answer

divide and conquer algorithm for matrix multiplication.

This relies on the block partitioning {displaystyle C={egin{pmatrix}C_{11}&C_{12}\C_{21}&C_{22}\end{pmatrix}},,A={egin{pmatrix}A_{11}&A_{12}\A_{21}&A_{22}\end{pmatrix}},,B={egin{pmatrix}B_{11}&B_{12}\B_{21}&B_{22}\end{pmatrix}}}which works for all square matrices whose dimensions are powers of two, i.e., the shapes are 2n × 2n for some n.

The matrix product is now {displaystyle {egin{pmatrix}C_{11}&C_{12}\C_{21}&C_{22}\end{pmatrix}}={egin{pmatrix}A_{11}&A_{12}\A_{21}&A_{22}\end{pmatrix}}{egin{pmatrix}B_{11}&B_{12}\B_{21}&B_{22}\end{pmatrix}}={egin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\end{pmatrix}}}which consists of eight multiplications of pairs of submatrices, followed by an addition step.

The divide and conquer algorithm computes the smaller multiplications recursively, using the scalar multiplication c11 = a11b11 as its base case.

The complexity of this algorithm as a function of n is given by the recurrence accounting for the eight recursive calls on matrices of size n/2 and (n2) to sum the four pairs of resulting matrices element-wise.

Application of the master theorem shows this recursion to have the solution (n3), the same as the iterative algorithm.

In the analysis of algorithms, the master theorem provides a solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms

Let v be a column vector. Want: A · v. (1) Break up v into log n sized chunks: v = v 1 v 2 . . . v n log n

(2) For each i = 1,... ,n/ ( log n ), look up v i in Pi .

(3) Look up the neighbors of v i, mark each neighbor found.

(4) For each Q j , define v j as the OR of all marked vectors in Q j

(5) Output v := 1 v 2 . . . v n log n Claim: v = A · v.

Matrix-Vector Multiplication: Fundamental Operation in Scientific Computing How fast can n × n matrix-vector multiplication be? (n2) steps just to read the matrix!

Main Result: If we allow O(n2+) preprocessing, then matrix-vector multiplication over any finite semiring can be done in O(n2/( log n)2).

"'> j as the OR of all marked vectors in Q j

(5) Output v := 1 v 2 . . . v n log n Claim: v = A · v.

Proposition. The divide-and-conquer multiplication algorithm requires (n2) bit operations to multiply two n-bit integers.

Pf. Apply case 1 of the master theorem to the recurrence:

Divide-and-conquer multiplication analysis

€ T(n) = 4T(n/2)

recursive calls !

#"#$ + (n) add, shift !"$ T(n) = (n 2 )

log n Claim: v = A · v.

MULTIPLY(x, y, n) oNormal>recursive calls !

#"#$ + (n) add, shift !"$ T(n) = (n 2 )

log n Claim: v = A · v.

IF (n = 1) RETURN x y.

ELSE m n / 2 .

a x / 2m;

b x mod 2m.

c y / 2m;

y mod 2m.

e MULTIPLY(a, c, m).

f MULTIPLY(b, d, m).

g MULTIPLY(b, c, m).

h MULTIPLY(a, d, m).

RETURN 22m e + 2m (g + h) + f.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.