 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/imperative-programming/4/g/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 4 / g / Solution by

Codex  0 2026-10-31

For each source row, use a temporary dense array to accumulate contributions from nonzero pairs. For every stored

A_{ik}

, traverse stored entries in row

k

of the other sparse matrix.

def mult(that: SparseMatrix): SparseMatrix = {
  require(N == that.N)
  val out = new SparseMatrix(N)
  for (i <- 0 until N) {
    val acc = Array.fill[Double](N)(0.0)
    for ((k, x) <- rows(i)) {
      for ((j, y) <- that.rows(k)) {
        acc(j) += x * y
      }
    }
    var j = N - 1
    var result: Row = Nil
    while (j >= 0) {
      if (acc(j) != 0.0) result = (j, acc(j)) :: result
      j -= 1
    }
    out.rows(i) = result
  }
  out
}

During accumulation, acc(j) is the sum of the already processed terms contributing to position

(i, j)

. Missing entries multiply to zero, so ignoring them loses no contribution under the finite arithmetic convention of part (e). At completion,

out_{ij} = k = 0 \sum N - 1 A_{ik} that_{kj} .

(1)

Descending j and prepending produce strictly increasing stored indices. Omitting zero also handles cancellation. The temporary array uses

O (N)

auxiliary space beyond the output. The time complexity is

O (N^{2} + \sum_{i} \sum_{(k, x) \in rows (i)} ∣ that.rows (k) ∣),

(2)

at worst

O (N^{3})

, but potentially much smaller when the matrices are sparse. The

N^{2}

term covers clearing and scanning the row accumulators. Finite-precision rounding can affect the numerical result, as in any Double matrix multiplication.

 Read the full article

 New to topics? Read the docs here!