1 Description and Objectives
In the next couple of lab session, you will write code to manipulate, convert,
transform, and
factorize matrices . In this lab, our focus will be on the creation and
conversion between
various matrix formats, and also on how one can perform basic ope rations on
matrices that
are stored in the different formats .
In class, we learned of three matrix formats: Dense, (compressed) sparse column,
and
(compressed) sparse row. Your mission, should you choose to accept it, will be
to write code
that can convert between each of these types of matrices and also multiply two
matrices that
are of the same type.
Lab Objectives
1. Understand dense matrix representation
2. Understand sparse matrix representation
3. Implement (efficient) conversion routines for converting between matrices of
different
formats
2 Dense Matrix Operations
Look at the DenseMatrix.java (template) class that you have been provided. In
this class,
the matrix is internally re presented as a two -dimenional array.
/// Holds the matrix
private double A_[][];
/// Holds the number of rows
private int m_;
/// Number of columns
private int n_;
The DenseMatrix class contains a number of methods that you must implement.
Problem 2
2.1 Problem
I would like for you to be able to implement methods that perform the operations
for addition ,
scalar multiplication, and matrix multiplication:
C = A + B
C = αA
C = AB
These methods have prototypes:
// Add two dense matrices
// Throw exception if dimensions are not conformal
public DenseMatrix plus(DenseMatrix B)
throws java.lang.IllegalArgumentException
// multiply a dense matrix by a scalar
public DenseMatrix times(double s)
// Multiply two dense matrices.
// Throw exception if dimensions are not conformal
public DenseMatrix times(DenseMatrix B)
throws java.lang.IllegalArgumentException
Try your methods on the sample matrices provided on the course web site: A1.txt,
B1.txt,
A2.txt, B2.txt. The Lab11.java code provided should put it through a workout for
you.
3 Sparse Matrix Representation
Look at the SparseColumnMatrix format class that you have been provided. As we
mentioned
in class, the (Compressed) Sparse Column format stores the matrix in three
arrays:
private int matbeg_[];
private int matind_[];
private double matval_[];
/// Number of columns
private int n_;
/// Number of rows
private int m_;
/// Number of non- zeroes
private int nz_;
We will do a little bit of coding so that I know that you understand the
differences between
the formats.
Problem 3
3.1 Problem
First you will need to write a constructor
public SparseColumnMatrix(DenseMatrix A)
that takes a DenseMatrix as input. I have given you a skeleton code for this
3.2 Problem
While you’re at it, just for fun, implement a constructor for the DenseMatrix
class so that it
can create itself from a SparseColumnMatrix.
3.3 Problem
Implement the methods
public SparseColumnMatrix plus(SparseColumnMatrix B)
and
public SparseColumnMatrix times(double beta)
that return A + B and βA (in sparse format) respectively.
4 Extra Credit
4.1 Problem
Implement a SparseRowMatrix class that has the same functionality as the
SparseColumnMatrix
class
4.2 Problem
Write a method that can (efficiently) convert between SparseColumnMatrix and
SparseRowMatrix
formats
4.3 Problem
Use the SparseRowMatrix to support the method:
public SparseColumnMatrix times(SparseColumnMatrix B)
in the SparseColumnMatrix class
5 Lab Deliverables
• Four files: Lab11.java, DenseMatrix.java, SparseColumnMatrix.java, and (if
you do the extra credit) SparseRowMatrix.java that contain code implementing the
matrix operations requested. You should not have to change the code in
Lab11.java,
though you may find it useful to comment parts out while you do the code
development.
Problem 6
6 Problem Set
6.1 Problem
CLRS 28.1-5
6.2 Problem
CLRS 28.3-2
6.3 Problem
CLRS 28.3-3
