VE477 Homework 8

Description

Questions preceded by a * are optional. Although they can be skipped without any deduction, it is important to know and understand the results they contain.

Ex. 1 — Fast multi-point evaluation and interpolation

Let R be a commutative ring, u₀, · · · , u_n−1 be n elements in R, and m_i = X − u_i , with 0 ≤ i < n, be n degree 1 polynomials in R[X ]. Without loss of generality we assume n to be a power of 2.

Part I — Fast multi-point evaluation

In order to perform fast multi-point evaluation the set of points U = {u₀, · · · , u_n } is recursively split into two halves of equal cardinality.

1.	Draw the binary tree resulting from the recursive split of the set U.
2.	Denote thei	depth of the binary tree by k and for all 0 ≤ i ≤ k and 0 ≤ j < 2k −i , define
	Mi ,j = ∏l2=0−1 mj 2i +l . Prove that for each i, j
					(1.1)
			Mi +1,j	= Mi ,2j Mi ,2j +1
				= mj .
			M0,j

3. How do the M_{i ,j} relate to the binary tree?

3. Fast multi-point evaluation.

3. 1. Write an algorithm that builds the subproduct tree and returns the polynomials M_{i ,j} as defined in (1.1).

   2. Write an recursive algorithm which takes a polynomial P of degree less than n = 2^k as input as well as u₀, · · · , u_n−1 and the subproducts M_{i ,j} . It should go down the subproduct tree and return P(u₀), · · · , P(u_n−1).

3. Correctness and complexity.

3. 1. By induction on k, prove the correctness of the previous algorithm.

3. 2. Show that the complexity of the algorithm is O(M(n) log n) operations in R.

Part II — Fast interpolation

* 1. Explain how to perform Lagrange interpolation.

Hint: an element a in R is invertible if there is a b in R such that ab = e, with e a unit in R.

2. Let si = ∏	n 1	m/(x − uj ) and that
	i ̸=j 1/(ui − uj ). Prove that m′, the derivative of m, is m′ = ∑j =0−

m^′(u_i ) = 1/s_i .

3. Devise a divide and conquer algorithm which proceeds from the leaves to the root of the binary tree from part I question 1, in order to return the interpolation of P at the points u₀, · · · , u_n−1. Hint: use the M_i , j to apply a recursive approach to Lagrange interpolation.

3. Correctness and complexity.

* a) By induction on k, prove the correctness of the previous algorithm.

3. • 2. Prove that computing the s_i in question 2, amounts to O(M(n) log n) operations in R.

3. • 2. Conclude that the interpolation problem can be solved in O(M(n) log n) ring operations.

3. Discuss the possibility of pre-computing the subproducts M_i , j.

Ex. 2 — Critical thinking

• • 1. Let G be a group such that for all x, y in G , (xy)² = (yx)², and for any x ≠ e, x² ≠ e, where e is a unit element. Prove that G is abelian.

• • 2. After passing ve477 two students, s₁ and s₂, are asked to determine two integers x and y such that 1 < x < y and x + y < 100. Student s₁ is told that x + y , while s₂ is given xy. Remembering the importance of critical thinking they start discussing:

S₂ : “No idea what those two numbers could be…”

S₁ : “I’m not surprised, I knew you couldn’t know!”

S₂ : “Uhm…so now I know…”

S₁ : “So do I!” What about you?

* Ex. 3 — Beyond ve477

Explain what the Swype keyboard is and propose some hints on how it could be implemented.

• Ex. 4 — Course survey

Complete the course survey and get a +5 bonus on the homework.