|
|
|
|
Summary
• Programming Exercise - Matrices
• Design Recipe
• Problem Analysis
• Design Issues and Class Interface
Programming Exercise - Matrices
Mathematics is a good domain to develop different classes and programs. For example,
solutions for Complex numbers, Matrices and Quadratic Equations can be sought for
developing our own classes. In this lecture, we will take a problem to manipulate
and
perform different operations on Matrices. Matrices are used in lot of real world
problems.
We will perform problem analysis, design and implementation.
Let’s take a look at analysis and design phases first by using our design recipe.
Design Recipe
Firstly we do analysis and try to come up with a problem statement. Express its
essence,
abstractly and with examples. After describing the problems in few sentences, we
try to
formulate the problem with examples. It is emphasized to pay attention to the details.
We
do analysis of the data structures to be used in the program and choose the best
fit to the
program requirements. The code is written to implement the program. After
implementation is completed, we do its testing to verify that it is behaving properly
in all
scenarios. If any bugs are found, they are fixed. This cycle of testing and bug
fixing
continues until the program is working perfectly without any problem.
We are going to write a program to manage operations on Matrices.
Page 553
At the start of the problem analysis phase, let’s try to understand the problem
domain
first.
Problem Analysis
A matrix is nothing but a two-dimensional array of numbers. It is normally represented
in
rows and columns. A matrix is represented as:
It is a matrix A
with 3 rows and 4 columns. So order of the matrix is 3 * 4.
Before going further, let’s consider what are the operations normally performed
on
matrices.
- A matrix is added to another matrix.
- A scalar value (an ordinary number) is added to a matrix.
- A matrix is subtracted from another matrix.
- A scalar number is subtracted from a matrix.
- A matrix is multiplied with another matrix.
- A scalar number is multiplied with a matrix.
- A matrix is divided by a scalar.
- A matrix is transposed.
Now, we will define what these operations are and if there are any restrictions
on
matrices performing these operations.
The sum or addition of two matrices of the same order is found by adding the
corresponding elements of the two matrices. If
A and
B are two matrices of order
m * n to
be added then their resultant matrix will also have the same order m * n.
Aij + Bij
Where i varies from 1 to m (max number of rows) and j varies from 1 to n (max number
of cols).
Clearly, there is a restriction on the matrices performing this addition operation
that they
should have same numbers of rows and columns, in other words their order should
be the
same.
There is another operation of addition of scalar number to a matrix. In this operation,
a
number is added to all elements of the matrix.
Subtraction operation works in the same fashion that two matrices of the same order
takes
part in this operation and resultant matrix with similar order is obtained by subtracting
each element of one matrix from the corresponding element of other matrix. For example,
see the subtraction operation and assignment below:
Cij = Aij
- Bij
1 2 3 4
5 6 7 8
9 10 11 12
A =
-2 -4 -5
-2 2 0
0 0 10 = -
1 2 3
5 6 7
9 10 11
3 6 8
7 4 7
9 10 1
Page 554
Not to confuse your understanding with assignment in computer programs, the resultant
matrix is put on the left of assignment operator otherwise in Mathematics it is
located on
the right.
Each element of matrix B
is subtracted from the corresponding element of the matrix
A
and the resultant goes to matrix C.
C will have the same number
of rows and columns as
A and B.
Similar to the addition, there is another operation for subtracting a scalar from
a matrix.
In this case, a number is subtracted from each element of the matrix.
For Division of a matrix by a scalar, the scalar number divides each element of
the
matrix. Let x be
a scalar number and A
be a matrix then division is represented as:
Cij = Aij
/ x
Each element of matrix A
is divided by the number
x to produce the corresponding
number in the resultant matrix
C. For example,
A11
(element in first row and first column
of matrix A) is divided by the scalar number
x to provide
C11 (element in
first row and
first column of matrix C).
The multiplication operation is bit complicated as compared to the above discussed
operations. We will discuss simple case first, when a scalar is multiplied by a
matrix.
Suppose, this time we want to multiply the scalar
x with the matrix
A as:
Cij = x * Aij
Each element of matrix A
is multiplied with the scalar
x and the resultant number
is put in
the corresponding location inside the matrix C.
Now, we will see how a matrix is multiplied with another matrix. Firstly, there
is a
restriction on order of the matrices involved in this operation. The number of columns
of
the first matrix should be equal to the number of rows of the second matrix.
Two matrices are multiplied in the following manner:
We take the first row of first matrix and multiply it with the first column of the
second
matrix. The multiplication is done in such a way that the first element of the row
is
multiplied with the first element of the column, second element is multiplied with
the
second element and so on. The results of all these multiplication operations are
added to
produce one number. The resultant number is placed at the corresponding position
(i.e. 1st
row 1st col in this case) in the resultant matrix.
Further the same first row is multiplied with the second column of the second matrix
and
the resultant number is placed at intersecting position of first row and second
column in
the resultant matrix. This process goes on till the last column of the second matrix.
Page 555
Then comes the second row of first matrix and whole operation is repeated for this
row,
this row is multiplied with all the columns of the second matrix. This process goes
on till
the last row of the first matrix.
Note the resultant matrix is put on the left of the
=. In Mathematics, this
is put on right
but not to confuse your understanding with assignment concept in computer programs,
it
is put on left.
If a matrix with order m
rows, n
columns is multiplied with another matrix of
n rows and
p columns then the resultant matrix will have
m rows and
p columns. In the above
diagram, the first matrix has two rows and second matrix has two columns, therefore,
the
resultant matrix has two rows and two columns.
Now comes the last operation, we are thinking of implementing i.e. Transpose of
a
matrix. Transpose of a matrix is obtained by interchanging its rows and columns.
How do
we interchange rows and columns for transposing the matrix? We take the first row
of the
matrix and write it as a first column of the new matrix. The second row of the original
matrix is written as second column of the new matrix and similarly the last row
of the
original matrix is written as last column of the new matrix. At the end of this
operation,
when all rows of the original matrix are finished, we have new matrix as transpose
of the
original matrix. There is no change in the size (order or number of rows and cols
of a
matrix) of the transposed matrix when the original matrix is a square matrix. But
when
the original matrix is not a square matrix, there is a change in the order of the
transposed
matrix. The number of rows of the original matrix becomes the number of columns
of the
transposed matrix and the number of columns of the original matrix becomes the number
of rows of the transposed matrix.
Until now in this problem analysis phase, we have analyzed the problem in order
to
understand what are the matrices and what are their operations to be implemented.
Now
at the next stage, we try to determine the followings:
- What are the constants to be used in our class?
- What are going to be the data structures to cater to the different sized
matrices?
- How much memory is required and how it will be allocated?
(1)(2)+(2)(1) (1)(4)+(2)(2)
(5)(2)+(6)(1) (5)(4)+(6)(2)
1 2 *
5 6
2 4
1 2
1 2 3
5 6 7
9 1 0 11
1 5 9
2 6 10
3 7 11
Page 556
- What is going to be the interface of the class?
Design Issues and Class Interface
We want to specify the size of the matrix at creation time and allocate the memory
for
that. So we don’t see any use of constants inside our class named
Matrix.
The size of the memory to be allocated is not going to be huge, as we are not catering
to
the very huge sized matrices. Therefore, the memory for a matrix is going to be
allocated
dynamically bluntly after the size of the matrix is specified in terms of rows and
columns
without worrying about the size of the matrix.
For the interface of our Matrix
class, we will declare a constructor that will accept integer
number of rows and columns of the matrix to be created as parameters.
Matrix ( int rows, int cols ) ;
The constructor function will be doing the memory allocation for the matrix.
As part of the interface, we will declare a display function inside our
Matrix class that
will display the elements on the screen.
void display ( Matrix & );
To perform already discussed different operations on matrices, we need to overload
operators. For example to perform addition of two matrices,
+ operator will be
overloaded as a member function of the
Matrix class. The
+ operator function
will be
called for the Matrix
object on the left of the
+ and the
Matrix object on the right
to it
will be passed as a parameter to it. This function will add the corresponding elements
of
the both matrices and returns the resultant back.
Matrix operator + ( Matrix & ) const;
The same thing applies to the subtraction operation of two matrices.
– operator function
will be overloaded for that as a member function of the Matrix class.
Matrix operator - ( Matrix & ) const;
The situation changes a bit, when we want to write the functions to cater to different
operations where both the operands are not matrix objects rather one of them is
scalar.
For example, when we want to do the following operation:
A + x ;
Where A is a matrix and x is a scalar.
Then we write a member function that accepts a scalar number as a parameter instead
of a
Matrix object.
Page 557
Matrix operator + ( Scalar ) const;
The Scalar can be an int,
double or
float, that we will cover
later.
But the situation is more different, when we want to perform the scalar addition
operation
in the following manner:
x + A ;
By now we should be clear that member function cannot be written to handle this
operation because there is a scalar number on the left of
+. Therefore, we need to
write a
friend operator function for this type of operation. The friend functions
are non-members
and therefore, defined outside of the class.
friend Matrix operator + ( Scalar , Matrix & ) ;
Similarly, when a scalar is subtracted from a
Matrix object like the
following:
A - x ;
A member function is written to cater to this operation.
Matrix operator - ( Scalar ) const;
But again, when a matrix is subtracted from a scalar number:
x - A ;
Then we have to write a friend
operator to handle this operation.
friend Matrix operator - ( Scalar , Matrix & ) ;
In order handle the multiplication operations of two Matrix objects like the following:
A * B ;
A member operator *
function is defined.
Matrix operator * ( const Matrix & ) ;
This operator is called for the
Matrix object on the left
of * and the object
on the right is
passed as an argument. The function multiplies both the matrices and returns the
resultant
matrix.
When a scalar is multiplied with a scalar like:
A * x ;
Page 558
The following member operator * handles this:
Matrix operator * ( Scalar ) const;
But for operation like the following:
x * A;
following friend operator
function is written:
friend Matrix operator * ( const Scalar , const Matrix & ) ;
For division operation like the following:
A / x;
A member operator / is overloaded as:
Matrix operator / ( const Scalar );
Now we will talk about transpose of a matrix. For this operation, we will write
a member
function transpose
that will transpose the original matrix.
Matrix & transpose(void) ;
Now we are left with few more things to cover to complete the rudimentary interface
of
our class Matrix.
Operators += and
-= are overloaded
as member operators. These composite operators
use the assignment operator (
= ).
We will also overload stream insertion and extraction operators as
friend functions to our
Matrix class as follows:
friend ostream & operator << ( ostream & , Matrix & ) ;
friend istream & operator >> ( istream & , Matrix & ) ;
So here is how we declare our
Matrix class. The interface of the class is the
public
methods of the class. Here is one important point to understand that what we are
concerned about here is the class interface and not about the program interface
to the user
of the program. A programmer can develop user interface by writing his/her code
while
using the class interface.
/* Declaration of the Matrix class. This class is containing the double type elements
*/
Page 559
class Matrix
{
private:
int numRows, numCols;
double **elements;
public:
Matrix(int=0, int=0); // default constructor
Matrix(const Matrix & ); // copy constructor
~Matrix(); // Destructor
int getRows(void) const; // Utility fn, returns no. of rows
int getCols(void) const; // Utility fn, returns no. of columns
const Matrix & input(istream &is = cin); // Read matrix from istream
const Matrix & input(ifstream &is); // Read matrix from istream
void output(ofstream &os) const; // Utility fn, prints matrix with graphics
void output(ostream &os = cout) const; // Utility fn, prints matrix with graphics
const Matrix& transpose(void); // Transpose the matrix and return a ref
const Matrix & operator = (const Matrix &m); // Assignment operator
Matrix operator+( Matrix &m) const; // Member op + for A+B; returns matrix
Matrix operator + (double d) const;
const Matrix & operator += (Matrix &m);
friend Matrix operator + (double d, Matrix &m);
Matrix operator-( Matrix & m) const; // Member op + for A+B; returns matrix
Matrix operator - (double d) const;
const Matrix & operator -= (Matrix &m);
friend Matrix operator - (double d, Matrix& m);
Matrix operator*(const Matrix & m);
Matrix operator * (double d) const;
friend Matrix operator * (const double d, const Matrix& m);
Matrix operator/(const double d);
friend ostream & operator << ( ostream & , Matrix & );
friend istream & operator >> ( istream & , Matrix & );
friend ofstream & operator << ( ofstream & , Matrix & );
friend ifstream & operator >> ( ifstream & , Matrix & );
void display( ) ;
};
In the above declarations, we should note how we are passing and returning
Matrix
objects. We are passing and returning the Matrix objects by reference because passing
the
Page 560
Matrix objects by value will be a overhead that will affect performance and more
memory will be allocated and de-allocated on stack.
Notice that we are doing dynamic memory allocation inside the
constructor of the class.
You must be remembering that wherever the dynamic memory allocation is made, it
has
to be freed explicitly. To de-allocate the memory, we will write code inside the
destructor
of the class Matrix.
The other consideration when we are allocating memory on free store
from within constructor is that the default
assignment operator will
not work here.
Remember, the default assignment
operator makes shallow
copy of the object members,
therefore, we will have to write our own
assignment operator ( =
) in order to make deep
copy of the object data members. Remember that a
copy constructor is called
when a new
Matrix object is initialized and constructed based on an already existent
Matrix object.
Therefore, we have to write our own
copy constructor in order
to make deep copy of the
object data members.
There is one very important point to mention about this class
Matrix. A
Matrix can be
composed of ints,
floats or
doubles as their elements.
Instead of handling these data types
separately, we can write Matrix
class as a template class and write code once for all
native data types. While writing this template class, the better approach to write
will be,
to go with a simple data type (e.g.
double) first to write
a Matrix class and
then extend it
to a template class later. Another thing that can be templatized in the
Matrix class is the
Scalar number. Actually, this Scalar number can be an
int,
float or
double; therefore, we
may also use a template for this.
We have to perform certain checks and make decisions inside the implementation of
member functions. For example, while writing the division operator member function,
we
will check against the number that it should be non-zero. Before adding two matrices,
we
will check for their number of rows and columns to be equal. Also in this exercise,
we
have declared only one class
Matrix to manipulate matrices. There are alternate
approaches to this. For example, we could declare a
Row class first and then
contain
multiple objects (same in number as number of rows required for the matrix object)
of
Row class inside the
Matrix class making a matrix
of a certain size. To make it simple,
we have selected to manage matrices using only one class
Matrix. The objective here
is to
practice the already studied programming constructs as much as possible.
|
|
|
|
|