= Solution
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,
$$
\boxed{\mathrm{out}_{ij}=\sum_{k=0}^{N-1}A_{ik}\,\mathrm{that}_{kj}.}
$$
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\left(N^2+\sum_i\sum_{(k,x)\in\mathrm{rows}(i)}|\mathrm{that.rows}(k)|\right),
$$
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>.
Back to article page
