Determining the smallest value of m by strassens algorithm

Question

Q1) This question is about determining when Strassen's Algorithm is faster than ordinary matrix multiplication, assuming that scalar addition and scalar multiplication take the same amount of time. Show all of your workings. Don't use the Master Method in this question.

(i) Explain why ordinary matrix multiplication of two n by n matrices involves 2n³-n² calculations. (Multiplication+Addition).

(ii) In Strassen's Algorithm, T(n), the total number of calculations (Multiplication+Addition) involved in multiplying two n by n matrices satisfies T(n) = 7T(n/2 ) + 9/2n² given T(1) = 1. Suppose n = 2^m. By considering the transformation G(m) = T(2^m) obtain a recursion equation for G(m) along with a condition on G(0).

(iii) Show that the solution to the recursion equation is G(m) = 7^m+1- 6 *4^m.

(iv) Hence show that T(n) = 7n^log₂7 -6n².

(v) Determine the smallest value of m for which Strassen's Algorithm involves fewer calculations than ordinary matrix multiplication.

Q2) In this question you will need to determine which of the 5 algorithms V to Z is quickest at solving a problem of input size n. The running time for each algorithm satisfies its own recursion equation given by:
Algorithm V: V (n) = 3V (n-1) + 4ⁿ with V (1) = 1
Algorithm W: W(n) = 3W(n-1) + 10n² + 20n + 40 with W(1) = 1
Algorithm X: X(n) = 3X(n -1) + 3ⁿ with X(1) = 1
Algorithm Y: Y (n) = 5Y (n - 1) - 4Y (n- 2) + 6n - 12 with Y (1) = 1; Y (2) = 2
Algorithm Z: Z(n) = 8Z(n - 1) - 15Z(n - 2) + 2ⁿ with Z(1) = 1; Z(2) = 2

(i) Obtain a closed form solution for the running time for each algorithm.
(These should be derived by hand without using Maple).

(ii) Use Maple to plot a suitable function of the running time against n for each algorithm on the same graph to illustrate how the choice of the most efficient algorithm changes with n. (Plotting multiple graphs may help to illustrate your argument).

(iii) By considering the running time for algorithm Z, simplify this expression 5ⁿ - 5(3ⁿ) + 2ⁿ⁺³ mod 6 for n   1
(Just state the answer and say why - no need to prove anything)

Q3) The running times of algorithms J, K, L and M are given by

Algorithm J: J(n) = 3J(n/4 ) + n with J(1) = 1

Algorithm K: K(n) = 5K(n/2 ) + n² with K(1) = 1

Algorithm L: L(n) = 6L(n/6 ) + n ln n with L(3) = 1

Algorithm M: M(n) = 2M(n/5 ) +M(n/3 ) + √n with M(1) = 1

(i) Explain how algorithms K & M divide up a problem of size n.
(ii) Sketch a recursion tree for algorithm J.
(iii) Using the Master Method, determine the asymptotic running times for each of the algorithms J, K & L.
(iv) Prove the 3 results that you obtained in (iii) are upper bounds on the running times of algorithms J, K & L, using proof by induction.
(v) Consider algorithm M and suppose p > 0.5 such that M(n) = O(n^p).
(a) By seeking the tightest possible upper bound on M determine p.
(b) Using proof by induction show that M(n) <=cn^p + d √n where c and d are chosen to make this upper bound as tight as possible.
(vi) Which of the algorithms J, K, L and M is asymptotically fastest?

Q4) This question is about solving nonlinear equations. You should ignore repeated roots. You cannot use any of Maple's built in `solve' type commands.

(i) Write a Maple procedure to numerically solve the coupled system of equations f(x; y) = 0 and g(x; y) = 0 with initial guesses x=x₀ and y=y₀ by extending the Newton-Raphson method to a system of 2 nonlinear equations.
(Use  nite di erences to evaluate the partial derivatives).

(ii) Using an initial guess of x0 = 1 and y0 = -1 test your procedure by obtaining one
solution, accurate to 5 decimal places, to this nonlinear system:
sin(5x) + 9- 3y² = 0
e^7y-4x + 6x- 8 = 0

Q5) In this question you are going to write a Maple program to determine the centre and radius of the smallest circle that encloses a set of points.
(i) Create a set A of 20 points located in a two dimensional space. The x and y coordinates of each point should be randomly assigned such that |x| <=100 and |y| <=100.

(ii) Determine the maximum and minimum values of x and y over the points in A. Define x₀ = 1/2(max(x) - min(x)) and y₀ = 1/2(max(y)- min(y)).
(iii) Calculate the radius, r₀, of a circle centred at the point (x0; y0) that encloses the set of points in A. Define dx = 1/10r₀.

(iv) Redefine dx as dx=1:1. By considering the resulting radius for each of the points (x₀- dx; y₀), (x_0, y₀), (x₀ + dx, y₀), (x₀, y₀- dx) and (x_0, y₀ + dx) choose a new value of x₀ and y₀ to reduce the radius.
(If none of the four new points reduces the radius, then leave x₀ and y₀ unchanged.)

(v) Iterate step (iv) 30 times.

(vi) Plot the points in set A along with a circle centred at the point (x₀, y₀) of the appropriate radius on the same graph.

(vii) Discuss any problems associated with successively reducing the value of dx.