Here is some code to generate the equations in text form so no one has to type out the characters from the JPGs in the paper. The indices are slightly different than in the paper (might have missed a transpose somewhere), but the result comes out correct, so it is probably fine. Note that it prints over 7 MB of data. It might be a good idea to pipe the output to a file first before looking at it: python3 print_equations.py > equations.txt
The individual equations could be simplified a bit more (e.q. by using SymPy) but I wanted to keep the dependencies to a minimum.
Make sure to run the code in the same directory as the files factorizations_f2.npz and factorizations_r.npz.
print_equations.py
import numpy as np
from ast import literal_eval as make_tuple
np.random.seed(0)
"""
The *.npz files contain a dict with keys like "(2,3,4)" and values containing
a list of matrices U, V and W. For example, for the 2-by-2 times 2-by-2 case,
we have the following matrices:
U =
[[ 0 1 1 0 1 1 0]
[ 0 0 -1 1 0 0 0]
[ 1 1 1 0 1 0 0]
[-1 -1 -1 0 0 0 1]]
V =
[[0 0 0 0 1 1 0]
[1 1 0 0 1 0 1]
[0 1 1 1 1 0 0]
[0 1 1 0 1 0 1]]
W =
[[ 0 0 0 1 0 1 0]
[ 0 -1 0 0 1 -1 -1]
[-1 1 -1 -1 0 0 0]
[ 1 0 0 0 0 0 1]]
Each column of U is multiplied with the vectorized matrix A.
Likewise, Each column of V is multiplied with the vectorized matrix B.
The resulting vectors are multiplied pointwise and their product is
multiplied with W, which forms the entries of the product matrix C = A times B.
Also see the function `multiply` below.
"""
# There are two factorizations, one for useful numbers and one for mod 2 math.
for filename, mod in [
("factorizations_r.npz", None),
("factorizations_f2.npz", 2),
]:
# Load the factorizations. Note that allow_pickle=True allows arbitrary
# code execution. A JSON file would have been a better format choice
# since nothing here is stored in NumPy format anyway.
factorizations = dict(np.load(filename, allow_pickle=True))
# Test each factorization
for key, UVW in factorizations.items():
U, V, W = map(np.array, UVW)
m, k, n = make_tuple(key)
print(f"\nMultiply {m}-by-{k} matrix A with {k}-by-{n} matrix B")
if mod is not None:
print(f"using mod {mod} arithmetic")
print()
# Check that shapes are correct
assert m * k == U.shape[0]
assert k * n == V.shape[0]
assert m * n == W.shape[0]
assert U.shape[1] == V.shape[1]
assert U.shape[1] == W.shape[1]
# Generate two random matrices for testing
A = np.random.randint(10, size=(m, k))
B = np.random.randint(10, size=(k, n))
def multiply(A, B, U, V, W):
# Multiply two matrices A and B using index matrices U, V and W
a = A.ravel()
b = B.ravel()
tmp = (U.T @ a) * (V.T @ b)
c = W @ tmp
C = c.reshape(n, m).T
return C
# Multiply matrices
C = multiply(A, B, U, V, W)
# Check that result is correct, taking potential mod 2 into account
if mod is None:
assert np.allclose(C, A @ B)
else:
assert np.allclose(C % mod, (A @ B) % mod)
def make_code(variables, factors):
# Generate code like "(a11 + a21 - a22)"
parts = []
for variable, factor in zip(variables, factors):
# Simplify +1 and -1 factors
if factor == 1:
factor = " + "
elif factor == -1:
factor = " - "
elif factor < 0:
factor = f" {factor} * "
elif factor > 0:
factor = f" + {factor} * "
else:
continue
parts.append(factor + variable)
code = "".join(parts).lstrip(" +")
if len(parts) > 1:
code = "(" + code + ")"
return code
def make_variables(var, m, n):
# Generate variables like a11, a12, a21, a22
# or maybe a_1_1, a_1_2, a_2_1, a_2_2.
# For larger matrices, we need a separator to avoid
# confusing e.g. a_1_11 with a_11_1.
separator = "_" if max(m, n, k) > 9 else ""
return [f"{var}{separator}{i + 1}{separator}{j + 1}"
for i in range(m) for j in range(n)]
A_variables = make_variables("a", m, k)
B_variables = make_variables("b", k, n)
C_variables = make_variables("c", m, n)
h_variables = [f"h{i + 1}" for i in range(U.shape[1])]
lines = [
", ".join(A_variables) + " = A.ravel()",
", ".join(B_variables) + " = B.ravel()",
]
# Generate code for computation of temporary vector
for h, u, v in zip(h_variables, U.T, V.T):
sa = make_code(A_variables, u)
sb = make_code(B_variables, v)
lines.append(f"{h} = {sa} * {sb}")
# Generate code for computation
for c, w in zip(C_variables, W):
lines.append(f"{c} = " + make_code(h_variables, w).strip("()"))
lines.append("C = np.array([" + ", ".join(C_variables) +
f"]).reshape({n}, {m}).T")
code = "\n".join(lines)
print(code)
# Verify that code generates the correct result
exec(code)
if mod is None:
assert np.allclose(C, A @ B)
else:
assert np.allclose(C % mod, (A @ B) % mod)
For example, the generated code for general 2-by-2 times 2-by-2 matrix multiplication is
Here is some code to generate the equations in text form so no one has to type out the characters from the JPGs in the paper. The indices are slightly different than in the paper (might have missed a transpose somewhere), but the result comes out correct, so it is probably fine. Note that it prints over 7 MB of data. It might be a good idea to pipe the output to a file first before looking at it:
python3 print_equations.py > equations.txtThe individual equations could be simplified a bit more (e.q. by using SymPy) but I wanted to keep the dependencies to a minimum.
Make sure to run the code in the same directory as the files
factorizations_f2.npzandfactorizations_r.npz.print_equations.pyFor example, the generated code for general 2-by-2 times 2-by-2 matrix multiplication is
For 4-by-4 times 4-by-4 matrix multiplication in $\mathbb {Z} _{2}$, i.e. when doing mod 2 math (missed that on first reading), the code is:
For the Matlab users: Note that
.ravel()in Python flattens row-wise, not column-wise. The same goes forreshape.