chap31.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

<a name="0973_1a91">31.2-2<a name="0973_1a91"><P>
How would you modify Strassen<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm to multiply <I>n</I> <img src="../images/mult.gif"> <I>n</I> matrices in which <I>n</I> is not an exact power of 2? Show that the resulting algorithm runs in time <img src="../images/bound.gif">(<I>n</I><SUP>1g 7</SUP>).<P>
<a name="0973_1a92">31.2-3<a name="0973_1a92"><P>
What is the largest <I>k</I> such that if you can multiply 3 <img src="../images/mult.gif"> 3 matrices using <I>k </I>multiplications (not assuming commutativity of multiplication), then you can multiply <I>n</I> <img src="../images/mult.gif"> <I>n</I> matrices in time <I>o</I>(<I>n</I><SUP>1g 7</SUP>)? What would the running time of this algorithm be?<P>
<a name="0973_1a93">31.2-4<a name="0973_1a93"><P>
<a name="0973_1a8b"><a name="0973_1a8c">V. Pan has discovered a way of multiplying 68 <img src="../images/mult.gif"> 68 matrices using 132,464 multiplications, a way of multiplying 70 <img src="../images/mult.gif"> 70 matrices using 143,640 multiplications, and a way of multiplying 72 <img src="../images/mult.gif"> 72 matrices using 155,424 multiplications. Which method yields the best asymptotic running time when used in a divide-and-conquer matrix-multiplication algorithm? Compare it with the running time for Strassen<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm.<P>
<a name="0973_1a94">131.2-5<a name="0973_1a94"><P>
How quickly can you multiply a <I>kn</I> <img src="../images/mult.gif"> <I>n</I> matrix by an <I>n</I> <img src="../images/mult.gif"> <I>kn</I> matrix, using Strassen<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm as a subroutine? Answer the same question with the order of the input matrices reversed.<P>
<a name="0973_1a95">31.2-6<a name="0973_1a95"><P>
<a name="0973_1a8d"><a name="0973_1a8e">Show how to multiply the complex numbers <I>a</I> + <I>bi</I> and <I>c</I> + <I>di</I> using only three real multiplications. The algorithm should take <I>a</I>, <I>b</I>, <I>c</I>, and <I>d</I> as input and produce the real component <I>ac</I> - <I>bd</I> and the imaginary component <I>ad</I> + <I>bc</I> separately.<P>
<P>


<P>







<h1><a name="0974_0001">* 31.3 Algebraic number systems and boolean matrix multiplication<a name="0974_0001"></h1><P>
The properties of matrix addition and multiplication depend on the properties of the underlying number system. In this section, we define three different kinds of underlying number systems: quasirings, rings, and fields. We can define matrix multiplication over quasirings, and Strassen<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s matrix-multiplication algorithm works over rings. We then present a simple trick for reducing boolean matrix multiplication, which is defined over a quasiring that is not a ring, to multiplication over a ring. Finally, we discuss why the properties of a field cannot naturally be exploited to provide better algorithms for matrix multiplication.<P>





