Fork me on GitHub
Announcement: We are hiring a PhD student to do research on functional high performance computing, including work on Futhark itself. See here for more details.

Matrix multiplication

Futhark has no builtin operator or function for multiplying matrices. Indeed, it does not have matrices as a distinct type at all. Instead, matrices are represented simply as two-dimensional arrays of some type that supports multiplication and addition. We can write a function for multiplying integer matrices via the usual map/reduce constructs:

let matmul_i32 [n][m][p] (A: [n][m]i32) (B: [m][p]i32) : [n][p]i32 =
  map (\A_row ->
         map (\B_col ->
                reduce (+) 0 (map2 (*) A_row B_col))
             (transpose B))
      A

We can also write a polymorphic higher-order function that encapsulates the general pattern:

let matmul [n][m][p] 'a
           (add: a -> a -> a) (mul: a -> a -> a) (zero: a)
           (A: [n][m]a) (B: [m][p]a) : [n][p]a =
  map (\A_row ->
         map (\B_col ->
                reduce add zero (map2 mul A_row B_col))
             (transpose B))
      A

We can then partially apply matmul to obtain a matrix multiplication function for a specific type.

let matmul_f32 = matmul (+) (*) 0f32