Matrix Multiply

Triple nested loop, O(n³). For each element C[i,j], compute the dot product of row i of A and column j of B. Using the transpose of A for a cache-friendly access pattern, but no tiling.

Cilia

func multiply(Matrix A, B) -> Matrix {
    const m = A.rows()
    const n = A.columns()
    const o = B.rows()
    const p = B.columns()

    assert(n == o, "A.columns() must equal B.rows()")

    Matrix C(m, p, 0.0)
    const AT = transpose(A)

    for j in 0..<p {
        for i in 0..<m {
            for k in 0..<n {
                C[i,j] += AT[k,i] * B[k,j]
            }
        }
    }

    return C
}

C++

auto multiply(const matrix& A, const matrix& B) -> matrix {
    const int m = A.rows();
    const int n = A.columns();
    const int o = B.rows();
    const int p = B.columns();

    assert(n == o && "A.columns() must equal B.rows()");

    matrix C(m, p, 0.0);
    const matrix AT = transpose(A);

    for (int j = 0; j < p; ++j) {
        for (int i = 0; i < m; ++i) {
            for (int k = 0; k < n; ++k) {
                C[i,j] += AT[k,i] * B[k,j];
            }
        }
    }

    return C;
}