In such situations, one should use a sparse implementation. Namely, each affine form is stored as a list of pairs (j,x_j), containing only the terms with non-zero coefficient x_j. For efficiency, the terms should be sorted in order of j. This representation makes the AA operations somewhat more complicated; however, the cost of each operation becomes proportional to the number of nonzero terms appearing in the operands, instead of the number of total symbols used so far.
