104 Chapter 2.Solution of Linear Algebraic Equations In(2.11.6)the"inverse"operator occurs just twice.It is to be interpreted as the reciprocal if the a's and c's are scalars,but as matrix inversion if the a's and c's are themselves submatrices.Imagine doing the inversion of a very large matrix,of order N=2m,recursively by partitions in half.At each step,halving the order doubles the number of inverse operations.But this means that there are only N divisions in all!So divisions don't dominate in the recursive use of(2.11.6).Equation (2.11.6) is dominated,in fact,by its 6 multiplications.Since these can be done by an Nlog27 algorithm,so can the matrix inversion! This is fun,but let's look at practicalities:If you estimate how large N has to be before the difference between exponent 3 and exponent log2 7=2.807 is substantial enough to outweigh the bookkeeping overhead.arising from the complicated nature of the recursive Strassen algorithm,you will find that LU decomposition is in no immediate danger of becoming obsolete. If,on the other hand,you like this kind of fun,then try these:(1)Can you 83g 18881992 1-800 multiply the complex numbers (a+ib)and(c+id)in only three real multiplications? [Answer:see $5.4.](2)Can you evaluate a general fourth-degree polynomial in to any from NUMERICAL RECIPES IN x for many different values of x with only three multiplications per evaluation? Answer: see 85.3.1 CITED REFERENCES AND FURTHER READING: (North America 州bMe se to make one paper THE Strassen.V.1969,Numerische Mathematik,vol.13,pp.354-356.[1] ART Kronsjo,L.1987,Algorithms:Their Complexity and Efficiency,2nd ed.(New York:Wiley). Winograd,S.1971.Linear Algebra and Its Applications,vol.4.pp.381-388 Programs Pan,V.Ya.1980,SIAM Journal on Computing,vol.9,pp.321-342. Pan,V.1984,How to Multiply Matrices Faster,Lecture Notes in Computer Science,vol.179 (New York:Springer-Verlag) Pan,V.1984,SIAM Review,vol.26,pp.393-415.[More recent results that show that an exponent of 2.496 can be achieved-theoretically!] Ito directcustserv@cambridge.org (outside North America). 1988-1992 by Numerical Recipes OF SCIENTIFIC COMPUTING(ISBN 0-521-43108-5) Software.104 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). In (2.11.6) the “inverse” operator occurs just twice. It is to be interpreted as the reciprocal if the a’s and c’s are scalars, but as matrix inversion if the a’s and c’s are themselves submatrices. Imagine doing the inversion of a very large matrix, of order N = 2m, recursively by partitions in half. At each step, halving the order doubles the number of inverse operations. But this means that there are only N divisions in all! So divisions don’t dominate in the recursive use of (2.11.6). Equation (2.11.6) is dominated, in fact, by its 6 multiplications. Since these can be done by an N log2 7 algorithm, so can the matrix inversion! This is fun, but let’s look at practicalities: If you estimate how large N has to be before the difference between exponent 3 and exponent log 2 7=2.807 is substantial enough to outweigh the bookkeeping overhead, arising from the complicated nature of the recursive Strassen algorithm, you will find that LU decomposition is in no immediate danger of becoming obsolete. If, on the other hand, you like this kind of fun, then try these: (1) Can you multiply the complex numbers(a+ib) and (c+id)in only three real multiplications? [Answer: see §5.4.] (2) Can you evaluate a general fourth-degree polynomial in x for many different values of x with only three multiplications per evaluation? [Answer: see §5.3.] CITED REFERENCES AND FURTHER READING: Strassen, V. 1969, Numerische Mathematik, vol. 13, pp. 354–356. [1] Kronsj¨o, L. 1987, Algorithms: Their Complexity and Efficiency, 2nd ed. (New York: Wiley). Winograd, S. 1971, Linear Algebra and Its Applications, vol. 4, pp. 381–388. Pan, V. Ya. 1980, SIAM Journal on Computing, vol. 9, pp. 321–342. Pan, V. 1984, How to Multiply Matrices Faster, Lecture Notes in Computer Science, vol. 179 (New York: Springer-Verlag) Pan, V. 1984, SIAM Review, vol. 26, pp. 393–415. [More recent results that show that an exponent of 2.496 can be achieved — theoretically!]