For each source row, use a temporary dense array to accumulate contributions from nonzero pairs. For every stored , traverse stored entries in row of the other sparse matrix.During accumulation,
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
}acc(j) is the sum of the already processed terms contributing to position . Missing entries multiply to zero, so ignoring them loses no contribution under the finite arithmetic convention of part (e). At completion,Descending j and prepending produce strictly increasing stored indices. Omitting zero also handles cancellation. The temporary array uses auxiliary space beyond the output. The time complexity isat worst , but potentially much smaller when the matrices are sparse. The term covers clearing and scanning the row accumulators. Finite-precision rounding can affect the numerical result, as in any Double matrix multiplication. Articles by others on the same topic
There are currently no matching articles.