Cashback Offer (25th Nov-05th Dec 2020). Get Flat 10% Cashback credited in your account on a minimum transaction of $80. Post Your Question

Question DetailsNormal
$ 20.00

CSC 505 Homework #1 | Problem No.6

Question posted by
Online Tutor Profile
request

6. [worth 5 points] Applying analysis of divide and conquer to a concrete problem.
The dominant operations in Strassen's matrix multiplication algorithm, particularly if the numbers being manipu-lated are multiple precision (take up more than one machine word), are scalar multiplications and scalar additions.

Recurrences for these two operations are as follows.
M(n) = 7M(n=2) note: no scalar multiplications are done before or after any recursive calls
M(1) = 1
for scalar multiplications
A(n) = 7A(n=2) + 10(n=2)2 there are 10 additions of n=2 n=2 matrices
A(1) = 0
for scalar additions

Strassen's algorithm, even if you ignore bookkeeping overhead, is not a good choice for small matrices.

Your job is to gure out the exact value of n at which it makes sense to stop recursing and use the ordinary
matrix multiplication algorithm instead. The number of scalar operations for the ordinary algorithm are n3
multiplications and n3 additions (actually there are n3  n2 but let's not make things too complicated). To
simplify your calculations, assume that multiplication takes twice as long as addition.

You should express the answer as simply as possible (you may want to assume s is a power of 2 to start with and come up with a more exact value later; this is not exactly kosher, but it works). Do not convert logarithms into numbers, i.e., say lg 7 instead of 2:80735492206 or 2:81.


Rather than come up with a closed form solution for s you can leave it as nding the root of a polynomial (one of the terms will be a non-integer power). You should then use a sophisticated calculator, MatLab, or any program that works to interpolate (using, e.g., binary search or Newton's method) an exact value for s. The result should be rounded up to the next power of 2.


3 points for coming up with the right recurrences with a base case that is not 1 and evaluating them;
2 points for the remaining details.


For up to 10 points extra credit, do an experiment to determine the best value for n at which to stop the recursion.
You can get up to 3 points for a detailed description of how such an experiment should be conducted. Submit your description, a writeup of your experiment, and your code with instructions for compiling and running it on a Unix-based system to the h1ex locker. It should be a zip archive with the name h1ex uid.zip, where uid is your unity login id.

Available Answer
$ 20.00

[Solved] CSC 505 Homework #1 | Problem No.6

  • This Solution has been Purchased 3 time
  • Submitted On 09 Dec, 2014 07:31:35
Answer posted by
Online Tutor Profile
solution

Strassen’s matrix multiplication:

Strassen’s showed that 2x2 matrix multiplications can be accomplished in 7 Multi...

Buy now to view the complete solution
Other Similar Questions
User Profile
vpqnr...

CSC 505 Homework #1 Problem 6 complete solution correct answer key

Strassen’s matrix multiplication: Strassen’s showed that 2x2 matrix multiplications can be accomplished in 7 Multiplications and 18 additions or subtractions. • This reduction can be done by divide and conquer app...
User Profile
Exper...

CSC 505 Homework #1 | Problem No.6

Strassen’s matrix multiplication:

Strassen’s showed that 2x2 matrix multiplications can be accomplished in 7 Multiplications and 18 additions or subtractions.   

•    T...

The benefits of buying study notes from CourseMerit

homeworkhelptime
Assurance Of Timely Delivery
We value your patience, and to ensure you always receive your homework help within the promised time, our dedicated team of tutors begins their work as soon as the request arrives.
tutoring
Best Price In The Market
All the services that are available on our page cost only a nominal amount of money. In fact, the prices are lower than the industry standards. You can always expect value for money from us.
tutorsupport
Uninterrupted 24/7 Support
Our customer support wing remains online 24x7 to provide you seamless assistance. Also, when you post a query or a request here, you can expect an immediate response from our side.
closebutton

$ 629.35