[UPDATE] ffGEMM : finite field general matrix multiply

Not parallelization, not vectorization but a secret 3rd thing

Fileforma is an independent laboratory dedicated to researching custom binary formats for Artificial Intelligence. We research alternatives to FP32 and BF16 for AI. Our team consists of Yale-educated statisticians and ex-military physicists.

ffGEMM is a fixed-point arithmetic library for fast matrix multiplications on CPU. This article introduces the underlying mathematics for Fileforma’s ffGEMM library.

Introduction to Finite Fields

Finite fields, also known as Galois fields, are algebraic structures in which a finite set of elements is equipped with two operations: addition and multiplication. These operations satisfy the properties of a field, meaning every non-zero element has a multiplicative inverse, and both addition and multiplication are associative, commutative, and distributive over each other.

Introduction to Matrix Multiplication

To multiply two matrices, we use the rule that the element in the i-th row and j-th column of the resulting matrix is the dot product of the i-th row of the first matrix with the j-th column of the second matrix.

Here are two 3×3 matrices:

Matrix 1:

\(\begin{bmatrix} A & B & C \\ D & E & F \\ G & H & I \end{bmatrix}\)

Matrix 2:

\(\begin{bmatrix} J & K & L \\ M & N & O \\ P & Q & R \end{bmatrix}\)

The product of these matrices would look like:

\({Result} = \begin{bmatrix} (AJ + BM + CP) & (AK + BN + CQ) & (AL + BO + CR) \\ (DJ + EM + FP) & (DK + EN + FQ) & (DL + EO + FR) \\ (GJ + HM + IP) & (GK + HN + IQ) & (GL + HO + IR) \end{bmatrix}\)

Introduction to the Chinese Remainder Theorem

The Chinese Remainder Theorem states that a unique integer represents sets of mods across different finite fields.

Formal Definition of the Chinese Remainder Theorem

Define a set of positive pairwise relatively prime integers

\(m_1,m_2,…,m_N\)

where

\(gcd(m_i​,m_j​)=1\)

and

\( M = \prod_{i=1}^{N} m_i \)

Let us define a set of integers

\(( x_1, x_2, \dots, x_N ) , ( k)\)

Then, there exists exactly one integer X such that:

\(k \leq X \leq k + M \)

that satisfies the conditions

\(X \equiv x_i \pmod{m_i} \quad \text{for } 1 \leq i \leq N\)

Combining Finite Fields and Matrix Multiplication using the Chinese Remainder Theorem

From our introduction to matrix multiplications, we observe that matrix multiplications are linear combinations of columns. For the first column, we observe these elements contribute to the overall result.

\(\begin{bmatrix} AJ \\ DJ \\ GJ \end{bmatrix}, \begin{bmatrix} AK \\ DK \\ GK \end{bmatrix}, \begin{bmatrix} AL \\ DL \\ GL \end{bmatrix}\)

From our introduction to the Chinese Remainder Theorem, we observe that we can combine integers using the Chinese Remainder Theorem.

To combine the integers A, D, and G using the Chinese Remainder Theorem, we assume that they correspond to solutions of the following system of congruences:

\(X \equiv A \pmod{m_1}, \ \ X \equiv D \pmod{m_2}, \ \ X \equiv G \pmod{m_3} \)

where

\(gcd(m_i​,m_j​)=1\)

and

\(M = \prod_{i=1}^{N} m_i\)

Using the Chinese Remainder Theorem we can find a unique solution

\( X = (A \cdot m_1 \cdot y_1) + (D \cdot m_2 \cdot y_2) + (G \cdot m_3 \cdot y_3) \mod M\)

Therefore, we conclude

\(\begin{bmatrix} AJ \\ DJ \\ GJ \end{bmatrix}, \begin{bmatrix} AK \\ DK \\ GK \end{bmatrix}, \begin{bmatrix} AL \\ DL \\ GL \end{bmatrix} \equiv \begin{bmatrix} XJ \end{bmatrix}, \begin{bmatrix} XK \end{bmatrix}, \begin{bmatrix} XL \end{bmatrix}\)

Our ffGEMM library builds upon the equivalence shown above.

Citations

• Lidl, R., & Niederreiter, H. (1997). Finite Fields. Cambridge University Press.

• Dummit, D. S., & Foote, R. M. (2004). Abstract Algebra (3rd ed.). Wiley.

• Stinson, D. R. (2006). Cryptography: Theory and Practice (3rd ed.). CRC Press.

• Omondi, A & Premkumar, B. (2007). Residue Number Systems : Theory and Implementation. Imperial College Press.