page104.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 141 行
HTML
141 行
<HTML>
<HEAD>
<TITLE>Canonical Matrix Multiplication</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html3190" HREF="page105.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page105.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html3188" HREF="page100.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page100.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html3184" HREF="page103.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page103.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html3192" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html3193" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION005340000000000000000">Canonical Matrix Multiplication</A></H2>
<A NAME="secfdsmatmul"> </A>
<P>
Given an <IMG WIDTH=43 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline61185" SRC="img661.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img661.gif" > matrix <I>A</I>
and an <IMG WIDTH=37 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline61189" SRC="img662.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img662.gif" > matrix <I>B</I>,
the product <I>C</I>=<I>AB</I> is an <IMG WIDTH=42 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline61195" SRC="img663.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img663.gif" > matrix.
The elements of the result matrix are given by
<P><A NAME="eqnmatmul"> </A> <IMG WIDTH=500 HEIGHT=46 ALIGN=BOTTOM ALT="equation4125" SRC="img664.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img664.gif" ><P>
Accordingly, in order to compute the produce matrix, C,
we need to compute <I>mp</I> summations
each of which is the sum of <I>n</I> product terms.
<P>
To represent matrices we use <tt>Matrix<T></tt> class
shown in Program <A HREF="page104.html#progmatrixh" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page104.html#progmatrixh"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
This class simply extends the <tt>Array2D<T></tt> class
by adding declarations for the various operations on matrices.
<P>
<P><A NAME="4297"> </A><A NAME="progmatrixh"> </A> <IMG WIDTH=575 HEIGHT=161 ALIGN=BOTTOM ALT="program4136" SRC="img665.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img665.gif" ><BR>
<STRONG>Program:</STRONG> <tt>Matrix<T></tt> Class Definition<BR>
<P>
<P>
An algorithm to compute the matrix product
is given in Program <A HREF="page104.html#progmatrix1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page104.html#progmatrix1c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
The algorithm given is a direct implementation of Equation <A HREF="page104.html#eqnmatmul" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page104.html#eqnmatmul"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
<P><A NAME="4303"> </A><A NAME="progmatrix1c"> </A> <IMG WIDTH=575 HEIGHT=351 ALIGN=BOTTOM ALT="program4153" SRC="img666.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img666.gif" ><BR>
<STRONG>Program:</STRONG> <tt>Matrix<T></tt> Class Multiplication Operator Definition<BR>
<P>
<P>
The matrix multiplication routine in Program <A HREF="page104.html#progmatrix1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page104.html#progmatrix1c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
overloads the multiplication operator, <tt>operator*</tt>,
as a member function of the <tt>Matrix<T></tt> class.
As a result it takes a single argument, <tt>arg</tt>,
which is a <tt>const</tt> reference to a matrix.
The routine computes a result matrix which is the produce
of <tt>*this</tt> and <tt>arg</tt>.
<P>
In C++ there are two ways to overload <tt>operator*</tt>.
The first is to define a non-member function
<PRE>Matrix<T> operator * (Matrix<T> const&, Matrix<T> const&);</PRE>
which takes two arguments,
both of them <tt>const</tt> references to <tt>Matrix<T></tt> objects,
and produces a result of type <tt>Matrix<T></tt>.
The second way is to declare a <tt>const</tt> member function
of class <tt>Matrix<T></tt> called
<PRE>Matrix<T> Matrix<T>::operator * (Matrix<T> const&) const;</PRE>
which takes as its single argument a <tt>const</tt> reference to a
<tt>Matrix<T></tt> class object.
<P>
There are pros and cons associated with each approach.
The former approach requires the function to be declared
a <tt>friend</tt><A NAME=4177> </A> of the <tt>Matrix<T></tt> class
and any of the classes from which it may be derived
if access to the <tt>protected</tt><A NAME=4180> </A> members of those classes
is needed in the implementation.
On the other hand, in this approach,
the operands are treated symmetrically with respect to
implicit type <em>coercion</em><A NAME=4182> </A>.
<P>
The latter approach has been chosen
for the implementation of the matrix multiplication operator
since <tt>Matrix<T></tt> is a derived class and the implementation of
the operator requires access to <tt>protected</tt> members of the base class.
<P>
To determine the running time of Program <A HREF="page104.html#progmatrix1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page104.html#progmatrix1c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,
we need to make some assumptions about the running times for
assignment, addition, and multiplication of objects of type <tt>T</tt>.
For simplicity, we shall assume that these are all constant.
We will also assume that the dimensions of the matrices to be multiplied
are <IMG WIDTH=43 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline61185" SRC="img661.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img661.gif" > and <IMG WIDTH=37 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline61189" SRC="img662.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img662.gif" >.
<P>
The algorithm begins by checking to see that the matrices
to be multiplied have compatible dimensions.
I.e., the number of columns of the first matrix must be equal to
the number of rows of the second one.
This check takes <I>O</I>(1) time in the worst case.
<P>
Next a matrix in which the result will be formed is constructed (line 6).
The running time for this is <IMG WIDTH=134 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61207" SRC="img667.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img667.gif" >.
If <tt>T</tt> is one of the built-in types whose constructor does nothing,
this running time reduces to <I>O</I>(1).
<P>
For each value of <I>i</I> and <I>j</I>,
the innermost loop (lines 12-13) does <I>n</I> iterations.
Each iteration takes a constant amount of time,
assuming assignment, addition, and multiplication of type <tt>T</tt> objects
each take a constant amount of time.
<P>
The body of the middle loop (lines 9-15)
takes time <I>O</I>(<I>n</I>) for each value of <I>i</I> and <I>j</I>.
The middle loop is done for <I>p</I> iterations,
giving the running time of <I>O</I>(<I>np</I>) for each value of <I>i</I>.
Since, the outer loop does <I>m</I> iterations,
its overall running time is <I>O</I>(<I>mnp</I>).
<P>
Finally, the result matrix is returned on line 17.
The return involves a call to the
copy constructor for <tt>Matrix<T></tt> class objects.
In fact, no such constructor has been declared for <tt>Matrix<T></tt>
class objects.
The default behavior of C++ in this case is to create a
<em>default copy constructor</em><A NAME=4192> </A>
for <tt>Matrix<T></tt> class objects.
In C++ the behavior of the default copy constructor
for objects of class <tt>X</tt> is to call
the copy constructor for the each of the base classes
from which the class <tt>X</tt> may be derived
and then to copy the data members of <tt>X</tt>
one-by-one using their respective copy constructors.
Since the <tt>Matrix<T></tt> class is derived from the <tt>Array2D<T></tt>
class and since the <tt>Matrix<T></tt> class has no data members,
the running time of this default copy constructor is equal to the
running time of the copy constructor for <tt>Array2D<T></tt> class objects
(see Section <A HREF="page83.html#secfdsarraycc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page83.html#secfdsarraycc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).
Hence the running time of line 18 is <IMG WIDTH=146 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61233" SRC="img668.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img668.gif" >.
Assuming that <IMG WIDTH=101 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61235" SRC="img669.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img669.gif" >, we get <I>O</I>(<I>mp</I>).
<P>
In summary, we have shown that lines 4-5 are <I>O</I>(1);
line 6 is <I>O</I>(<I>mp</I>);
lines 7-16 are <I>O</I>(<I>mnp</I>); and
line 17 is <I>O</I>(<I>mp</I>).
Therefore, the running time of the canonical matrix multiplication
algorithm is <I>O</I>(<I>mnp</I>).
<P>
<HR><A NAME="tex2html3190" HREF="page105.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page105.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html3188" HREF="page100.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page100.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html3184" HREF="page103.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page103.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html3192" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html3193" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?