Matrix Multiply Divide and Conquer Assignment

Background

Matrix multiply can be performed recursively. We will implement two approaches, one with immutable support classes. Another with mutable data. Each presents its own challenges.

${\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}\\\mathbf {A} _{21}&\mathbf {A} _{22}\\\end{pmatrix}}{\begin{pmatrix}\mathbf {B} _{11}&\mathbf {B} _{12}\\\mathbf {B} _{21}&\mathbf {B} _{22}\\\end{pmatrix}}={\begin{pmatrix}\mathbf {A} _{11}\mathbf {B} _{11}+\mathbf {A} _{12}\mathbf {B} _{21}&\mathbf {A} _{11}\mathbf {B} _{12}+\mathbf {A} _{12}\mathbf {B} _{22}\\\mathbf {A} _{21}\mathbf {B} _{11}+\mathbf {A} _{22}\mathbf {B} _{21}&\mathbf {A} _{21}\mathbf {B} _{12}+\mathbf {A} _{22}\mathbf {B} _{22}\\\end{pmatrix}}$

source: Wikipedia Parallel Matrix Multiplication

Code To Implement

Immutable Parallel To The Max Version

TreeImMatrix

class:	TreeImMatrix.java
methods:	add multiply
package:	matrixmultiply.dnc
source folder:	student/src/main/java

add and multiply double dispatch
@Override public ImMatrix add(ImMatrix b) throws ExecutionException, InterruptedException { return b.doubleDispatchAdd(this); } @Override public ImMatrix multiply(ImMatrix b) throws ExecutionException, InterruptedException { return b.doubleDispatchPreMultiply(this); }

doubleDispatchAdd(a)

method: public ImMatrix doubleDispatchAdd(TreeImMatrix a) (parallel implementation required)

doubleDispatchPreMultiply(a)

method: public ImMatrix doubleDispatchPreMultiply(TreeImMatrix a) (parallel implementation required)

Mutable Performance Conscious Version

OffsetSubMatrix

class:	OffsetSubMatrix.java
methods:	sequentialMultiply parallelMultiply
package:	matrixmultiply.challenge
source folder:	student/src/main/java

sequentialMultiply(a, b)

method: void sequentialMultiply(OffsetSubMatrix a, OffsetSubMatrix b) (sequential implementation only)

In class OffsetSubMatrix, method sequentialMultiply you will find your base case and the sub matrices prepared for you.

Warning:the base case uses +=

sequentialMultiply

void sequentialMultiply(OffsetSubMatrix a, OffsetSubMatrix b) { if (size == 1) { values[row][col] += (a.values[a.row][a.col] * b.values[b.row][b.col]); } else { OffsetSubMatrix result11 = sub11(); OffsetSubMatrix result12 = sub12(); OffsetSubMatrix result21 = sub21(); OffsetSubMatrix result22 = sub22(); OffsetSubMatrix a11 = a.sub11(); OffsetSubMatrix a12 = a.sub12(); OffsetSubMatrix a21 = a.sub21(); OffsetSubMatrix a22 = a.sub22(); OffsetSubMatrix b11 = b.sub11(); OffsetSubMatrix b12 = b.sub12(); OffsetSubMatrix b21 = b.sub21(); OffsetSubMatrix b22 = b.sub22(); // https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm#Divide_and_conquer_algorithm throw new NotYetImplementedException(); } }

You simply need to make the appropriate recursive calls to compute the result on the right:

parallelMultiply(a, b, isParallelPredicate)

method: void parallelMultiply(OffsetSubMatrix a, OffsetSubMatrix b, IntPredicate isParallelPredicate) (parallel implementation required)

Again, given the following:

${\begin{pmatrix}\mathbf {A} _{11}\mathbf {B} _{11}+\mathbf {A} _{12}\mathbf {B} _{21}&\mathbf {A} _{11}\mathbf {B} _{12}+\mathbf {A} _{12}\mathbf {B} _{22}\\\mathbf {A} _{21}\mathbf {B} _{11}+\mathbf {A} _{22}\mathbf {B} _{21}&\mathbf {A} _{21}\mathbf {B} _{12}+\mathbf {A} _{22}\mathbf {B} _{22}\\\end{pmatrix}}$

source: Wikipedia Parallel Matrix Multiplication

What computation can be done in parallel? What computation must be performed sequentially?

Warning: The resulting data (this.values) is mutated and shared.

void parallelMultiply(OffsetSubMatrix a, OffsetSubMatrix b, IntPredicate isParallelPredicate)
			throws InterruptedException, ExecutionException {
		if (size > 1 && isParallelPredicate.test(size)) {
			OffsetSubMatrix result11 = sub11();
			OffsetSubMatrix result12 = sub12();
			OffsetSubMatrix result21 = sub21();
			OffsetSubMatrix result22 = sub22();

			OffsetSubMatrix a11 = a.sub11();
			OffsetSubMatrix a12 = a.sub12();
			OffsetSubMatrix a21 = a.sub21();
			OffsetSubMatrix a22 = a.sub22();

			OffsetSubMatrix b11 = b.sub11();
			OffsetSubMatrix b12 = b.sub12();
			OffsetSubMatrix b21 = b.sub21();
			OffsetSubMatrix b22 = b.sub22();

			throw new NotYetImplementedException();

		} else {
			sequentialMultiply(a, b);
		}
	}

Testing

Immutable Parallel To The Max Version

class:	_ParallelDncMatrixMultiplyTestSuite.java
package:	matrixmultiply.dnc
source folder:	testing/src/test/java

Mutable Performance Conscious Version

class:	DivideAndConquerMatrixMultiplyTestSuite.java
package:	matrixmultiply.challenge
source folder:	testing/src/test/java

Pledge, Acknowledgments, Citations

file:

matrix-multiply-divide-and-conquer-pledge-acknowledgments-citations.txt

More info about the Honor Pledge