<h2>Quasirings</h2><P>
<a name="0975_1a8f"><a name="0975_1a90">Let <img src="745_a.gif"> denote a number system, where <I>S</I> is a set of elements, <img src="../images/xor14.gif"> and <img src="745_b.gif"> are binary operations on <I>S</I> (the addition and multiplication operations, respectively), and <img src="745_c.gif"> are distinct distinguished elements of <I>S</I>. This system is a <I><B>quasiring</I></B> if it satisfies the following properties:<P>
<a name="0975_1a91">1.     <img src="745_d.gif"> is a <I><B>monoid</I></B>:<P>
<a name="0975_1a92"><img src="../images/dot12.gif">     <I>S</I> is <I><B>closed</I></B> under <img src="../images/xor14.gif">; that is, <I>a</I> <img src="../images/xor14.gif"> <I>b</I> <img src="../images/memof12.gif"> <I>S</I> for all <I>a</I>, <I>b</I> <img src="../images/memof12.gif"> <I>S</I>.<P>
<a name="0975_1a93"><img src="../images/dot12.gif">     <img src="../images/xor14.gif"> is <I><B>associative</I></B>; that is, <I>a</I> <img src="../images/xor14.gif"> (<I>b</I> <img src="../images/xor14.gif"> <I>c</I>) = (<I>a</I> <img src="../images/xor14.gif"> <I>b</I>) <img src="../images/xor14.gif"> <I>c</I> for all <I>a</I>, <I>b</I>, <I>c</I> <img src="../images/memof12.gif"> <I>S</I>.<P>
<a name="0975_1a94"><img src="../images/dot12.gif">     <img src="745_e.gif"> is an <I><B>identity</I></B> for <img src="../images/xor14.gif">; that is, <img src="745_f.gif"> for all <I>a</I> <img src="../images/memof12.gif"> <I>S</I>.<P>
Likewise, <img src="745_g.gif"> is a monoid.<P>
<a name="0975_1a95">2.     <img src="745_h.gif"> is an <I><B>annihilator</I></B>, that is, <img src="745_i.gif"> for all <I>a</I> <img src="../images/memof12.gif"> <I>S</I>.<P>
<a name="0975_1a96">3.     The operator <img src="../images/xor14.gif"> is <I><B>commutative</I></B>; that is, <I>a </I><img src="../images/xor14.gif"><I> b</I> = <I>b </I><img src="../images/xor14.gif"><I> a</I> for all <I>a, b </I><img src="../images/memof12.gif"><I> S</I>.<P>
<a name="0975_1a97">4.     The operator <img src="745_j.gif"> <I><B>distributes</I></B> over <img src="../images/xor14.gif">; that is, <img src="745_k.gif"> and <img src="745_l.gif"> for all <I>a,b,c </I><img src="../images/memof12.gif"><I> S</I>.<P>
<a name="0975_1a98"><a name="0975_1a99"><a name="0975_1a9a"><a name="0975_1a9b"><a name="0975_1a9c"><a name="0975_1a9d">Examples of quasirings include the <I><B>boolean quasiring</I></B> ({0,1}, <FONT FACE="Times New Roman" SIZE=4><img src="../images/angledwn.gif"></FONT>, <FONT FACE="Times New Roman" SIZE=4><img src="../images/angleup.gif"></FONT>, 0, 1), where <FONT FACE="Times New Roman" SIZE=4><img src="../images/angledwn.gif"></FONT> denotes logical OR and <FONT FACE="Times New Roman" SIZE=4><img src="../images/angleup.gif"></FONT> denotes logical AND, and the natural number system (<B>N</B>, +, <img src="../images/dot10.gif">, 0, 1), where + and <img src="../images/dot10.gif"> denote ordinary addition and multiplication. Any closed semiring (see Section 26.4) is also a quasiring; closed semirings obey additional idempotence and infinite-sum properties.<P>
We can extend <img src="../images/xor14.gif"> and <img src="746_a.gif"> to matrices as we did for + and <img src="../images/dot10.gif"> in Section 31.1. Denoting the <I>n</I> <img src="../images/mult.gif"> <I>n</I> identity matrix composed of <img src="746_b.gif"> we find that matrix multiplication is well defined and the matrix system is itself a quasiring, as the following theorem states.<P>
<a name="0975_1a9f">Theorem 31.7<a name="0975_1a9f"><P>
<a name="0975_1a9e">If <img src="746_c.gif"> is a quasiring and <I>n</I> <img src="../images/gteq.gif"> 1, then <img src="746_d.gif"> is a quasiring.<P>
<I><B>Proof     </I></B>The proof is left as Exercise 31.3-3.      <P>
<P>







