102 Chapter 2.Solution of Linear Algebraic Equations We will make use of QR decomposition,and its updating,in 89.7. CITED REFERENCES AND FURTHER READING: Wilkinson,J.H.,and Reinsch,C.1971,Linear Algebra,vol.Il of Handbook for Automatic Com- putation (New York:Springer-Verlag),Chapter 1/8.[1] Golub,G.H.,and Van Loan,C.F.1989,Matrix Computations,2nd ed.(Baltimore:Johns Hopkins University Press),885.2,5.3,12.6.[2] 2.11 Is Matrix Inversion an N3 Process? We close this chapter with a little entertainment,a bit of algorithmic prestidig- itation which probes more deeply into the subject of matrix inversion.We start with a seemingly simple question: How many individual multiplications does it take to perform the matrix mul- tiplication of two 2 x 2 matrices. University Press. THE a12 (2.11.1) 121 a22 Programs Eight,right?Here they are written explicitly: 爱 OF SCIENTIFIC( 61 c11=a11×b11+a12×b21 c12=a11×b12+a12×b22 (2.11.2) c21=a21×b11+a22×b21 C22=a21×b12+a22×b22 Do you think that one can write formulas for the c's that involve only seven 是留会 10-621 4310-5 multiplications?(Try it yourself,before reading on.) Numerical Recipes Such a set of formulas was,in fact,discovered by Strassen [11.The formulas are: (outside Q1≡(a11+a22）×(b11+b22) North Software. Q2≡(a21+a22)×b11 Q3≡a11×(b12-b22) Q4三a22×(-b11+b21) (2.11.3) Q5三(a11+a12）×b22 Q6≡(-a11+a21)×(b11+b2) Qr≡(a12-a22)×(b21+b22)102 Chapter 2. Solution of Linear Algebraic Equations Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). We will make use of QR decomposition, and its updating, in §9.7. CITED REFERENCES AND FURTHER READING: Wilkinson, J.H., and Reinsch, C. 1971, Linear Algebra, vol. II of Handbook for Automatic Com￾putation (New York: Springer-Verlag), Chapter I/8. [1] Golub, G.H., and Van Loan, C.F. 1989, Matrix Computations, 2nd ed. (Baltimore: Johns Hopkins University Press), §§5.2, 5.3, 12.6. [2] 2.11 Is Matrix Inversion an N3 Process? We close this chapter with a little entertainment, a bit of algorithmic prestidig￾itation which probes more deeply into the subject of matrix inversion. We start with a seemingly simple question: How many individual multiplications does it take to perform the matrix mul￾tiplication of two 2 × 2 matrices,
a11 a12 a21 a22 ·
b11 b12 b21 b22 =
c11 c12 c21 c22 (2.11.1) Eight, right? Here they are written explicitly: c11 = a11 × b11 + a12 × b21 c12 = a11 × b12 + a12 × b22 c21 = a21 × b11 + a22 × b21 c22 = a21 × b12 + a22 × b22 (2.11.2) Do you think that one can write formulas for the c’s that involve only seven multiplications? (Try it yourself, before reading on.) Such a set of formulas was, in fact, discovered by Strassen [1]. The formulas are: Q1 ≡ (a11 + a22) × (b11 + b22) Q2 ≡ (a21 + a22) × b11 Q3 ≡ a11 × (b12 − b22) Q4 ≡ a22 × (−b11 + b21) Q5 ≡ (a11 + a12) × b22 Q6 ≡ (−a11 + a21) × (b11 + b12) Q7 ≡ (a12 − a22) × (b21 + b22) (2.11.3)