2.27. The square of a matrix A is its product with itself, AA. (a) Show that...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
2.27. The square of a matrix A is its product with itself, AA. (a) Show that five multiplications are sufficient to compute the square of a 2 2 matrix. (b) What is wrong with the following algorithm for computing the square of an n n matrix? "Use a divide-and-conquer approach as in Strassen's algorithm, except that in- stead of getting 7 subproblems of size n/2, we now get 5 subproblems of size n/2 thanks to part (a). Using the same analysis as in Strassen's algorithm, we can conclude that the algorithm runs in time O(nlog25)." (c) In fact, squaring matrices is no easier than matrix multiplication. In this part, you will show that if n x n matrices can be squared in time S(n) = O(nc), then any two n x n matrices can be multiplied in time O(nc). i. Given two n x n matrices A and B, show that the matrix AB + BA can be computed in time 3S(n) + O(n). ii. Given two n x n matrices X and Y, define the 2n x 2n matrices A and B as follows: X 0 A = [ and B = 0 0 0 Y 0 0 [ 8 X ]. What is AB + BA, in terms of X and Y? iii. Using (i) and (ii), argue that the product XY can be computed in time 3S(2n) + O(n). Conclude that matrix multiplication takes time O(n). 2.27. The square of a matrix A is its product with itself, AA. (a) Show that five multiplications are sufficient to compute the square of a 2 2 matrix. (b) What is wrong with the following algorithm for computing the square of an n n matrix? "Use a divide-and-conquer approach as in Strassen's algorithm, except that in- stead of getting 7 subproblems of size n/2, we now get 5 subproblems of size n/2 thanks to part (a). Using the same analysis as in Strassen's algorithm, we can conclude that the algorithm runs in time O(nlog25)." (c) In fact, squaring matrices is no easier than matrix multiplication. In this part, you will show that if n x n matrices can be squared in time S(n) = O(nc), then any two n x n matrices can be multiplied in time O(nc). i. Given two n x n matrices A and B, show that the matrix AB + BA can be computed in time 3S(n) + O(n). ii. Given two n x n matrices X and Y, define the 2n x 2n matrices A and B as follows: X 0 A = [ and B = 0 0 0 Y 0 0 [ 8 X ]. What is AB + BA, in terms of X and Y? iii. Using (i) and (ii), argue that the product XY can be computed in time 3S(2n) + O(n). Conclude that matrix multiplication takes time O(n).
Expert Answer:
Related Book For
Data Analysis and Decision Making
ISBN: 978-0538476126
4th edition
Authors: Christian Albright, Wayne Winston, Christopher Zappe
Posted Date:
Students also viewed these programming questions
-
The population of a certain country was studied in an article. The authors examined the different occupations for males and females in the country. The accompanying table is a frequency distribution...
-
Q1. You have identified a market opportunity for home media players that would cater for older members of the population. Many older people have difficulty in understanding the operating principles...
-
Python and most Python libraries are free to download or use, though many users use Python through a paid service. Paid services help IT organizations manage the risks associated with the use of...
-
Which statement is correct? A) Tax credits reduce tax liability on a dollar-for-dollarbasis. B) Tax deductions reduce tax liability on a dollar-for-dollarbasis. C) The benefit of a tax credit depends...
-
Select several specific parts in a typical automobile, I and identify the processes described in this chapter that can be used to make those parts. Explain your reasoning.
-
Consider a failing bank. A deposit of $180,000 is worth how much if the FDIC uses the payoff method? The purchase-and-assumption method? Which is more costly to tax payers?
-
Christina decides to save money for after graduation. Christina starts by setting aside \(\$ 10\). Each week, Christina increases the amount she saves by \(\$ 5\). How much money will Christina save...
-
Goltra Clinic is considering investing in new heart monitoring equipment. It has two options: Option A would have an initial lower cost but would require a significant expenditure for rebuilding...
-
Cullumber Limited purchased delivery equipment on March 1, 2016, for $117,500 cash. At that time, the equipment was estimated to have a useful life of five years and a residual value of $10,010....
-
Please Help!! will upvote! Boxwood Company sells blankets for 540 each. The following information was taken from the inventory records during May. The company had no beginning inventory on May 1....
-
1.What was the Lehman purchase and how important was it to Barclay's in terms of their corporate strategy? Did Barclays get a good price from the receivers? Explain. By the way, what is a receiver...
-
Plan finances for new business ventures in Australia Profit, loss and cash flow projections Monthly projected $ sales Jul Aug Sep Oct Nov Dec Jan Feb Mar Apr May Jun Total Coffee regular $ 8,734...
-
Analysis these 3 Financial ratios. Price-to-Earnings Ratio (P/E Ratio), Debt-to-Equity Ratio and Inventory Turnover Ratio in this company: Incitec Pivot limited (IPL) over the past 5 financial years,...
-
In our reading about Ethical Considerations, the authors of the text outline several ethical principles of communication. Which of these principles is the most important to our study of intercultural...
-
I am representing my client in a mock case and my client has had two DUIs in one month with a BAC reading of .30 and .32 My opponent may go for my client to do jail time or fine but I want to present...
-
You have set up a small factory with a monthly rental of 10,000 and an annual insurance of 6000 to produce a consumable item. You spend 3 and 4 per unit respectively towards the raw material and the...
-
On October 1, 2014, the Dow Jones Industrial Average (DJIA) opened at 17,042 points. During that day it lost 237 points. On October 2 it lost 4 points. On October 3 it gained 209 points. Deter-mine...
-
Holts method assumes an additive trend. For example, a trend of five means that the level will increase by five units per period. Suppose that there is actually a multiplicative trend. For example,...
-
The Pierce Company manufactures drill bits. The production of the drill bits occurs in lots of 1000 units. Due to the intense competition in the industry and the correspondingly low prices, Pierce...
-
The file S12_72.xlsx contains data on a motel chains revenue and advertising. a. Use these data and multiple regression to make predictions of the motel chains revenues during the next four quarters....
-
1.12 Andreas Delon's Compensation. Andreas Delon is a French citizen who has been offered the position of CEO of LakePharma, a large French pharmaceuticals firm. LakePharma produces high-quality...
-
1.11 Peng Plasma Pricing. Peng Plasma is a privately held Chinese business. It specializes in the manufacture of plasma cutting torches. Over the past eight years, it has held the Chinese renminbi...
-
1.13 Euro Virtual's Consolidated Earnings. Euro Vir- tual pays different tax rates for each of its country operations. a. What are its earnings per share in euros after deducting taxes? b. What is...
Study smarter with the SolutionInn App