cin and returns the
unique solution vector x
with Ax = b to cout.
If no such unique vector exists, a message is printed.
If you are not familiar with Gaussian elimination,
you can program the following
alternative functionality:
Your C++ program reads dimensions m and n
and a sparse coefficient matrix A and a sparse
vector b from cin and returns the
the sparse vector y
with y = Ab to cout.
Sparse vectors for both alternatives are sparse matrices
with n = 1.
The public interface and data structure for the sparse matrix is
given in sparsemat.h.
The header file contains already written members for I/O so
that you can test your program easily. A sample file containing
the input to the sparse matrix A is
sparsemat.dat.
Note that the template class needs a Field. We assume
the Field type has constructors from ints, copy constructors,
the operators +, -, *, /, =, ==
and that operator>> and
operator<< are appropriately overloaded
to provide I/O.
Please submit a file sparsemat.h
and several test programs.
modular.cpp contains the class z_p
which implements a mathematical field modulo a 15-bit prime residue.
Your main function should read in the prime first and place
it in a static data member of the class.
double.cpp uses plain double for
the mathematical field.
There is a problem with the pivot search in
sparsemat<double>::linsolve
as very small entries
could be used as pivot elements. This is addressed next.
fuzzy.cpp wraps the type double
so that == returns true if the arguments are
within a preset ``fuzz'' value, which is a small static
member of type double.
put_value.
You may wish to look, or try your solution first.
BONUS EXTENSION:
Instantiating the template sparsemat<>
for many mathematical fields may cause code bloat, because
each of the member functions gets compiled for each of the
mathematical fields. The task here is to compute with all of three
mathematical fields discussed above while
using a single class sparsemat<field_base>,
where field_base is an abstract base class
for the derived classes that implement the double, modular,
and fuzzy arithmetic. All member functions used in sparsemat
are virtual (cf.
C++Examples/Stacks/).
There is a problem with the constructors, as they cannot be virtual.
(In Java, clone(), which is the default copy method,
can be declared abstract, i.e., virtual).
Remember that operator[] returns a copy
of the mathematical field element in the matrix.
In addition, STL's make_pair template function
uses the copy constructor for initializing the pairs data members.
However, the copy constructor of field_base
cannot return a clone of the element, that is
a copy of the derived class object, because no constructors can be
declared virtual.
A solution to this problem is to use a separate class
abstract_field as the abstract class and
instantiate sparsemat<abstract_field> instead.
An instance of the abstract_field class contains
a pointer to the field_base object, which actually
must be derived class object. Now all constructors and the
destructor for abstract_field
can be written in terms of the virtual
member functions clone, etc. of field_base.
The header file
abstract_field.h
is a prototype for such a design. Note that the static
member default_elem_ptr gets initialized
by the function set_default_elem_ptr to
point to a derived object before each of the derived classes is used.
Note: you should not have to change anything in your sparsemat
template class. The class abstract_field can be
thought of as a ``wrapped'' pointer type.
Please submit a file abstract.cpp that
contains the missing member function definitions, the derived
class declarations and their member definitions and
a main program that exercises all derived classes.