📄 page457.html
字号:
<HTML><HEAD><TITLE>Example-Matrix Multiplication</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html6432" HREF="page458.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6430" HREF="page448.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6426" HREF="page456.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6434" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0014350000000000000000">Example-Matrix Multiplication</A></H2><A NAME="secalgsmatrix"> </A><P>Consider the problem of computing the product of two matrices.That is, given two <IMG WIDTH=38 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68097" SRC="img1809.gif" > matrices, <I>A</I> and <I>B</I>,compute the <IMG WIDTH=38 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68097" SRC="img1809.gif" > matrix <IMG WIDTH=76 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68105" SRC="img1810.gif" >,the elements of which are given by<P><A NAME="eqnalgsmatmul"> </A> <IMG WIDTH=500 HEIGHT=47 ALIGN=BOTTOM ALT="equation32949" SRC="img1811.gif" ><P>Section <A HREF="page96.html#secfdsmatmul"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows that the direct implementationof Equation <A HREF="page457.html#eqnalgsmatmul"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> results in an <IMG WIDTH=40 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58941" SRC="img329.gif" > running time.In this section we show that the use of a divide-and-conquerstrategy results in a slightly better asymptotic running time.<P>To implement a divide-and-conquer algorithmwe must break the given problem into several subproblemsthat are similar to the original one.In this instance we view each of the <IMG WIDTH=38 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68097" SRC="img1809.gif" > matricesas a <IMG WIDTH=33 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline68111" SRC="img1812.gif" > matrix,the elements of which are <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68113" SRC="img1813.gif" > submatrices.Thus, the original matrix multiplication, <IMG WIDTH=76 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68105" SRC="img1810.gif" > can be written as<P> <IMG WIDTH=408 HEIGHT=39 ALIGN=BOTTOM ALT="displaymath68093" SRC="img1814.gif" ><P>where each <IMG WIDTH=26 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68117" SRC="img1815.gif" >, <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68119" SRC="img1816.gif" >, and <IMG WIDTH=24 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68121" SRC="img1817.gif" >is an <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68113" SRC="img1813.gif" > matrix.<P>From Equation <A HREF="page457.html#eqnalgsmatmul"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> we get thatthe result submatrices can be computed as follows:<P> <IMG WIDTH=500 HEIGHT=88 ALIGN=BOTTOM ALT="eqnarray32989" SRC="img1818.gif" ><P>Here the symbols + and <IMG WIDTH=8 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline60753" SRC="img676.gif" > are taken to meanaddition and multiplication (respectively) of <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68113" SRC="img1813.gif" > matrices.<P>In order to compute the original <IMG WIDTH=38 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68097" SRC="img1809.gif" > matrix multiplicationwe must compute eight <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68113" SRC="img1813.gif" > matrix products(<em>divide</em>)followed by four <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68113" SRC="img1813.gif" > matrix sums(<em>conquer</em>).Since matrix addition is an <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > operation,the total running time for the multiplication operationis given by the recurrence:<P><A NAME="eqnalgsmatmul2"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation33025" SRC="img1819.gif" ><P>Note that Equation <A HREF="page457.html#eqnalgsmatmul2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is an instance of the generalrecurrence given in Equation <A HREF="page452.html#eqnalgsdandq"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In this case, <I>a</I>=8, <I>b</I>=2, and <I>k</I>=2.We can obtain the solution directly from Equation <A HREF="page456.html#eqnalgsdandqsoln"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Since <IMG WIDTH=43 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline68035" SRC="img1793.gif" >, the total running time is <IMG WIDTH=215 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline68147" SRC="img1820.gif" >.But this no better than the original, direct algorithm!<P>Fortunately,it turns out that one of the eight matrix multiplications is redundant.Consider the following series of seven <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68113" SRC="img1813.gif" > matrices:<P> <IMG WIDTH=500 HEIGHT=160 ALIGN=BOTTOM ALT="eqnarray33039" SRC="img1821.gif" ><P>Each equation above has only one multiplication.Ten additions and seven multiplications are requiredto compute <IMG WIDTH=21 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68151" SRC="img1822.gif" > through <IMG WIDTH=21 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68153" SRC="img1823.gif" >.Given <IMG WIDTH=21 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68151" SRC="img1822.gif" > through <IMG WIDTH=21 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68153" SRC="img1823.gif" >,we can compute the elements of the product matrix <I>C</I> as follows:<P> <IMG WIDTH=500 HEIGHT=88 ALIGN=BOTTOM ALT="eqnarray33065" SRC="img1824.gif" ><P>Altogether this approach requires seven <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68113" SRC="img1813.gif" >matrix multiplications and 18 <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68113" SRC="img1813.gif" > additions.Therefore, the worst-case running timeis given by the following recurrence:<P><A NAME="eqnalgsmatmul3"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation33079" SRC="img1825.gif" ><P><P>As above, Equation <A HREF="page457.html#eqnalgsmatmul3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is an instance of the generalrecurrence given in Equation <A HREF="page452.html#eqnalgsdandq"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.and we obtain the solution directly from Equation <A HREF="page456.html#eqnalgsdandqsoln"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In this case, <I>a</I>=7, <I>b</I>=2, and <I>k</I>=2.Therefore, <IMG WIDTH=43 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline68035" SRC="img1793.gif" > and the total running time is<P> <IMG WIDTH=328 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath68094" SRC="img1826.gif" ><P>Note <IMG WIDTH=122 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68173" SRC="img1827.gif" >.Consequently,the running time of the divide-and-conquer matrix multiplication strategyis <IMG WIDTH=50 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline68175" SRC="img1828.gif" > which is better (asymptotically)than the straightforward <IMG WIDTH=40 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58941" SRC="img329.gif" > approach.<P><HR><A NAME="tex2html6432" HREF="page458.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6430" HREF="page448.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6426" HREF="page456.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6434" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -