2.11 Is Matrix Inversion an N3 Process? 103 in terms of which c11=Q1+Q4-Q5+Q7 c21=Q2+Q4 (2.11.4) c12=Q3+Q5 c22=Q1+Q3-Q2+Q6 What's the use of this?There is one fewer multiplication than in equation (2.11.2),but many more additions and subtractions.It is not clear that anything has been gained.But notice that in (2.11.3)the a's and b's are never commuted. Therefore(2.11.3)and(2.11.4)are valid when the a's and b's are themselves matrices. The problem of multiplying two very large matrices(of order N =2m for some 不 integer m)can now be broken down recursively by partitioning the matrices into quarters,sixteenths,etc.And note the key point:The savings is not just a factor "7/8";it is that factor at each hierarchical level of the recursion.In total it reduces RECIPES I the process of matrix multiplication to order Nlog7 instead of N3. What about all the extra additions in (2.11.3)-(2.11.4)?Don't they outweigh the advantage of the fewer multiplications?For large N,it turns out that there are University Press. 斋 six times as many additions as multiplications implied by (2.11.3)(2.11.4).But, if N is very large,this constant factor is no match for the change in the exponent from N3 to Nlog2 7 With this "fast"matrix multiplication,Strassen also obtained a surprising result Programs for matrix inversion[1].Suppose that the matrices 兴 OF SCIENTIFIC( a11 a12 and C11 C12 (2.11.5) 6 a21 a22 C21 C22 are inverses of each other.Then the c's can be obtained from the a's by the following operations (compare equations 2.7.22 and 2.7.25): COMPUTING (ISBN R1 Inverse(a11) @cambri 1988-1992 by Numerical Recipes 10-621 R2=a21×R Rg=R1×a12 R4=a21×R3 (outside 膜 R5=R4-a22 North Software. R6=Inverse(Rs) (2.11.6) C12 R3 X R6 C21=R6 X R2 R7=R3×c21 c11=R1-R7 c22=-R62.11 Is Matrix Inversion an N 3 Process? 103 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). in terms of which c11 = Q1 + Q4 − Q5 + Q7 c21 = Q2 + Q4 c12 = Q3 + Q5 c22 = Q1 + Q3 − Q2 + Q6 (2.11.4) What’s the use of this? There is one fewer multiplication than in equation (2.11.2), but many more additions and subtractions. It is not clear that anything has been gained. But notice that in (2.11.3) the a’s and b’s are never commuted. Therefore (2.11.3) and (2.11.4) are valid when the a’s and b’s are themselves matrices. The problem of multiplying two very large matrices (of order N = 2 m for some integer m) can now be broken down recursively by partitioning the matrices into quarters, sixteenths, etc. And note the key point: The savings is not just a factor “7/8”; it is that factor at each hierarchical level of the recursion. In total it reduces the process of matrix multiplication to order N log2 7 instead of N3. What about all the extra additions in (2.11.3)–(2.11.4)? Don’t they outweigh the advantage of the fewer multiplications? For large N, it turns out that there are six times as many additions as multiplications implied by (2.11.3)–(2.11.4). But, if N is very large, this constant factor is no match for the change in the exponent from N3 to Nlog2 7. With this “fast” matrix multiplication, Strassen also obtained a surprising result for matrix inversion [1]. Suppose that the matrices
a11 a12 a21 a22 and
c11 c12 c21 c22 (2.11.5) are inverses of each other. Then the c’s can be obtained from the a’s by the following operations (compare equations 2.7.22 and 2.7.25): R1 = Inverse(a11) R2 = a21 × R1 R3 = R1 × a12 R4 = a21 × R3 R5 = R4 − a22 R6 = Inverse(R5) c12 = R3 × R6 c21 = R6 × R2 R7 = R3 × c21 c11 = R1 − R7 c22 = −R6 (2.11.6)