<h2>Rings</h2><P>
<a name="0976_1a9f"><a name="0976_1aa0">Subtraction is not defined for quasirings, but it is for a <I><B>ring</I></B>, which is a quasiring <img src="746_e.gif"> that satisfies the following additional property:<P>
<a name="0976_1aa1"><a name="0976_1aa2"><a name="0976_1aa3">5.     Every element in <I>S</I> has an <I><B>additive inverse</I></B>; that is, for all <I>a </I><img src="../images/memof12.gif"><I> S,</I> there exists an element <I>b </I><img src="../images/memof12.gif"><I> S</I> such that <img src="746_f.gif">. Such a <I>b</I> is also called the <I><B>negative</I></B> of <I>a</I> and is denoted (-<I>a</I>).<P>
Given that the negative of any element is defined, we can define subtraction by <I>a </I>- <I>b</I> = <I>a </I>+ (-<I>b</I>).<P>
There are many examples of rings. The integers (<B>Z</B>, +, <img src="../images/dot10.gif">, 0, 1) under the usual operations of addition and multiplication form a ring. The integers modulo <I>n</I> for any integer <I>n</I> &gt; 1<FONT FACE="CG Times (W1)" SIZE=2>--</FONT>that is, (<B>Z</B><I><SUB>n</I></SUB>, +, <img src="../images/dot10.gif">, 0, 1), where + is addition modulo <I>n</I> and <img src="../images/dot10.gif"> is multiplication modulo <I>n</I>--form a ring. Another example is the set <B>R</B>[<I>x</I>] of finite-degree polynomials in <I>x</I> with real coefficients under the usual operations--that is, (<B>R</B>[<I>x</I>], +, <img src="../images/dot10.gif">, 0, 1), where + is polynomial addition and <img src="../images/dot10.gif"> is polynomial multiplication.<P>
The following corollary shows that Theorem 31.7 generalizes naturally to rings.<P>
<a name="0976_1aa4">Corollary 31.8<a name="0976_1aa4"><P>
If <img src="746_g.gif"> is a ring and <I>n</I> <img src="../images/gteq.gif"> 1, then <img src="746_h.gif"> is a ring.<P>
<I><B>Proof     </I></B>The proof is left as Exercise 31.3-3.      <P>
Using this corollary, we can prove the following theorem.<P>
<a name="0976_1aa5">Theorem 31.9<a name="0976_1aa5"><P>
Strassen's matrix-multiplication algorithm works properly over any ring of matrix elements.<P>
<I><B>Proof     </I></B>Strassen's algorithm depends on the correctness of the algorithm for 2 <img src="../images/mult.gif"> 2 matrices, which requires only that the matrix elements belong to a ring. Since the matrix elements do belong to a ring, Corollary 31.8 implies the matrices themselves form a ring. Thus, by induction, Strassen's algorithm works correctly at each level of recursion.      <P>
Strassen's algorithm for matrix multiplication, in fact, depends critically on the existence of additive inverses. Out of the seven products <I>P</I><SUB>1</SUB>,<I> P</I><SUB>2</SUB>, . . . ,<I>P</I><SUB>7</SUB>, four involve differences of submatrices. Thus, Strassen's algorithm does not work in general for quasirings.<P>
<P>







<h2>Boolean matrix multiplication</h2><P>
<a name="0977_1aa4"><a name="0977_1aa5"><a name="0977_1aa6">Strassen's algorithm cannot be used directly to multiply boolean matrices, since the boolean quasiring ({0,1}, <FONT FACE="Times New Roman" SIZE=4><img src="../images/angledwn.gif"></FONT>, <FONT FACE="Times New Roman" SIZE=4><img src="../images/angleup.gif"></FONT>, 0, 1) is not a ring. There are instances in which a quasiring is contained in a larger system that is a ring. For example, the natural numbers (a quasiring) are a subset of the integers (a ring), and Strassen's algorithm can therefore be used to multiply matrices of natural numbers if we consider the underlying number system to be the integers. Unfortunately, the boolean quasiring cannot be extended in a similar way to a ring. (See Exercise 31.3-4.)<P>
The following theorem presents a simple trick for reducing boolean matrix multiplication to multiplication over a ring. Problem 31-1 presents another efficient approach.<P>
<a name="0977_1aa7">Theorem 31.10<a name="0977_1aa7"><P>
If <I>M</I>(<I>n</I>) denotes the number of arithmetic operations required to multiply two <I>n</I> <img src="../images/mult.gif"> <I>n</I> matrices over the integers, then two <I>n</I> <FONT FACE="Times" SIZE=2><img src="../images/mult.gif"></FONT> <I>n</I> boolean matrices can be multiplied using <I>O</I>(<I>M</I>(<I>n</I>)) arithmetic operations.<P>
<I><B>Proof     </I></B>Let the two matrices be <I>A</I> and <I>B,</I> and let <I>C </I>= <I>AB</I> in the boolean quasiring, that is,<P>
<img src="747_a.gif"><P>
Instead of computing over the boolean quasiring, we compute the product <I>C</I>' over the ring of integers with the given matrix-multiplication algorithm that uses <I>M</I>(<I>n</I>) arithmetic operations. We thus have<P>
<img src="747_b.gif"><P>
Each term <I>a<SUB>ik</SUB>b<SUB>kj</I></SUB> of this sum is 0 if and only if <I>a<SUB>ik</I></SUB> <FONT FACE="Times New Roman" SIZE=4><img src="../images/angleup.gif"></FONT> <I>b<SUB>kj</I> </SUB>= 0, and 1 if and only if <I>a<SUB>ik</SUB><FONT FACE="Times New Roman" SIZE=4> </I><img src="../images/angleup.gif"><I> b<SUB>kj</I></FONT></SUB> = 1. Thus, the integer sum <img src="748_a.gif"> is 0 if and only if every term is 0 or, equivalently, if and only if the boolean OR of the terms, which is <I>c<SUB>ij</I></SUB>, is 0. Therefore, the boolean matrix <I>C</I> can be reconstructed with <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) arithmetic operations from the integer matrix <I>C</I>' by simply comparing each <img src="748_b.gif"> with 0. The number of arithmetic operations for the entire procedure is then <I>O</I>(<I>M</I>(<I>n</I>)) +<img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) = <I>O</I>(<I>M</I>(<I>n</I>)), since <I>M</I>(<I>n</I>) = <img src="../images/omega12.gif">(<I>n</I><SUP>2</SUP>).      <P>
Thus, using Strassen's algorithm, we can perform boolean matrix multiplication in <I>O</I>(<I>n </I><SUP>lg 7</SUP>) time.<P>
The normal method of multiplying boolean matrices uses only boolean variables. If we use this adaptation of Strassen's algorithm, however, the final product matrix can have entries as large as <I>n</I>, thus requiring a computer word to store them rather than a single bit. More worrisome is that the intermediate results, which are integers, may grow even larger. One method for keeping intermediate results from growing too large is to perform all computations modulo <I>n</I> + 1. Exercise 31.3-5 asks you to show that working modulo <I>n</I> + 1 does not affect the correctness of the algorithm.<P>
<P>







