Suppose (prior to one-hot-encoding) you have predictors/fields from a set $Z$ (say movie genre, user gender, and user race). Suppose further, each predictor $z \in Z$ can take on one of $k_z$ values. After one-hot encoding, you will have a new set of binary features $X$ of size $K := \sum_{z \in Z}k_z$.
In a model with all interactions, you must estimate a matrix of interaction coefficients $Q$, which has $K\times (K+1) / 2$ unique terms.
The factorization machine puts structure on the matrix $Q$, and assumes that $Q \equiv W^{T} W$, where $W$ is of dimension $l \times K$, with $1\le l \le K$ some number specified by the user. We estimate $W$ instead of $Q$.
The field-aware factorization machine puts structure on $Q$ as well. It partitions $Q$ into blocks based on $z$ (the original features). If $q_{z_i, z_j}$ denotes the $z_i,z_j$ block of $Q$, we assume that $q_{z_i,z_j}$ comes from the $z_i,z_j$ block of $W_j^{T} W_i$, where $W_i$ is of dimension $l \times K$. As with the FM, we estimate the $W_i$ instead of $Q$.
The FM factorization of $Q$ has $K \times l $ parameters. The "feild-aware" FM has $K\times l\times |Z|$ parameters. A model with all interactions has $K \times (K+1)/2$ parameters.