<h2>Fields</h2><P>
<a name="0978_1aa7">A ring <img src="748_c.gif"> is a <I><B>field</I></B> if it satisfies the following two additional properties:<P>
<a name="0978_1aa8">6.     The operator <img src="748_d.gif"> is <I><B>commutative</I></B>; that is, <img src="748_e.gif"> for all <I>a, b</I> <img src="../images/memof12.gif"> <I>S</I>.<P>
<a name="0978_1aa9"><a name="0978_1aaa">7.     Every nonzero element in <I>S</I> has a <I><B>multiplicative inverse</I></B>; that is, for all <img src="748_f.gif">, there exists an element <I>b</I> <img src="../images/memof12.gif"> <I>S</I> such that <img src="748_g.gif">.<P>
Such an element <I>b</I> is often called the i<I><B>nverse</I></B> of <I>a</I> and is denoted <I>a</I><SUP>-1</SUP>.<P>
Examples of fields include the real numbers (<B>R</B>, +, <img src="../images/dot10.gif">, 0, 1), the complex numbers (<B>C</B>, +, <img src="../images/dot10.gif">, 0, 1), and the integers modulo a prime <I>p</I>: (<B>Z</B><I><SUB>p</I></SUB>, +, <img src="../images/dot10.gif">, 0, 1).<P>
Because fields offer multiplicative inverses of elements, division is possible. They also offer commutativity. By generalizing from quasirings to rings, Strassen was able to improve the running time of matrix multiplication. Since the underlying elements of matrices are often from a field--the real numbers, for instance--one might hope that by using fields instead of rings in a Strassen-like recursive algorithm, the running time might be further improved.<P>
This approach seems unlikely to be fruitful. For a recursive divide-and-conquer algorithm based on fields to work, the matrices at each step of the recursion must form a field. Unfortunately, the natural extension of Theorem 31.7 and Corollary 31.8 to fields fails badly. For <I>n</I> &gt; 1, the set of <I>n</I> <img src="../images/mult.gif"> <I>n</I> matrices <I>never</I> forms a field, even if the underlying number system is a field. Multiplication of <I>n</I> <FONT FACE="Times" SIZE=2><img src="../images/mult.gif"></FONT> <I>n</I> matrices is not commutative, and many <I>n</I> <FONT FACE="Times" SIZE=2><img src="../images/mult.gif"></FONT> <I>n</I> matrices do not have inverses. Better algorithms for matrix multiplication are therefore more likely to be based on ring theory than on field theory.<P>
<P>